java.util.collections 총정리 Queue편

저번의 set에 이어 queue에 대해서도 알아보자.

javadoc, 직접 코드를 확인해보면서 분석해보자.

 

java.util에 존재하는 collection

아래와 같은 상속, 구현 구조를 띄고 있다. 

•  Collection
  • Queue
    • Deque
      • ArrayDeque
    • AbstractQeue
    • PrioirtyQueue

Queue

public interface Queue<E> extends Collection<E>

위와 같이 Collection을 확장하고 있다.

 

javadocs에 기술된 내용을 의역해보면 아래와 같다

 

1.5에서 소개됨. 처리하기 전에 elements들을 담아두기 위해 설계된 collection이다.

기본적인 collection의 연산 외에 추가적인 insertion, extraction, inspection 연산을 제공한다.

각각의 메소드는 연산에 따라 두 종류의 형태를 띈다

 

1. 예외가 발생하면 thows하거나

2. null, false 등의 값을 리턴한다.

 

큐는 일반적으로 (항상 그렇진 않지만), FIFO의 순서로 저장된다. 

우선순위 큐는 supplied comparator에 의한 순으로 저장되고, Stack은 LIFO 순으로 저장된다.

어떤 순서로 저장되던, remove나 poll에 의해서 head에 있는 원소가 삭제되고, 모든 원소는 tail에 저장된다.

모든 Queue의 구현은 ordering properties를 명시해야 한다.

 

add 메서드는 원소를 추가하는데 실패하면 uncheked exception을 throwing한다. 하지만, offer은 false 값을 리턴한다.

그래서 offer은 예외가 발생할 수 있는 상황에서 사용하는 것은 적합하지 않다. (예를 들어 크기가 고정된 큐에 원소를 추가하는 상황)

 

remove는 poll은 큐가 비어있을 때 리턴하는 값에 차이가 있다, remove는 exception을 throws하고, poll은 null을 리턴한다.

 

element과 peek은 원소를 리턴하지만, head의 원소를 삭제하지 않는다.

 

큐의 인터페이스는 concurrent programing에서 일반적으로 쓰이는 blocking queue 메서드를 정의하지 않는다. 이러한 메서드들은 이 인터페이스를 extends하는 BlockingQueue에 정의 되어 있다.

 

큐는 일반적으로 null인 원소의 삽입을 허용하지 않는다. 

Queue의 구현은 equals와 hashCode를 구현하지 않지만,  Object에 있는 것을 상속 받는다(동일성 보장). 

왜냐하면 원소 기반의 동등성은 항상 같은 원소를 가지고 있는 queue를 위해 항상 잘 정의되어 있지 않고, 다른 ordering properties를 가진 queue를 위해 잘 정의되어 있다.

 

 

큐에 정의된 메소드는 아래와 같다

1. boolean add(E e);
2. boolean offer(E e);
3. E remove();
4. E poll();
5. E element();
6. E peek();

 

=Insert()

 

특정 원소를 queue에 insert한다. *(insert가능한 상황에서만.)

 

추가하는데 실패하면 아래와 같은 예외가 발생할 수 있다.

 

• IllegalStateException : 용량 제한으로 인해 추가될 수 없을 때.
• ClassCastException : 만역 클래스 타입이 제한되어 있을 때, 다른 클래스 타입의 원소를 추가하려고 할 때.
• NullPointerException : null인 원소가 추가되려고 할 때.
• IllegalArgumentException : 만약 원소의 property가 제한되어있을 때, 다른 property의 원소가 추가되려고 할 때

    /**
     * Inserts the specified element into this queue if it is possible to do so
     * immediately without violating capacity restrictions, returning
     * {@code true} upon success and throwing an {@code IllegalStateException}
     * if no space is currently available.
     *
     * @param e the element to add
     * @return {@code true} (as specified by {@link Collection#add})
     * @throws IllegalStateException if the element cannot be added at this
     *         time due to capacity restrictions
     * @throws ClassCastException if the class of the specified element
     *         prevents it from being added to this queue
     * @throws NullPointerException if the specified element is null and
     *         this queue does not permit null elements
     * @throws IllegalArgumentException if some property of this element
     *         prevents it from being added to this queue
     */
    boolean add(E e);

 

Offer()

queue의 사이즈가 정해져있을 때, add보다 이 메소드를 사용하는게 좋다.

(add는 추가 성공 여부에 따라 boolean값도 리턴해준다.)

 

추가하는데 실패했을 때 아래와 같은 exception들이 발생할 수 있다.

• ClassCastException : 만약 클래스 타입이 제한되어 있을 때, 다른 클래스 타입의 원소를 추가하려고 할 때.
• NullPointerException : null인 원소가 추가되려고 할 때.
• IllegalArgumentException : 만약 원소의 property가 제한되어있을 때, 다른 property의 원소가 추가되려고 할 때

 

    /**
     * Inserts the specified element into this queue if it is possible to do
     * so immediately without violating capacity restrictions.
     * When using a capacity-restricted queue, this method is generally
     * preferable to {@link #add}, which can fail to insert an element only
     * by throwing an exception.
     *
     * @param e the element to add
     * @return {@code true} if the element was added to this queue, else
     *         {@code false}
     * @throws ClassCastException if the class of the specified element
     *         prevents it from being added to this queue
     * @throws NullPointerException if the specified element is null and
     *         this queue does not permit null elements
     * @throws IllegalArgumentException if some property of this element
     *         prevents it from being added to this queue
     */
    boolean offer(E e);

 

remove()

 

큐에서 head에 있는 원소를 제거하는 함수이다. 이 메서드는 비어있을 때  NoSuchElementException을 발생시킨다는 점에서 poll과 다르다.

 

queue의 사이즈가 정해져있을 때, add보다 이 메소드를 사용하는게 좋다.

(add는 추가 성공 여부에 따라 boolean값도 리턴해준다.)

 

삭제하는데 실패했을 때 아래와 같은 예외를 발생시킨다.

 

• NoSuchElementException : 큐가 비어있어 삭제할 원소가 없을 때 발생

    /**
     * Retrieves and removes the head of this queue.  This method differs
     * from {@link #poll poll} only in that it throws an exception if this
     * queue is empty.
     *
     * @return the head of this queue
     * @throws NoSuchElementException if this queue is empty
     */
    E remove();

 

poll()

큐에서 head에 있는 원소를 제거하고 해당 원소를 리턴하는 함수이다. 이 메서드는 비어있을 때  NoSuchElementException을 발생시킨다는 점에서 poll과 다르다.

 

remove와 다르게 삭제하는데 실패하면 예외를 발생하는게 아니라 null을 리턴한다.

 

    /**
     * Retrieves and removes the head of this queue,
     * or returns {@code null} if this queue is empty.
     *
     * @return the head of this queue, or {@code null} if this queue is empty
     */
    E poll();

 

element()

poll과 다르게 원소를 삭제하지 않고 리턴한다. 값을 가져오는데 실패하면 예외를 발생시킨다. 이와 다르게 peek은 null를 리턴한다.

    /**
     * Retrieves, but does not remove, the head of this queue.  This method
     * differs from {@link #peek peek} only in that it throws an exception
     * if this queue is empty.
     *
     * @return the head of this queue
     * @throws NoSuchElementException if this queue is empty
     */
    E element();

peek()

지우지 않고 값을 리턴한다. 큐가 비어있으면 null를 리턴한다.

 

    /**
     * Retrieves, but does not remove, the head of this queue,
     * or returns {@code null} if this queue is empty.
     *
     * @return the head of this queue, or {@code null} if this queue is empty
     */
    E peek();

 

Deque

public interface Deque<E> extends Queue<E>

1.6부터 제공.

큐의 양 끝에서 원소를 insert, remove할 수 있는 선형 collection이다.

deck이라고 발음하며, double ended queue에서 따온것이다.

 

대부분의 덱의 구현은 저장할 수 있는 elements의 수가 정해져 있지 않지만. capacity가 한정된 덱의 구현도 지원한다.

이 인터페이스는 덱의 앞뒤에 접근할 수 있는 메서드들을 정의하고 있다. 

 

이 메서드들은 두가지 형태로 존재한다. 

1. 연산에 실패하면 exception을 throws한다.

2. 연산에 실패하면 null이나 false를 리턴한다.

 

2번은 특히 capacity-restricted한 덱의 구현에 사용된다.

 

덱은 LIFO 스택에 사용될 수 있다. 하지만 레거시인 Stack 클래스보다 이 인터페이스를 사용하는 것이 낫다.

덱이 stack처럼 사용될 대, stack 메소드는 아래의 덱의 메소드와 정확하게 똑같다.

 

push = addFirst

pop = removeFirst

peek = peekFirst

 

이 인터페이스는 List 인터페이스와 다르게 원소에 접근할 수 있는 index를 지원하지 않는다.

 

덱의 구현은 엄격하게 null인 원소의 삽입을 금지하지 않지만, null인 원소를 삽입하지 않도록 강하게 장려되고 있다.

왜냐하면, 덱이 비어있다는 것을 알리기 위해 특정 값으로 null이 쓰이기 때문이다.

 

덱의 구현은 element 기반의 equals, hashCode를 정의하지 않고, 동일성 보장 기반의 Object의 equals, hashCode를 상속받는다.

 

 

정의되어 있는 메서드는 아래와 같다.

(Queue, Collection 클래스에서 상속받은 메서드 생략)

• void addFirst(E e);
  
  • 덱의 앞부분에 특정 원소를 삽입함. 용량 제한에 의해 삽입에 실패하면 IllegalStateExpception이 발생.
  • 용량 제한이 있으면, offerFisrt()를 사용하는 것을 권장함.

	//  아래와 같은 상황에 다음과 같은 Exception이 발생함.
    
     * @param e the element to add
     * @throws IllegalStateException if the element cannot be added at this
     *         time due to capacity restrictions
     * @throws ClassCastException if the class of the specified element
     *         prevents it from being added to this deque
     * @throws NullPointerException if the specified element is null and this
     *         deque does not permit null elements
     * @throws IllegalArgumentException if some property of the specified
     *         element prevents it from being added to this deque
     */

• void addLast(E e);
  
  • 덱에 특정 원소를 뒤에 삽입함. 용량 제한에 의해 삽입에 실패하면 IllegalStateException이 발생함.
  • 용량 제한이 있는 덱세어는 일반적으로 offerLast()를 사용하길 권장함.

	// 발생할 수 있는 Exception들

	 * @param e the element to add
     * @throws IllegalStateException if the element cannot be added at this
     *         time due to capacity restrictions
     * @throws ClassCastException if the class of the specified element
     *         prevents it from being added to this deque
     * @throws NullPointerException if the specified element is null and this
     *         deque does not permit null elements
     * @throws IllegalArgumentException if some property of the specified
     *         element prevents it from being added to this deque
     */

• boolean offerFirst(E e);
  
  • addFirst()와 동일하지만, 삽입 성공 여부에 따라 boolean 값을 리턴함. 용량 제한이 있는 덱에서 사용하는 것이 좋음.
• boolean offerLast(E e);
  
  • addLast()와 동일하지만, 삽입 성공 여부에 따라 boolean 값을 리턴함. 용량 제한이 있는 덱에서 사용하는 것이 좋음.
• E removeFirst();
  
  • 첫번째 원소를 덱에서 삭제한 후 리턴한다. pollFisrt와 유일한 차이점은, 덱이 비어있으면 NoSuchElementException을 발생시킴
• E removeLast();
  
  • 마지막 원소를 덱에서 삭제한 후 리턴한다. pollLast와 유일한 차이점은, 덱이 비어있으면 NoSuchElementException을 발생 시킴
• E pollFirst();
  
  • 첫번째 원소를 덱에서 삭제한 후 리턴한다. 덱이 비어있으면 null를 리턴함.
• E pollLast();
  
  • 첫번째 원소를 덱에서 삭제한 후 리턴한다. 덱이 비어있으면 null를 리턴함.
• E getFirst();
  
  • 첫번째 원소를 리턴함. 단 삭제하지 않음. 덱이 비어있으면 NosuchElementException을 발생
• E getLast();
  
  • 마지막 원소를 리턴함. 단 삭제하지 않음. 덱이 비어있으면 NosuchElementException을 발생
• E peekFirst();
  
  • 첫번째 원소를 리턴함. 단 삭제하지 않음. 덱이 비어있으면 null 리턴
• E peekLast();
  
  • 마지막 원소를 리턴함. 단 삭제하지 않음. 덱이 비어있으면 null 리턴
• boolean removeFirstOccurrence(Object o);
  
  • 덱 안의 가장 먼저 등장하는 o를 제거한다.
  • Object.equals()를 통해 동일한지 비교한다.
  • 만약 해당 object가 없는 경우, 아무일도 일어나지 않는다.
  • 만약 제거에 성공하면 true를 리턴 실패하면 false를 리턴함.
• boolean removeLastOccurrence(Object o);
  
  • 덱 안의 가장 마지막에 등장하는 o를 제거한다.
  • Object.equals()를 통해 동일한지 비교한다.
  • 만약 해당 object가 없는 경우, 아무일도 일어나지 않는다.
  • 만약 제거에 성공하면 true를 리턴 실패하면 false를 리턴함.
• void push(E e);
  
  • 스택을 위한 매서드, 삽입에 실패하면 IllegalStateExpcetion을 발생시킴

     * @param e the element to push
     * @throws IllegalStateException if the element cannot be added at this
     *         time due to capacity restrictions
     * @throws ClassCastException if the class of the specified element
     *         prevents it from being added to this deque
     * @throws NullPointerException if the specified element is null and this
     *         deque does not permit null elements
     * @throws IllegalArgumentException if some property of the specified
     *         element prevents it from being added to this deque
     */

• E pop();
  
  • 스택을 위한 메서드, 첫번째 원소를 제거하고 리턴한다.
  • removeFirst()와 동일함.
  • 만약 덱이 비어있으면 NoSuchElementException 발생
• Iterator<E> descendingIterator();
  
  • 역순으로 시퀀셜한 iterator을 리턴한다. 원소들은 tail -> head 순으로 리턴된다.

 

ArrayDeque

Deque를 구현한 리사이즈 가능한 Array이다.

capactiy제한이 없다고, 필요에 따라 늘어난다. 스레드 세이프하지 않으며, 외부의 synchronized가 없으면, 멀티스레드에서 concurrent한 접근을 지원하지 않음. 스택처럼 쓸 때 Stack클래스보다 빠르고, 큐처럼 쓸 때, LinkedList보다 빠르다.

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable

 

 

AbstractQueue

Queue를 구현하는데 뼈대를 제공한다.

public abstract class AbstractQueue<E>
    extends AbstractCollection<E>
    implements Queue<E>

 * This class provides skeletal implementations of some {@link Queue}
 * operations. The implementations in this class are appropriate when
 * the base implementation does <em>not</em> allow <tt>null</tt>
 * elements.  Methods {@link #add add}, {@link #remove remove}, and
 * {@link #element element} are based on {@link #offer offer}, {@link
 * #poll poll}, and {@link #peek peek}, respectively, but throw
 * exceptions instead of indicating failure via <tt>false</tt> or
 * <tt>null</tt> returns.

PriortyQueue

1.5 부터 제공됨. 우선순위 힙을 기반으로둔 n

내부 요소는 힙으로 구성되어 이진트리 구조로 이뤄짐.`

내부구조가 힙으로 구성되어 있기에 시간 복잡도는 O(nlogn)

null인 원소를 허용하지 않음.

non-comparable한 object를 insert하는 것을 허용하지 않음.

 

/**
 * An unbounded priority {@linkplain Queue queue} based on a priority heap.
 * The elements of the priority queue are ordered according to their
 * {@linkplain Comparable natural ordering}, or by a {@link Comparator}
 * provided at queue construction time, depending on which constructor is
 * used.  A priority queue does not permit {@code null} elements.
 * A priority queue relying on natural ordering also does not permit
 * insertion of non-comparable objects (doing so may result in
 * {@code ClassCastException}).

public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable