Java 대기열 인터페이스 및 해당 구현

여기에서는 Java Queue 인터페이스에 대해 설명합니다. 큐 데이터 구조가 무엇인지, Java에서 어떻게 표현되는지, 모든 큐에서 가장 중요한 메소드는 무엇인지 알아낼 것입니다 . 또한 Java 언어로 된 Queue 구현은 무엇입니까? 그런 다음 가장 중요한 구현을 자세히 살펴보고 예제를 통해 학습합니다.

대기열 데이터 구조

대기열은 작업 수행의 특정 순서인 선입선출(FIFO)이 있는 선형 추상 데이터 구조입니다. 즉, 구조의 끝에만 요소를 추가(또는 대기열에 넣거나 대기열에 넣기)할 수 있고 처음부터 요소를 가져올 수 있습니다(대기열에서 빼거나 ​​대기열에서 제거). Queue 데이터 구조를 매우 쉽게 상상할 수 있습니다. 실생활에서 대기열이나 고객의 줄처럼 보입니다. 먼저 온 고객이 먼저 서비스를 받을 것입니다. 맥도날드나 다른 곳에서 줄을 서 있는 사람이 4명이라면 가장 먼저 줄을 서는 사람이 먼저 가게를 차지하게 됩니다. 새로운 손님이 오면 그 손님은 5번째로 햄버거를 사게 될 것입니다. 그래서 큐로 작업을 하다보면 끝에 새로운 요소가 추가되고 요소를 얻고자 하면 처음부터 가져오게 됩니다. 이것이 고전적인 대기열 데이터 구조 작업의 주요 원칙입니다.

자바의 대기열

Java의 대기열은 인터페이스입니다. Oracle 설명서에 따르면 대기열 인터페이스에는 2개의 수퍼 인터페이스, 대기열에서 상속되는 4개의 다른 인터페이스 및 매우 인상적인 클래스 목록이 있습니다. 무슨 뜻이에요? 먼저 Java Queue는 Collection Framework의 일부이며 Collection 인터페이스를 구현합니다. 따라서 삽입, 삭제 등 Collection 인터페이스의 모든 메소드를 지원합니다. Queue는 개체가 "for-each 루프" 문의 대상이 되도록 하는 Iterable 인터페이스를 구현합니다.

대기열 방법 Java

Queue는 여러 메서드를 선언합니다. 인터페이스의 메소드로서 Queue를 구현하는 모든 클래스에 표시되어야 합니다. 가장 중요한 대기열 메서드인 Java:

• Boolean offer() – 가능한 경우 대기열에 새 요소를 삽입합니다.
• Boolean add(E e) – 가능한 경우 대기열에 새 요소를 삽입합니다. 성공하면 true를 반환하고 공간이 없으면 IllegalStateException을 throw합니다.
• Object poll() – 헤드에서 요소를 검색하고 제거합니다. 대기열이 비어 있으면 null을 반환합니다.
• Object remove() – 큐의 헤드에서 요소를 검색하고 제거합니다.
• Object peek() – 대기열의 헤드에서 요소를 검색하지만 제거하지는 않습니다. 대기열이 비어 있으면 null을 반환합니다.
• Object element() – 대기열의 헤드에서 요소를 검색하지만 제거하지는 않습니다.

Java Queue의 하위 인터페이스

대기열 인터페이스는 4개의 하위 인터페이스( BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E>) 에 의해 상속됩니다 . Deques, Blocking Queues 및 Transfer Queues with BlockingDeque의 세 그룹으로 나눌 수 있습니다. 이 그룹들을 살짝 살펴보겠습니다.

데케스

Deque는 D ouble- Ended Queue 를 의미하며 큐(선입선출/FIFO)로 데이터의 꼬리에서 추가 또는 제거를 지원하거나 스택( last - in- 선입선출/LIFO). Deque 인터페이스를 구현하는 클래스: ArrayDeque, ConcurrentLinkedDeque, LinkedBlockingDeque, LinkedList.

차단 대기열

블로킹 큐는 두 가지 경우에 스레드를 차단하는 큐입니다.

• 스레드가 빈 큐에서 요소를 가져오려고 합니다.
• 스레드가 전체 대기열에 요소를 넣으려고 합니다.

스레드가 빈 큐에서 항목을 가져오려고 하면 다른 스레드가 항목을 큐에 넣을 때까지 기다립니다. 마찬가지로 스레드가 전체 큐에 요소를 넣으려고 할 때 다른 스레드가 요소를 위한 여유 공간을 확보하기 위해 큐에서 요소를 가져올 때까지 기다립니다. 물론 "가득 찬 큐"라는 개념은 큐의 크기가 제한되어 있으며 일반적으로 생성자에 지정되어 있음을 의미합니다. 표준 차단 대기열에는 LinkedBlockingQueue, SynchronousQueue 및 ArrayBlockingQueue가 포함됩니다. BlockingQueue 인터페이스 구현 클래스 : ArrayBlockingQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedTransferQueue, PriorityBlockingQueue, SynchronousQueue. BlockingDequeBlockingQueue의 하위 인터페이스입니다. BlockingQueue와 같은 BlockingDeque는 차단 대기열이지만 양방향입니다. 따라서 Deque 인터페이스의 속성을 상속합니다. 다중 스레드 실행을 지향하며 제로 요소를 허용하지 않으며 용량이 제한될 수 있습니다. BlockingDeque 인터페이스의 구현은 큐가 비어 있는 경우 요소를 가져오고 큐가 가득 찬 경우 큐에 요소를 추가하는 작업을 차단합니다.

전송 대기열

TransferQueue 인터페이스는 BlockingQueue 인터페이스를 확장합니다. 그러나 대기열이 비어 있거나(읽기) 가득 찬 경우(쓰기) 스레드가 차단될 수 있는 BlockingQueue 인터페이스 대기열의 구현과 달리 TransferQueue 인터페이스 대기열은 다른 스트림이 요소를 검색할 때까지 쓰기 스트림을 차단합니다. 이를 위해 전송 방법을 사용하십시오. 즉, BlockingQueue의 구현은 Producer가 생성한 요소가 대기열에 있어야 함을 보장하는 반면 TransferQueue의 구현은 Producer 요소가 Consumer에 의해 "수신"되도록 보장합니다. TransferQueue 인터페이스의 공식 Java 구현은 LinkedTransferQueue뿐입니다.

Java 대기열 구현

Queue 인터페이스를 구현하는 많은 클래스가 있습니다.

• Queue Java 8 문서에 따른 AbstractQueue , 이 추상 클래스는 일부 Queue 작업의 기본 구현을 제공합니다. null 요소를 허용하지 않습니다. Queue classic offer , poll 및 peek 를 기반으로 하는 추가, 제거 및 요소 메서드가 각각 3개 더 있습니다 . 그러나 false 또는 null 반환을 통해 실패를 나타내는 대신 예외를 throw합니다.
• ArrayBlockingQueue — 배열이 지원하는 고정 크기 FIFO 차단 대기열
• ArrayDeque — Deque 인터페이스의 크기 조정 가능한 배열 구현
• ConcurrentLinkedDeque — 연결된 노드를 기반으로 하는 무제한 동시 deque입니다.
• ConcurrentLinkedQueue — 연결된 노드를 기반으로 하는 제한 없는 스레드 안전 대기열입니다.
• DelayQueue — 힙이 지원하는 시간 기반 스케줄링 대기열
• LinkedBlockingDeque — Deque 인터페이스의 동시 구현.
• LinkedBlockingQueue - 연결된 노드가 지원하는 선택적으로 제한된 FIFO 차단 대기열
• LinkedList — List 및 Deque 인터페이스의 이중 연결 목록 구현입니다. 모든 선택적 목록 작업을 구현하고 모든 요소(null 포함)를 허용합니다.
• LinkedTransferQueue — 연결된 노드를 기반으로 하는 무제한 TransferQueue
• PriorityBlockingQueue — 힙이 지원하는 무제한 차단 우선순위 큐
• PriorityQueue — 힙 데이터 구조를 기반으로 하는 우선 순위 큐
• SynchronousQueue — 각 삽입 작업이 다른 스레드에 의한 해당 제거 작업을 기다려야 하는 블로킹 대기열이며 그 반대의 경우도 마찬가지입니다.

가장 널리 사용되는 구현은 LinkedList, ArrayBlockingQueue 및 PriorityQueue입니다. 더 나은 이해를 위해 그것들을 살펴보고 몇 가지 예를 들어 봅시다.

LinkedList

Java의 클래스 LinkedList는 List 및 Deque 인터페이스를 구현합니다. 따라서 양쪽에서 요소를 추가하고 제거하는 것을 지원하는 양방향 대기열인 List와 Deque의 조합입니다. Java에서 LinkedList는 이중으로 연결된 List입니다. List의 모든 요소는 Node를 호출하고 개체와 두 개의 인접한 개체(이전 및 다음)에 대한 참조를 포함합니다. LinkedList가 메모리 사용 측면에서 그다지 효과적이지 않다고 말할 수 있습니다. 사실이지만 이 데이터 구조는 삽입 및 삭제 작업 성능의 경우에 유용할 수 있습니다. 그러나 반복자를 사용하는 경우에만 발생합니다(이 경우 일정한 시간에 발생). 인덱스에 의한 액세스 작업은 끝의 시작 부분(둘 중 더 가까운 쪽)에서 원하는 요소까지 검색하여 수행됩니다. 그러나 요소 간 참조를 저장하기 위한 추가 비용을 잊지 마십시오. 따라서 LinkedList는 Java에서 가장 많이 사용되는 대기열 구현입니다. 이는 List 및 Deque의 구현이기도 하며 null을 포함한 모든 개체로 구성된 양방향 대기열을 만들 수 있습니다. LinkedList는 요소의 모음입니다.

LinkedList 생성자

매개변수가 없는 LinkedList()는 빈 목록을 구성하는 데 사용됩니다. LinkedList(Collection<? extends E> c)는 지정된 컬렉션의 요소를 순서대로 포함하는 목록을 생성하기 위한 것으로 컬렉션의 반복자에 의해 반환됩니다.

주요 LinkedList 방법:

• add(E element) 이 목록의 끝에 지정된 요소를 추가합니다.
• add(int index, E element) 지정된 위치 index에 요소를 삽입합니다.
• get(int index) 이 목록의 지정된 위치에 있는 요소를 반환합니다.
• remove(int index) 인덱스 위치에 있는 요소를 제거합니다.
• remove(Object o) 이 목록에 있는 경우 이 목록에서 첫 번째 ?o 요소를 제거합니다.
• remove() 목록의 첫 번째 요소를 검색하고 제거합니다.
• addFirst(), addLast() 목록의 시작/끝에 요소 추가
• clear()는 목록에서 모든 요소를 ​​제거합니다.
• contains(Object o)는 목록에 o 요소가 포함되어 있으면 true를 반환합니다.
• indexOf(Object o)는 o 요소가 처음 나타나는 인덱스를 반환하거나 목록에 없으면 -1을 반환합니다.
• set(int index, E element) 인덱스 위치에 있는 요소를 해당 요소로 바꿉니다.
• size()는 목록에 있는 요소의 수량을 반환합니다.
• toArray()는 처음부터 마지막 ​​요소까지 목록의 모든 요소를 ​​포함하는 배열을 반환합니다.
• 스택에서 요소를 팝하는 pop()(목록으로 표시됨)
• 스택에 요소를 푸시하는 push(E e)(이 목록으로 표시됨)

Java Queue 예제 — LinkedList(여러 방법으로 요소 넣기 및 제거)

import java.util.*;
 
public class LinkedListTest {
 
       public static void main(String args[]){
 
           LinkedList<Integer> myLinkedList= new LinkedList<Integer>();
           myLinkedList.add(1);
           myLinkedList.add(2);
           myLinkedList.add(4);
           System.out.println("three added elements: " + myLinkedList);
           //put one element into the head, not to the tail:
           myLinkedList.push(5);
           System.out.println("The new element last in will be the first: " + myLinkedList);
           //add new element at the specified position:
           myLinkedList.add(4,3);
           //put one element into the head, not to the tail (same as push):
           myLinkedList.addFirst(6);
           System.out.println(myLinkedList);
           //now remove element no 2 (it is 1):
           myLinkedList.remove(2);
           System.out.println(myLinkedList);
           //now remove the head of the list
           myLinkedList.pop();
           System.out.println(myLinkedList);
           //remove with the other method
           myLinkedList.remove();
           System.out.println(myLinkedList);
           //and with one more
           myLinkedList.poll();
           System.out.println(myLinkedList);
       }
       }

우선순위 대기열

PriorityQueue는 FIFO의 일반적인 의미에서 정확히 대기열이 아닙니다. 우선 순위 큐의 요소는 사용되는 생성자에 따라 자연 순서에 따라 또는 큐 생성 시 제공되는 Comparator에 따라 순서가 지정됩니다. 그러나 목록과 같은 선형 구조(가장 큰 것에서 가장 작은 것 또는 그 반대)와 같은 순서는 아닙니다. 우선 순위 최소 힙을 기반으로 하는 우선 순위 대기열입니다. 힙은 이진 트리를 기반으로 하는 데이터 구조입니다.. 각 부모의 우선 순위는 자식의 우선 순위보다 큽니다. 각 부모가 2개 이하의 자식을 가지고 있고 수준을 채우는 것이 위에서 아래로(동일한 수준에서 왼쪽에서 오른쪽으로) 진행되는 경우 트리를 완전 이진법이라고 합니다. 이진 힙은 새 요소가 추가되거나 제거될 때마다 자체적으로 재구성됩니다. 최소 힙의 경우 삽입 순서에 관계없이 가장 작은 요소가 루트로 이동합니다. 이 최소 힙을 기반으로 하는 우선 순위 큐이므로 정수의 PriorityQueue가 있는 경우 첫 번째 요소는 이 숫자 중 가장 작은 값이 됩니다. 루트를 삭제하면 그 다음으로 작은 것이 루트가 됩니다.

주요 PriorityQueue 방법:

• boolean add(object)는 지정된 요소를 우선 순위 대기열에 삽입합니다. 성공하면 true를 반환합니다. 대기열이 가득 차면 메서드에서 예외가 발생합니다.
• boolean offer(object)는 지정된 요소를 이 우선 순위 대기열에 삽입합니다. 대기열이 가득 차면 메서드는 false를 반환합니다.
• boolean remove(object)는 지정된 요소가 있는 경우 이 대기열에서 단일 인스턴스를 제거합니다.
• 객체 poll()은 이 대기열의 헤드를 검색하고 제거합니다. 대기열이 비어 있으면 null을 반환합니다.
• void clear()는 우선순위 큐에서 모든 요소를 ​​제거합니다.
• Object element()는 이 큐의 헤드를 제거하지 않고 검색합니다. 대기열이 비어 있으면 NoSuchElementException이 발생합니다.
• Object peek()는 대기열을 제거하지 않고 대기열의 헤드를 검색합니다. 대기열이 비어 있으면 null을 반환합니다.
• 부울 contains(객체 o)는 대기열에 o 요소가 포함된 경우 true를 반환합니다.
• int size()는 이 대기열의 요소 수를 반환합니다.

PriorityQueue의 예

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class PriorityQueueExample {
   public static void main(String[] args) {
 
       Queue<Integer> queueL = new LinkedList<>();
       for (int i = 5; i > 0; i--) {
           queueL.add(i);
       }
       System.out.println("Print our LinkedList Queue (FIFO): " + queueL);
       Queue<Integer> priorityQueue = new PriorityQueue<>();
 
       for (int i = 5; i > 0; i--) {
       priorityQueue.offer(i);
       }
 
       System.out.println("PriorityQueue printing (by iterating, no elements removing): " + priorityQueue);
       System.out.println("Print PriorityQueue using poll() (by retrieval): " );
       while (!priorityQueue.isEmpty()) {
           System.out.println(priorityQueue.poll());
       }
}
}
Print our LinkedList Queue (FIFO): [5, 4, 3, 2, 1]
PriorityQueue printing (by iterating, no elements removing): [1, 2, 4, 5, 3]
Print our  PriorityQueue using poll() (by retrieval): 
1
2
3
4
5

우선 순위 대기열은 이진 힙을 기반으로 하므로 요소를 선형 정렬 순서로 유지하지 않는다는 점을 이해하는 것이 중요합니다. 루트에서 리프까지의 모든 방법은 순서가 있지만 루트에서 다른 방법은 그렇지 않습니다. 즉, 대기열의 최소 요소를 매우 빠르게 얻을 수 있습니다. 매번 헤드를 삭제하면 정렬된 구조가 인쇄됩니다.

ArrayBlockingQueue

ArrayBlockingQueue 의 내부 데이터 구조요소를 저장하는 원형 배열을 기반으로 합니다. 큐의 끝에 새로운 요소가 삽입되고 추출 작업이 큐의 헤드에서 요소를 반환하는 경우의 일반적인 큐(FIFO)입니다. 한 번 생성된 큐 용량은 변경할 수 없습니다. 전체 대기열에 요소를 삽입(넣기)하려고 하면 흐름이 차단됩니다. 빈 대기열에서 요소를 가져오려고 하면 스레드가 차단됩니다. 이전에 말했듯이 이 배열은 원형입니다. 즉, 배열의 첫 번째 요소와 마지막 요소가 논리적으로 인접한 것으로 취급됩니다. 대기열은 요소를 대기열에 넣거나 대기열에서 제거할 때마다 머리 요소와 꼬리 요소의 인덱스를 전진시킵니다. 일부 인덱스가 배열의 마지막 요소를 진행하면 0부터 다시 시작합니다. 따라서, 큐는 헤드 제거의 경우(일반적인 배열에서와 같이) 모든 요소를 ​​이동할 필요가 없습니다. 단, Iterator.remove를 사용하여 중간에서 요소를 제거하는 경우 요소가 이동됩니다. ArrayBlockingQueue는 생산자(요소 삽입)와 소비자(요소 추출)의 대기 흐름 작업을 주문하기 위해 생성자에 공정한 매개변수가 있는 추가 공정성 정책을 지원합니다 . 기본적으로 순서는 보장되지 않습니다. 그러나 대기열이 "fair == true"로 생성된 경우 ArrayBlockingQueue 클래스의 구현은 FIFO 순서로 스레드 액세스를 제공합니다. 주식은 일반적으로 대역폭을 줄이지만 변동성을 줄이고 리소스 부족을 방지합니다.

ArrayBlockingQueue 클래스 생성자

• ArrayBlockingQueue(정수 용량)는 기본 액세스 정책을 사용하여 고정 용량의 대기열을 생성합니다.
• ArrayBlockingQueue(int capacity, boolean fair)는 고정된 용량과 지정된 액세스 정책으로 대기열을 생성합니다.
• ArrayBlockingQueue(int capacity, boolean fair, Collection <? extends E> c)는 액세스 정책에 의해 지정된 고정 용량으로 큐를 생성하고 큐에 요소를 포함합니다.

여기에 BlockingQueueExample 예제가 있습니다. 하나의 요소와 공정한 플래그의 용량으로 ArrayBlockingQueue의 대기열을 생성합니다. 두 개의 스레드가 시작됩니다. 그 중 첫 번째인 생산자 스레드는 put 메서드를 사용하여 메시지 배열의 메시지를 큐에 넣습니다. 두 번째 소비자인 스레드는 take 메서드를 사용하여 큐에서 요소를 읽고 콘솔에 표시합니다. 요소의 순서는 대기열의 자연스러운 순서입니다.

import java.util.concurrent.*;
 
public class ArrayBlockingQueueExample {
 
   private BlockingQueue<Integer> blockingQueue;
   private final Integer[]  myArray = {1,2,3,4,5};
  
       public ArrayBlockingQueueExample ()
       { blockingQueue = new ArrayBlockingQueue<Integer>(1, true);
           (new Thread(new Producer())).start();
           (new Thread(new Consumer())).start();
       }
 
       class Producer implements Runnable
       {
           public void run() {
               try {
                   int counter = 0;
                   for (int i=0; i < myArray.length; i++) {
                       blockingQueue.put(myArray[i]);
                       if (counter++ < 2)
                           Thread.sleep(3000);
                   } blockingQueue.put(-1);
               }
               catch (InterruptedException e) {
                   System.err.println(e.getMessage());
               }
           }
       }
 
       class Consumer implements Runnable
       {
           public void run() {
               try {
                   Integer message = 0;
                   while (!((message = blockingQueue.take()).equals(-1)))
                       System.out.println(message);
               } catch (InterruptedException e) {
                   System.err.println(e.getMessage());
               }
           }
       }
 
       public static void main(String[] args) {
           new ArrayBlockingQueueExample();
       }
   }

출력은 자연스러운 순서의 대기열입니다. 처음 두 요소는 지연되어 나타납니다. 배운 내용을 보강하려면 Java 과정에서 비디오 강의를 시청하는 것이 좋습니다.

결론

• Queue는 큐의 끝에 요소를 삽입하고 큐의 시작 부분에서 제거하는 데 사용됩니다. FIFO 개념을 따릅니다.
• Java Queue는 Collection Framework의 일부이며 Collection 인터페이스를 구현합니다. 따라서 삽입, 삭제 등 Collection 인터페이스의 모든 메소드를 지원합니다.
• Queue의 가장 자주 사용되는 구현은 LinkedList, ArrayBlockingQueue 및 PriorityQueue입니다.
• 우선 순위 큐의 요소는 사용되는 생성자에 따라 자연 순서에 따라 또는 큐 생성 시 제공되는 Comparator에 따라 순서가 지정됩니다.
• BlockingQueues에서 null 작업이 수행되면 NullPointerException이 발생합니다.