Queue

작성일 | In

[자료구조] Queue

큐(queue)란?

  • 데이터 입력과 출력을 다른 창구를 통해 수행하는 자료구조.
  • FIFO(First In First Out) 특징을 갖고 있다. 즉, 먼저 입력한 데이터가 먼저 출력되는 구조이다.

큐의 기능

큐의 기능은 스택의 기능과 흡사하다. 데이터를 삽입, 삭제할 수 있어야 하며, 다음으로 출력된 데이터를 확인할 수 있어야 하고, 큐에 담긴 데이터의 개수를 확인할 수 있어야 한다.

  • push()
    데이터 삽입

  • pop()
    데이터 삭제

  • front()
    다음번 삭제될 데이터 확인

  • size()
    데이터 개수 확인

  • empty()
    비어있는지 확인

큐 구현

큐도 스택과 마찬가지로 배열로 구현할 수 있다. 하지만 단순히 배열로만 구현한다면 치명적인 큐의 공간 손실이 발생한다. 큐는 데이터를 삽입하는 인덱스(rear)와 삭제하는 인덱스(front)가 다르다. 삽입 삭제가 발생하면 할수록 배열 앞쪽 인덱스는 낭비된다. 만약 rear와 front가 배열의 마지막 인덱스에 다다르게 된다면, 더 이상 해당 큐를 사용할 수 없게 된다.

따라서 큐를 배열로 구현할 땐 순환 큐(Circular Queue) 방식으로 구현하는 것이 일반적이다. front와 rear 인덱스가 배열 마지막 인덱스를 넘어서면 다시 0으로 되돌리는 방식이다. 이 방식을 통해 큐 공간의 낭비를 방지할 수 있다.

구현하기 나름이지만, 순환 큐의 포인트는 큐가 비어있는 상태와 큐가 가득 찬 상태를 front와 rear과의 상태를 통해 알아내는데에 있다.

front는 항상 빈 인덱스(첫 번째 데이터의 이전 인덱스)를 가리키고, rear는 큐의 마지막으로 삽입된 데이터의 인덱스를 가리킨다.

이러한 규칙을 세워두면, 큐가 비어있는 상태는 front == rear로 판단할 수 있고, 큐가 가득 차 있는 상태는 (rear + 1) % capacity == front로 판단할 수 있다.

비어있는 순환 큐 비어있는 큐

가득 찬 순환 큐 가득 찬 큐

즉, 순환 큐는 최대 (큐의 크기 - 1)개의 데이터를 저장할 수 있다. 따라서 필자는 사용자가 큐를 만들 때 인자로 주는 크기(n) + 1만큼의 배열 공간을 생성하여, 큐가 n개의 데이터를 저장할 수 있게끔 구현했다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
template <typename T>
class CircularQueue {
    private:
        int capacity;
        int front;
        int rear;
        T* arr;

    public:
        CircularQueue(int _capacity) {
            capacity = _capacity+1;
            front = 0;
            rear = 0;
            arr = (T*)calloc(capacity, sizeof(T));
        }

        int empty() {
            return front == rear;
        }

        int push(T data) {
            if((rear + 1) % capacity == front)
                return -1;
            else {
                rear = (rear + 1) % capacity;
                arr[rear] = data;
            }
        }

        int pop() {
            if(empty())
                return -1;
            else
                front = (front + 1) % capacity;
        }

        int size() {
            if(rear < front)
                return capacity - (front - rear);
            else
                return rear - front;
        }

        T getFront() {
            if(empty())
                return -1;
            else
                return arr[(front+1) % capacity];
        }
};
0%