큐(Queue) / 원형큐(Circular Queue)

 

---

큐의 정의

데이터의 삽입과 삭제가 서로 다른 곳(top,rear)에서 발생하는 선형구조이다.

- 데이터 삽입 발생 위치 : rear

- 데이터 삭제 발생 위치 : front

 

가장 먼저 들어온 데이터를 front가 참조하며 데이터 삭제 시 가장 먼저 삭제된다.

이를 FIFO(First In First Out) 구조라고 한다.

 

큐의 연산

enqueue

Queue의 가장 뒤쪽(rear)에 데이터를 삽입한다.

dequeue

Queue의 가장 앞쪽(front)의 데이터를 삭제하고 반환한다.

peek

Queue의 가장 앞쪽(front)의 데이터를 반환한다.

isFull

Queue가 꽉 차있는지 확인한다.

isEmpty

Queue가 비어있는지 확인한다.

 

큐의 구현

 

큐의 구현은 스택과 마찬가지로 두 가지 방법이 있다.

배열을 통해 구현하는 방법과, 연결리스트를 이용하여 구현하는 방법이다.

배열을 이용한 큐의 구현

public class ArrayQueue {
    int rear = -1;
    int front = -1;
    Object[] queue;

    public ArrayQueue(int size) {
        queue = new Object[size];
    }

    void enqueue(Object data) {
        if(isFull()) {
            throw new IllegalStateException("Queue is full");
        }
        queue[++rear] = data;
    }

    Object dequeue() {
        if(isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        Object data = queue[++front];
        return data;
    }

    Object peek() {
        if(isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        return queue[front+1];
    }

    boolean isFull() {
        return rear >= queue.length-1;
    }

    boolean isEmpty() {
        return front == rear;
    }
}

 

isFull의 조건을 보자. rear >= queue.length-1이다. 즉, rear가 0에서 점점 증가하다가 주어진 배열의 맨 끝 인덱스까지 오면 큐가 꽉 찼다고 정의하고있다. 하지만 rear가 맨 끝 인덱스에 있다는 사실은 언제나 큐가 꽉 찼다는 사실을 의미하지는 않는다.

한 번이라도 dequeue 연산으로 데이터가 삭제된다면 배열 내에 다시 사용 가능한 공간이 존재하게 된다.

 

위 사진처럼 index 0부터 front까지의 공간이 사용가능하지만, rear가 가장 마지막 index에 도착했다는 이유만으로 큐가 꽉 찼다고 보는 경우가 생기는 것이다. 이와 같은 배열 공간의 낭비를 막기위해서는 원형큐의 개념을 적용하여 큐를 구현하면 된다.

원형큐로 구현하면 위 사진과 같은 상황에서 rear를 index 0으로 이동하여 0에 데이터를 삽입할 수 있다.

원형 큐 (Circular Queue)

큐의 마지막과 끝을 연결한 형태의 큐이다. 

나머지 연산을 이용하여 주어진 큐의 크기를 모두 사용할 수 있도록 한다.

다음과 같이 구현하였다.

public class ArrayQueue {
    int rear = -1;
    int front = -1;
    Object[] queue;

    public ArrayQueue(int size) {
        queue = new Object[size];
    }

    void enqueue(Object data) {
        if(isFull()) {
            throw new IllegalStateException("Queue is full");
        }
        rear = (rear+1) % queue.length;
        queue[rear] = data;
    }

    Object dequeue() {
        if(isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        front = (front+1) % queue.length;
        Object data = queue[front];
        return data;
    }

    Object peek() {
        if(isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        return queue[(front+1) % queue.length];
    }

    boolean isFull() {
        return (rear + 1) % queue.length == front;
    }

    boolean isEmpty() {
        return front == rear;
    }
}

 

 

연결리스트를 이용한 큐의 구현

연결리스트로 구현한 큐를 그림으로 나타내면 아래와 같다.

 

 

배열로 구현한 큐와 다른 점이 있다.

front는 맨 앞 노드(가장 먼저 들어온 노드)를 가리킨다.

- 배열로 구현한 큐는 front가 맨 앞 노드의 이전 위치를 가리키고 있었다.

 

class Node<T> {
    public Node(T data, Node<T> link) {
        this.data = data;
        this.link = link;
    }
    T data;
    Node<T> link;
}

public class ListQueue<T> {

    Node<T> front, rear;

    public ListQueue() {
        front = null;
        rear = null;
    }

    void enqueue(T data) {
        Node<T> newNode = new Node<T>(data, null);
        if (isEmpty()) {
            front = newNode;
        } else {
            rear.link = newNode;
        }
        rear = newNode;
    }

    T dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        Node<T> pastFront = front;
        T dequeueData = front.data;
        front = pastFront.link;
        pastFront.data = null;
        pastFront.link = null;
        if (front == null) {
            rear = null; // 큐가 비어있다면 rear도 null로 설정
        }
        return dequeueData;
    }

    T peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        return front.data;
    }

    boolean isEmpty() {
        return (front == null);
    }
}

* 연결리스트로 구현한 큐의 경우 메모리가 다 차지 않는한 크기 제한이 없기 때문에 isFull 메서드를 구현하지 않았다.

 

 

- 큐에 비어있을 때와 그렇지 않을 때 enqueue의 작업은 달라진다.

큐에 데이터가 처음으로 들어왔을 때를 생각해보자. front는 다음으로 삭제될 노드를, rear는 다음으로 추가될 위치의 노드를 가르키고 있어야 하므로 front와 rear 모두가 새로운 노드를 참조하여야한다.

큐가 비어있지 않을 때는, rear쪽에서의 처리만 해주면 된다.

 

- isEmpty의 조건은 front == null 이다. 이를 이해하기 위해서 큐가 비워지기 바로 전의 상황을 생각해보자.

노드가 하나 밖에 없으므로 front와 rear가 같은 노드를 가르키고 있을 것이다. 이제 dequeue의 작업이 완료되면 큐는 빈 상태가 된다. dequeue의 코드를 보면 front = pastFront.link가 수행되는 것이 보일 것이다. 가장 마지막에 삽입된 노드의 link에는 항상 null이 저장되어있으므로 front = null이 된다. 즉, 큐가 비어있는 상태에서 front는 항상 null이다. (가장 초기 상태 포함) 

 

- dequeue의 두 번째 if 문에서 front == null이라는 것은 이제 큐가 비었다는 것을 의미한다. 따라서 rear도 null로 함께 바꿔준다.