Java Language
대기열 및 대기열

PriorityQueue의 사용법

PriorityQueue 는 데이터 구조입니다. SortedSet 와 마찬가지로 PriorityQueue 도 PriorityQueue 따라 요소를 정렬합니다. 우선 순위가 높은 요소가 먼저옵니다. PriorityQueue 의 타입은 데이터 구조의 요소의 우선 순위를 결정하는 comparable 또는 comparator 인터페이스를 구현해야합니다.

//The type of the PriorityQueue is Integer.
PriorityQueue<Integer> queue = new PriorityQueue<Integer>();

//The elements are added to the PriorityQueue
queue.addAll( Arrays.asList( 9, 2, 3, 1, 3, 8 ) );

//The PriorityQueue sorts the elements by using compareTo method of the Integer Class
//The head of this queue is the least element with respect to the specified ordering
System.out.println( queue );  //The Output: [1, 2, 3, 9, 3, 8]
queue.remove();
System.out.println( queue );  //The Output: [2, 3, 3, 9, 8]
queue.remove();
System.out.println( queue );  //The Output: [3, 8, 3, 9]
queue.remove();
System.out.println( queue );  //The Output: [3, 8, 9]
queue.remove();
System.out.println( queue );  //The Output: [8, 9]
queue.remove();
System.out.println( queue );  //The Output: [9]
queue.remove();
System.out.println( queue );  //The Output: []

FIFO 대기열로서의 LinkedList

java.util.LinkedList 클래스는 구현하면서 java.util.List 의 범용 구현 java.util.Queue 너무에서 작동하는 인터페이스 FIFO (시, 가장 먼저) 원칙.

아래 예제에서 offer() 메소드를 사용하면 요소가 LinkedList 삽입됩니다. 이 삽입 조작은 enqueue 라고합니다. 아래 while 루프에서 요소는 FIFO를 기반으로 Queue 에서 제거됩니다. 이 작업을 dequeue 라고합니다.

Queue<String> queue = new LinkedList<String>();

queue.offer( "first element" );
queue.offer( "second element" );
queue.offer( "third element" );
queue.offer( "fourth. element" );
queue.offer( "fifth. element" );

while ( !queue.isEmpty() ) {
  System.out.println( queue.poll() );
}

이 코드의 출력은 다음과 같습니다.

first element
second element
third element
fourth element
fifth element

출력에서 볼 수 있듯이 첫 번째로 삽입 된 요소 인 "첫 번째 요소"가 먼저 제거되고 두 번째 요소는 두 번째 위치에서 제거됩니다.

스택

스택이란 무엇입니까?

Java에서 Stacks는 객체의 LIFO (Last In, First Out) 데이터 구조입니다.

Stack API

Java에는 다음과 같은 메소드가 포함 된 Stack API가 들어 있습니다.

Stack()            //Creates an empty Stack
isEmpty()          //Is the Stack Empty?             Return Type: Boolean
push(Item item)    //push an item onto the stack
pop()              //removes item from top of stack  Return Type: Item
size()             //returns # of items in stack     Return Type: Int

예

import java.util.*;

public class StackExample {

   public static void main(String args[]) {
      Stack st = new Stack();
      System.out.println("stack: " + st);
      
      st.push(10);
      System.out.println("10 was pushed to the stack");
      System.out.println("stack: " + st);
      
      st.push(15);
      System.out.println("15 was pushed to the stack");
      System.out.println("stack: " + st);
      
      st.push(80);
      System.out.println("80 was pushed to the stack");
      System.out.println("stack: " + st);
      
      st.pop();
      System.out.println("80 was popped from the stack");
      System.out.println("stack: " + st);
      
      st.pop();
      System.out.println("15 was popped from the stack");
      System.out.println("stack: " + st);
      
      st.pop();
      System.out.println("10 was popped from the stack");
      System.out.println("stack: " + st);
      
     if(st.isEmpty())
      {
         System.out.println("empty stack");
      }
   }
}

반환 값 :

stack: []
10 was pushed to the stack
stack: [10]
15 was pushed to the stack
stack: [10, 15]
80 was pushed to the stack
stack: [10, 15, 80]
80 was popped from the stack
stack: [10, 15]
15 was popped from the stack
stack: [10]
10 was popped from the stack
stack: []
empty stack

BlockingQueue

BlockingQueue는 인터페이스입니다.이 인터페이스는 큐에서 대기열에서 제외하려고 시도하거나 큐가 비어 있거나 큐에 항목을 대기열에 넣으려고 할 때 차단합니다. 빈 큐에서 큐 해제를 시도하는 스레드는 다른 스레드가 항목을 큐에 삽입 할 때까지 차단됩니다. 전체 큐에서 항목을 큐에 넣으려고하는 스레드는 다른 스레드가 하나 이상의 항목을 큐에서 제거하거나 큐를 완전히 지우거나 큐에서 공간을 만들 때까지 차단됩니다.

BlockingQueue 메소드는 즉시 만족할 수없는 연산을 처리하는 여러 가지 방법으로 네 가지 형식으로 제공되지만 미래의 어떤 시점에서 만족 될 수 있습니다. 하나는 예외를 발생시키고 두 번째는 특수 값 (null 또는 false)을 반환합니다. 작업), 작업이 성공할 때까지 세 번째는 현재 스레드를 무기한 차단하고, 포기하기 전에 지정된 최대 시간 제한 만 위해 네 번째 블록을 차단합니다.

BlockingQueue 는 바운드 또는 언 바운드가 가능 합니다. 바운드 형식의 BlockingQueue는, 초기 용량으로 초기화됩니다.

BlockingQueue<String> bQueue = new ArrayBlockingQueue<String>(2);

큐의 크기가 정의 된 초기 용량과 같으면 put () 메서드에 대한 모든 호출이 차단됩니다.

안 바운드 형식의 Queue는 용량없이 초기화됩니다. 실제로는 디폴트로 Integer.MAX_VALUE로 초기화됩니다.

BlockingQueue 일반적인 구현은 다음과 같습니다.

1. ArrayBlockingQueue
2. LinkedBlockingQueue
3. PriorityBlockingQueue

이제 ArrayBlockingQueue 의 예를 살펴 보겠습니다.

BlockingQueue<String> bQueue = new ArrayBlockingQueue<>(2);
bQueue.put("This is entry 1");
System.out.println("Entry one done");
bQueue.put("This is entry 2");
System.out.println("Entry two done");
bQueue.put("This is entry 3");
System.out.println("Entry three done");

그러면 다음과 같이 인쇄됩니다.

Entry one done
Entry two done

그리고 스레드는 두 번째 출력 후에 차단됩니다.

대기열 인터페이스

기초

Queue 은 처리하기 전에 요소를 보유하기위한 모음입니다. 대기열은 일반적으로 요소를 FIFO (선입 선출) 방식으로 정렬합니다.

대기열의 헤드는 제거 또는 폴링 호출에 의해 제거 될 요소입니다. FIFO 대기열에서 모든 새 요소는 대기열의 끝에 삽입됩니다.

대기열 인터페이스

public interface Queue<E> extends Collection<E> {
    boolean add(E e);

    boolean offer(E e);

    E remove();

    E poll();

    E element();

    E peek();
}

각 Queue 메서드는 두 가지 형식으로 존재합니다.

• 조작이 실패했을 경우는 예외를 Throw합니다.
• other는 작업이 실패 할 경우 특수 값을 반환합니다 (작업에 따라 null 또는 false .

Deque

Deque 는 큐의 앞 또는 뒤쪽에 요소를 추가 할 수있는 "이중 종료 큐"입니다. 큐는 요소를 큐의 끝에 추가 할 수 있습니다.

Deque 는 Queue 인터페이스를 상속받습니다. 즉, 정규 메소드가 남아 있음을 의미하지만, Deque 인터페이스는 큐에보다 유연한 추가 메소드를 제공합니다. 큐가 작동하는 방식을 알고 있다면 추가 메서드는 실제로 자체적으로 말합니다. 이러한 메서드는보다 융통성을 더하기위한 것입니다.

물론 offer , poll 및 peek 대한 동일한 옵션을 사용할 수 있지만 예외가 아니라 특수 값으로 작동합니다. 그들이 여기에서하는 일을 보여줄 필요가 없습니다.

요소 추가 및 액세스

Deque의 말미에 요소를 추가하려면, add() 메소드를 호출합니다. deque의 head와 tail에 요소를 추가하는 addFirst() 및 addLast() 메서드를 사용할 수도 있습니다.

Deque<String> dequeA = new LinkedList<>();

dequeA.add("element 1");      //add element at tail
dequeA.addFirst("element 2"); //add element at head
dequeA.addLast("element 3");  //add element at tail

큐에서 요소를 가져 오지 않고 큐의 맨 위에있는 요소를 들여다 볼 수 있습니다. 이 작업은 element() 메서드를 통해 수행됩니다. Deque 의 첫 x 째 W 마지막 요소를 리턴하는 getFirst() W getLast() 메소드를 사용할 수도 있습니다. 어떻게 보이는지 다음과 같습니다.

String firstElement0 = dequeA.element();
String firstElement1 = dequeA.getFirst();
String lastElement = dequeA.getLast();

요소 제거하기

양단 큐에서 요소를 제거하려면 remove remove() , removeFirst() 및 removeLast() 메서드를 호출합니다. 다음은 몇 가지 예입니다.

String firstElement = dequeA.remove();
String firstElement = dequeA.removeFirst();
String lastElement  = dequeA.removeLast();