[자료 구조] 큐(Queue) - 단일 연결 리스트를 이용한 Deque, Java 구현

스택과 비교해 보며 큐 자료 구조에 대해 알아봅시다. 이번 글에서는 java로 `양방향 큐(deque)`를 `이중 연결 리스트(doubly linked list)`로 구현합니다.

 

• 자료구조, 알고리즘 시리즈 모아보기

 

큐

`큐(queue)`는 이름 그대로 줄 서는 것과 같습니다.(줄 서 있는 것을 미국에서는 line이라고 하지만 영국에서는 queue라고 합니다.) 줄을 설 때를 생각해 보면 먼저 온 사람이 먼저 원하는 것을 얻습니다. 늦게 온 사람은 늦게 얻죠. 이런 구조를 `FIFO(First In First Out)`이라 합니다.

- 연산

큐 또한 스택과 마찬가지로 `추상 자료 유형(Abstract Data Type)`으로 연산(행위)으로 정의됩니다. 

• enqueue: 새로운 요소를 자료 구조에 추가
• dequeue: 자료 구조에 저장되어 있는 요소 중 가장 예전에 저장된 요소를 삭제

enqueue는 스택의 push와 같고 dequeue는 스택의 pop과 비슷합니다. 이런 비슷한 정의 때문에 큐는 스택과 같이 이야기됩니다. 하지만 이 작은 차이가 구현과 사용에 큰 차이를 가져옵니다. 추가로 양쪽 모두에서 enqueue, dequeue가 가능한 `양방향 큐`를 `double-ended queue` 줄여서 `deque`라고 합니다. 

- 사용

큐는 들어온 순서대로 처리해야 할 때 주로 사용됩니다.

• 메시지 큐
• 실시간(real-time) 시스템의 인터럽트(interrupt) 처리
• 프린터 대기 순위 등 각종 대기 순위

 

Java 구현

큐는 앞과 뒤가 있습니다. 줄을 생각해보면 당연합니다. 줄에는 줄에 들어오는 쪽이 있고 나가는 쪽이 있습니다. 우리는 줄에 들어오는 쪽을 뒤, 나가는 쪽을 앞이라고 부릅니다. 큐도 마찬가지입니다. 보통 큐에서 나가는 쪽을 front, head, start, first 등으로 부르고 큐에 들어오는 쪽을 back, tail, end, last, rear 등으로 부릅니다. 이 글에서는 front와 back으로 하겠습니다.

- 이중 연결 리스트 이용한 Deque 구현

큐는 연결 리스트(linked list)로 구현이 가능합니다.

`단일 연결 리스트(Singly linked list)`로 구현할 경우 마지막 요소를 삭제할 때 𝛩(n)의 시간 복잡도를 갖습니다. 마지막 요소를 삭제하기 위해서는 마지막 요소의 직전 요소를 알아야합니다. 마지막 요소의 직전 요소를 변수에 담아 둔다고 하더라도 마지막 요소 삭제 후 마지막 요소의 직전 요소를 업데이트할 때 𝛩(n)의 시간 복잡도를 갖습니다. 따라서 단일 연결 리스트로 큐를 구현하면 삽입은 𝛩(1), 삭제는 𝛩(n)입니다.

`이중 연결 리스트(doubly linked list)`로 큐를 구현할 경우 삽입과 삭제 모두 𝛩(1)의 시간 복잡도로 구현할 수 있습니다. 위에서 언급했던 양방향 큐(deque)역시 이중 연결 리스트로 구현이 가능합니다. Java API에서 제공되는 Queue 인터페이스와 LinkedList 클래스를 사용하면 되지만 연습을 위해 직접 클래스를 구현해 봅시다.(Java API의 LinkedList는 이중 연결 리스트입니다.)

저는 이중 연결 리스트로 양방향 큐(deque)를 구현했습니다. 단방향 큐는 메서드 쌍 중 하나만 사용하면 됩니다.(enqueueFront-dequeueBack 혹은 enqueueBack-dequeueFront)

import java.util.StringJoiner;
import java.util.Iterator;
import java.util.NoSuchElementException;

class Queue<E> implements Iterable<E> {
    class Node<E> {
        E data;
        Node<E> prev = null, next = null;
        Node(E element) {
            data = element;
        }
    }
    private Node<E> front = null, back = null;
    private int size = 0;

    // private 메서드
    private Node<E> node(int index) {
        if(index < (size>>1)) {
            Node<E> x = front;
            for(int i=0; i<index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = back;
            for(int i=size-1; i>index; i--)
                x = x.prev;
            return x;
        }
    }
    private boolean isDataIndex(int index) {
        return index >=0 && index < size;
    }

    // 기본 메서드
    public int size() { return size; }
    public void clear() { front = back = null; size = 0; }
    public boolean isEmpty() { return front == null; }

    // 추가(enqueueFront, enqueueBack)
    public void enqueueFront(E element) {
        final Node<E> newNode = new Node<>(element);
        if(isEmpty())
            back = newNode;
        else {
            Node<E> f = front;
            newNode.next = f;
            f.prev = newNode;
        }
        front = newNode;
        size++;
    }
    public void enqueueBack(E element) {
        final Node<E> newNode = new Node<>(element);
        if(isEmpty())
            front = newNode;
        else {
            Node<E> b = back;
            newNode.prev = b;
            b.next = newNode;
        }
        back = newNode;
        size++;
    }
    // 삭제(dequeueFront, dequeueBack)
    public E dequeueFront() {
        if(isEmpty())
            return null;
        Node<E> f = front;
        front = f.next;
        if(front == null)
            back = null;
        else
            front.prev = null;
        E value = f.data;
        size--;
        f.data = null;
        f.next = null; // help gc
        return value;
    }
    public E dequeueBack() {
        if(isEmpty())
            return null;
        Node<E> b = back;
        back = b.prev;
        if(back == null)
            front = null;
        else
            back.next = null;
        E value = b.data;
        size--;
        b.data = null;
        b.prev = null; // help gc
        return value;
    }

    // 검색(peekFront, peekBack, peek)
    public E peekFront() {
        if(isEmpty())
            return null;
        return front.data;
    }
    public E peekBack() {
        if(isEmpty())
            return null;
        return back.data;
    }
    public E peek(int index) {
        if(!isDataIndex(index))
            return null;
        return node(index).data;
    }

    @Override
    public String toString() {
        Node<E> x = front;
        StringJoiner joiner = new StringJoiner(",","(front) "," (back)");
        while(x != null) {
            joiner.add(x.data.toString());
            x = x.next;
        }
        return joiner.toString();
    }

    class IteratorHelper implements Iterator<E> {
        Node<E> x = front;
        public boolean hasNext(){
            return x != null;
        }
        public E next() {
            if(!hasNext())
                throw new NoSuchElementException();
            E value = x.data;
            x = x.next;
            return value;
        }
    }

    @Override
    public Iterator<E> iterator() {
        return new IteratorHelper();
    }
}