큐 (1) - 선형 큐

1. Queue

큐는 스택과 반대로 들어간 순서대로 나오는 자료구조이다. 이 때문에 FIFO(First In, First Out)라고 불린다. 아래 그림을 보면 5, 7, 12, 8, 9를 먼저 순서대로 넣었다. 그리고 빼면 가장 먼저 들어간 5부터 7, 12, 8, 9 순서대로 다시 빠진다. 큐는 인간의 사고방식과 매우 비슷한데, 은행의 번호표, 매표소의 대기줄과 비슷하다.

 

[그림] Queue (큐)

 

2. Front & Rear

큐를 구현할 때 항상 빠지지 않고 나오는 Front와 Rear는 바로 앞과 뒤를 가리키는 인덱스이다. 처음에는 Front와 Rear가 모두 0 혹은 -1(빈 것을 구분하기 위해)에 존재하지만, 데이터를 넣을때, Rear가 점점 커지고, 데이터를 빼면 Front가 점점 거진다. 위 그림을 보면 Rear와 Front가 쉽게 이해할 수 있다.

 

3. Enqueue & Dequeue

스택과 다르게 큐에 어떠한 원소를 삽입할때는 Enqueue, 뺄때는 Dequeue라는 용어를 사용한다. insert, delete등의 용어를 사용해도 큰 문제는 없지만 대부분 enqueue, dequeue라는 단어를 사용한다.

 

4. Linear Queue (선형 큐)

public class ArrayLinearQueue {

    private int[] array;
    private int capacity;
    private int rear = 0;
    private int front = 0;

    public ArrayLinearQueue(int capacity) {
        this.capacity = capacity;
        this.array = new int[capacity];
    }

    public ArrayLinearQueue() {
        this.capacity = 5;
        this.array = new int[capacity];
    }

    public int size() {
        return rear - front;
    }

    public boolean isEmpty(){
        return size() == 0;
    }

    public boolean isFull(){
        return rear == capacity || size() == capacity;
    }

    public void enqueue(int data){
        if(isFull())
            throw new ArrayIndexOutOfBoundsException();

        this.array[rear] = data;
        this.rear++;
    }

    public int dequeue(){
    // Dequeue할 때, List처럼 Shift하지 않는다.
        if(isEmpty())
            throw new ArrayIndexOutOfBoundsException();

        int data = this.array[front];
        this.array[front] = 0;
        this.front++;
        return data;
    }

    public int peek(){
        return this.array[front];
    }

    @Override public String toString() {
        return Arrays.toString(array);
    }
}

 

5. Linear Queue(선형 큐)의 문제점

[그림] 선형 큐의 문제점

만약 1, 4, 7, 2, 5를 순서대로 넣고 가장 먼저 들어온 1을 뺐다고 가정해보자. 그러면 아래와 같이 rear는 인덱스 4에 위치하고 front는 인덱스 1에 위치한다. 분명히 0번 인덱스에 공간이 남았지만, 더이상 데이터를 채워넣을 수 없다. 이러한 문제를 해결하기 위해 Circular Queue (원형 큐)가 등장했다. 원형큐는 다음 글에서 설명한다. 

 

6. Reference

자료구조