[DataStructure] Queue (Java)

Queue

참고링크

Module java.base
Package java.util
Interface Queue<E>
Type Parameters:
E - the type of elements held in this queue
All Superinterfaces:
Collection<E>, Iterable<E>
All Known Subinterfaces:
BlockingDeque<E>, BlockingQueue<E>, Deque<E>, TransferQueue<E>
All Known Implementing Classes:
AbstractQueue, ArrayBlockingQueue, ArrayDeque, ConcurrentLinkedDeque, ConcurrentLinkedQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedList, LinkedTransferQueue, PriorityBlockingQueue, PriorityQueue, SynchronousQueue
public interface Queue<E>
extends Collection<E>

설명

처리전에 요소를 가지고 있도록 디자인된 컬렉션입니다.

기본적인 자료구조 동작 이외에, 추가적인 삽입, 추출, 검사 같은 작업을 제공합니다.
각 메서드들은 두가지 형태로 되어있습니다: 하나는 작업이 실패하면 예외가 발생하고,

다른 하나는 특수 값을 반환합니다.

insert 작업의 특수한 값을 반환하는 형식은 용량이 제한된 queue implementations와 함께 사용하도록 설계 되었습니다.
대부분의 implementations에서 insert 작업은 실패 할 수 없습니다.

Queue methods 요약

- Throws exception    
Insert    : add(e)
Remove    : remove()
Examine    : element()

- Returns special value
Insert    : offer(e)
Remove    : poll()
Examine    : peek()

큐는 일반적으로 FIFO(선입선출) 방식으로 요소를 정렬하지만 반드시 그런것은 아닙니다.
예외 중에는 제공된 comparator, 또는 요소의 자연스러운 순서에 따라 요소를

정렬하는 우선순위 Queue와 그리고 LIFO queues (또는 스택) 이 있습니다.
사용된 순서가 무엇이든 대기열의 HEAD는 remove()또는 poll() 에 의해 제거되는 요소입니다.
FIFO queue 에서는 모든 요소가 queue의 TAIL에 들어갑니다.

다른 종류의 큐는 아마 다른 위치 규칙을 사용할 수 있습니다.
모든 큐 구현은 순서 속성을 지정해야 합니다.

 

offer 메서드는 가능한 경우 요소를 삽입하고 그렇지 않으면 false를 반환합니다.
Collection.add 메서드와 다릅니다.

Collection.add 메서드는 요소를 추가할때 확인되지 않은 exception으로 보내야만 add가 실패할 수 있는 메서드입니다.
offer 메서드는 예를 들어 사이즈가 제한된 queue에서 오류가 예외적인 것이 아니라 정상적인 경우에 사용하도록 설계되었습니다.

 

remove() 및 poll() 메서드는 대기열의 헤드를 제거하고 반환합니다.
정확하게 queue에서 제거된 요소는 queue의 ordering 정책 기능입니다 이 정책은 구현에 따라 다릅니다.
remove()와 poll() 메서드는 queue가 비어있는 상황에서만 다릅니다:

remove()는 exception을 발생시키는 반면 poll은 null을 반환합니다.

 

element() 와 peek() 메소드는 HEAD 요소를 반환하는데 삭제는 하지 않습니다.

 

Queue 인터페이스는 동시 프로그래밍에서 일반적인 blocking queue 메서드를 정의하지 않습니다.
요소가 나타나거나 공간이 사용 가능해질 때까지 기다리는 이러한 메서드는 이 인터페이스를 확장하는 BlockingQueue 인터페이스에 정의되어 있습니다.

 

LinkedList와 같은 일부 구현에는 null insert를 금지하지 않지만 queue 구현은 일반적으로 null 요소의 insert를 허용하지 않습니다.

 

허용하는 구현에서도 null은 queue에 요소가 포함되어 있지 않음을 나타내기 위해 poll 메서드에 의해 특수 반환 값으로 사용되기 때문에 null을 queue에 insert해서는 안됩니다.

 

queue 구현은 일반적으로 equals 및 hashCode 메서드의 요소 기반 버전을 정의하지 않고 대신 Object 클래스에서 ID 기반 버전을 상속합니다. 요소 기반 동등성은 동일한 요소이지만 순서 속성이 다른 queue에 대해 항상 잘 정의되지 않기 때문입니다.

 

이 인터페이스는 Java Collections Framework의 구성원입니다.

메서드

boolean    add​(E e)    
용량 제한을 위반하지 않고 즉시 수행할 수 있는 경우 지정된 요소를 대기열에 삽입하고 성공 시 true를 반환하고 현재 사용 가능한 공간이 없으면 IllegalStateException을 발생시킵니다.
E    element()    
이 큐의 헤드를 검색하지만 제거하지는 않습니다.
boolean    offer​(E e)    
용량 제한을 위반하지 않고 즉시 수행할 수 있는 경우 지정된 요소를 이 대기열에 삽입합니다.
E    peek()    
이 대기열의 헤드를 검색하지만 제거하지는 않습니다. 이 대기열이 비어 있으면 null을 반환합니다.
E    poll()    
이 대기열의 헤드를 검색 및 제거하거나 이 대기열이 비어 있으면 null을 반환합니다.
E    remove()    
이 대기열의 헤드를 검색하고 제거합니다.

사용법

import java.util.Queue;

public class QueueMain {
  public static void main(String[] args){
    Queue queue = new LinkedList();

    queue.add("test1");
    queue.add("test2");
    queue.offer("test3");
    queue.offer("test4");

    System.out.println(queue.remove());
    System.out.println(queue.element());
    System.out.println(queue.poll());
    System.out.println(queue.peek());
  }
}


/* 결과
test1
test2
test2
test3
*/

시간복잡도

add() - queue TAIL에 요소를 추가합니다. 따라서 TAIL만 업데이트하므로 O(1)
remove() - queue HEAD에 요소를 제거합니다. O(1)

참고링크

공간복잡도

대부분의 Collection들은 O(n)
참고링크
참고링크