Queue

Queue는 FIFO(First In First Out), 선입 선출 방식으로 항목을 저장하는 데이터 구조이다.

명품 매장에 명품을 사러 사람들이 줄을 서 있다. 새로운 사람이 온다면 대기열 중간에 합류할 수 없고 끝에서부터 서서 기다려야 할 것이다. 그리고 구매를 마친 사람들이 매장을 나가게 되면 대기열의 첫 줄의 사람이 매장 안으로 들어간다.

이는 queue 구조와 매우 유사하다.

queue

따라서 큐에 요소를 삽입할 때마다 해당 요소는 큐의 끝에 삽입된다.

큐의 구현

1. Array

• Linear Queue

선형 큐는 1차원 배열을 사용하여 순차 자료구조 방식으로 큐를 구현한다.

public class LinearArrayQueue {
    int[] arr;
    int topOfQueue;         // end : 대기열 상단 -1로 초기화
    int beginningOfQueue;   // front : 대기열 시작 -1로 초기화

    public LinearArrayQueue(int size) {
        this.arr = new int[size];
        this.topOfQueue = -1;
        this.beginningOfQueue = -1;
    }

    public boolean isFull() {
        return topOfQueue == arr.length - 1;
    }

    public boolean isEmpty() {
        return beginningOfQueue == -1 || beginningOfQueue == arr.length;
    }

    // 삽입
    public void enQueue(int value) {
        if (isFull()) {
            System.out.println("Queue is Full");
        }
        // 비어있다면 시작은 0으로 초기화
        else if (isEmpty()) {
            this.beginningOfQueue = 0;
            this.arr[++topOfQueue] = value;
        } else {
            this.arr[++topOfQueue] = value;
        }
    }

    // 삭제
    public int deQueue() {
        if (isEmpty()) {
            return -1;
        }
        int result = arr[beginningOfQueue++];
        if (beginningOfQueue > topOfQueue) {
            beginningOfQueue = topOfQueue = -1;
        }
        return result;
    }

    public int peek() {
        if (isEmpty()) {
            return -1;
        }
        return this.arr[beginningOfQueue];
    }

    public void deleteQueue() {
        this.arr = null;
    }
}

• Circular Queue

선형 큐에서 deQueue() 연산을 수행하게 되면 제거된 요소의 index는 빈 공간이되고 활용되지 않는다. 다시 활용하려면 매번 삭제하면서 뒤에 있는 요소를 한칸씩 이동시켜야 한다. N개의 요소가 있으면 O(N)만큼의 시간 복잡도가 발생하고 이는 성능상 매우 비효율적이다.

원형 큐는 선형과 다르게 Queue의 끝에 도착하면 시작 지점으로 다시 돌아간다. 원형 큐는 배열의 처음과 끝이 연결되어 있다는 것을 가정한다. 초기 공백 상태의 front와 end는 0이다. 또, 원형 큐에서 포화 상태는 front와 end 사이에 빈 공간이 존재하므로 front와 end의 값을 증가시킬 때 배열의 크기에 대해 나머지 연산자를 사용해 빈 공간을 구현하는 것이다.

선형 큐에서는 size를 5로 할당하면 5개의 공간을 사용하지만 원형 큐에서는 하나의 빈 공간을 만든다. 즉, size를 5로 할당해도 4개의 공간만 사용한다는 것이다.

public class CircularQueue {
    int[] arr;
    int topOfQueue;         // end
    int beginningOfQueue;   // front
    int size;

    public CircularQueue(int size) {
        this.arr = new int[size];
        this.topOfQueue = -1;
        this.beginningOfQueue = -1;
        this.size = size;
    }

    public boolean isEmpty() {
        return topOfQueue == -1; // topOfQueue == beginningOfQueue
    }

    public boolean isFull() {
        // (end + 1) % size == beginningOfQueue
        if (topOfQueue + 1 == beginningOfQueue) return true;
        return beginningOfQueue == 0 && topOfQueue + 1 == size;
    }

    // size = 5일 경우, 4개의 item을 삽입하고 1개를 제거하면 beginning = 1이되고, top = (size - 1)이 된다.
    // 여기서 데이터를 삽입하려고 하면 topOfQueue의 index는 0으로 돌아간다. -> 마지막 공간을 사용하지 않는다.
    public void enQueue(int value) {
        if (isFull()) {
            System.out.println("CQ is Full");
        } else if (isEmpty()) {
            this.beginningOfQueue = 0;
            this.topOfQueue++;
            this.arr[topOfQueue] = value;
        } else {
            if (topOfQueue + 1 == size) {
                this.topOfQueue = 0;
            } else {
                this.topOfQueue++;
            }
            this.arr[topOfQueue] = value;
        }
    }

    public int deQueue() {
        if (isEmpty()) {
            return -1;
        } else {
            int result = arr[beginningOfQueue];
            arr[beginningOfQueue] = 0;      // 삭제 의미를 0으로 표현한다.

            // 큐가 비어있다는 의미이다.
            if (beginningOfQueue == topOfQueue) {
                beginningOfQueue = topOfQueue = -1;
                return result;
            }

            if (beginningOfQueue + 1 == size) {
                beginningOfQueue = 0;
                return result;
            }

            beginningOfQueue++;
            return result;
        }
    }

    public int peek() {
        if (isEmpty()) {
            System.out.println("CQ is Empty");
            return -1;
        }
        return this.arr[beginningOfQueue];
    }

    public void deleteQueue() {
        this.arr = null;
    }
}

시간 복잡도 : O(1)

1. LinkedList

public class LinkedListQueue {
    LinkedList list;

    public LinkedListQueue() {
        this.list = new LinkedList();
    }

    public boolean isEmpty() {
        return list.getHead() == null;
    }

    public void enQueue(int value) {
        list.add(list.size(), value);
    }

    public int deQueue() {
        int value = -1;
        if (isEmpty()) return value;
        value = list.getHead().data;
        list.remove(0);
        return value;
    }

    public int peek() {
        if (isEmpty()) return -1;
        return list.getHead().data;
    }

    public void deleteQueue() {
        list.getHead() == null;
        list.getTail() == null;
    }
}

시간 복잡도 : O(1)