Queue ADT 정의, Java 구현

일단 Queue ADT부터 정의해보자.

https://en.wikipedia.org/wiki/Queue_(abstract_data_type)

Queue는 선형 자료구조 일종으로 FIFO 구조로 작동하고, 양 쪽 끝에서 각각 삽입, 삭제가 이루어진다.
따라서 삽입을 위한 enqueue(data) - O(1), 삭제를 위한 deque() - O(1) 연산이 있다.
이를 이용하여 bfs탐색, 혹은 대기열 버퍼, 캐싱 등을 할 때 사용할 수 있다.

Queue를 응용한 Deque 구조가 있는데 양쪽에서 삽입,삭제가 모두 일어난다. C++에는 std::deque, Java에서는 Deque 인터페이스를 상속한 ArrayDeque 클래스가 있다.

Stack과 마찬가지로 데이터를 저장하는 부분을 배열 혹은 링크드리스트로 구현을 할 수 있고, 이에 따라 resize 연산을 추가로 구현해야한다. 여기서는 단방향 링크드리스트로 구현하였다.

1. Queue와 Node에 필요한 필드를 정의한다.

public class Queue {
    Node front, rear;

    private class Node {
        Object data;
        Node next;
    }

    Node(Object data) {
        this.data = data;
        this.next = null;
    }
}

2. 삽입, 삭제 연산을 정의한다.

void enque(Object data) {
    Node newNode = new Node(data);
    if(this.rear == null) {
        this.front = this.rear = newNode;
        return;
    }

    this.rear.next = newNode;
    this.rear = newNode;
}

void dequeue() {
    if(this.front == null) return;

    this.front = this.front.next;

    if(this.front == null) {
        this.rear = null;
    }
}

public class Queue {
    Node front, rear;

    private class Node {
        Object data;
        Node next;

        Node(Object data) {
            this.data = data;
            this.next = null;
        }
    }

    public Queue() {
        this.front = this.rear = null;
    }

    void enqueue(Object data) {
        Node newNode = new Node(data);
        if(this.rear == null) {
            this.front = this.rear = newNode;
            return;
        }

        this.rear.next = newNode;
        this.rear = newNode;
    }

    void dequeue() {
        if(this.front == null) return;

        this.front = this.front.next;

        if(this.front == null) {
            this.rear = null;
        }
    }
}