[자료구조] 큐(Queue)

큐

• 데이터가 들어오는 위치가 가장 뒤에 있고, 데이터가 나가는 위치가 가장 앞에 있는 자료구조
• 먼저 들어온 데이터가 가장 먼저 삭제되는 선입선출(First In First Out, FIFO) 자료구조
• 어떠한 작업 / 데이터를 순서대로 실행/사용하기 위해서 대기시킬 때 사용
• 큐 응용
  • Queue, PriorityQueue, Deque

코드 설계

• Queue의 인터페이스의 추상 메서드 확인
• LinkedList에서 구현 코드 확인

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

  boolean offer(E paramE);

  E remove();

  E poll();

  E element(); // 해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환

  E peek(); // 해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환
}

코드 구현

• Queue 인터페이스의 핵심 메서드를 LinkedList에서 확인

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, Serializable {
    transient int size = 0;
    transient Node<E> first;
    transient Node<E> last; 
    private static final long serialVersionUID = 876323262645176354L;
    public LinkedList() {}

    // 새로운 Node를 만들어 기존의 Queue의 마지막 node의 next에 연결, Queue의 size + 1
    public boolean add(E paramE) {
        linkLast(paramE);
        return true;
    }
    // add와 같은 기능을 함
    public boolean offer(E paramE) { 
        return add(paramE); 
    }

    // Queue의 index확인 후에 link가 연결된 부분을 null을 대입하여 link 연결을 해제
    public E remove(int paramInt) {
        checkElementIndex(paramInt);
        return unlink(node(paramInt));
    }

    // Queue의 first값을 확인 후 link를 제거한 뒤에 해당 Node를 반환
    public E poll() {
        Node<E> node = this.first;
        return (node == null) ? null : unlinkFirst(node);
    }

    // Queue의 first값을 확인하여 값을 조회
    public E element() { 
        return getFirst(); 
    }

    // Queue의 first값을 확인하여 값을 조회
    public E peek() {
        Node<E> node = this.first;
        return (node == null) ? null : node.item;
    }

    public E getFirst() {
        Node<E> node = this.first;
        if (node == null)
            throw new NoSuchElementException(); 
        return node.item;
    }

    void linkLast(E paramE) {
        Node<E> node1 = this.last;
        Node<E> node2 = new Node<>(node1, paramE, null);
        this.last = node2;
        if (node1 == null) {
            this.first = node2;
        } else {
            node1.next = node2;
        } 
        this.size++;
        this.modCount++;
    }

    E unlink(Node<E> paramNode) {
        E e = paramNode.item;
        Node<E> node1 = paramNode.next;
        Node<E> node2 = paramNode.prev;
        if (node2 == null) {
            this.first = node1;
        } else {
            node2.next = node1;
            paramNode.prev = null;
        } 
        if (node1 == null) {
            this.last = node2;
        } else {
            node1.prev = node2;
            paramNode.next = null;
        } 
        paramNode.item = null;
        this.size--;
        this.modCount++;
        return e;
    }

    private E unlinkFirst(Node<E> paramNode) {
        E e = paramNode.item;
        Node<E> node = paramNode.next;
        paramNode.item = null;
        paramNode.next = null;
        this.first = node;
        if (node == null) {
            this.last = null;
        } else {
            node.prev = null;
        } 
        this.size--;
        this.modCount++;
        return e;
    }

    private void checkElementIndex(int paramInt) {
        if (!isElementIndex(paramInt))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(paramInt)); 
    }
    ...
}