[자료구조] 4. 큐(Queue)

큐

스택이 LIFO(Last In First Out)의 구조라면 큐는 FIFO(First In First Out), 즉 선입선출의 구조라고 할 수 있습니다.

큐에는 앞(front)과 뒤(rear)가 존재하는데, 이때 데이터 삽입시에 뒤에 enqueue 되고, 데이터를 꺼낼 시에는 앞에서 dequeue 됩니다.

활용

이러한 큐의 개념은 여러곳에서 사용됩니다. 대용량의 트래픽을 처리할 때 큐를 응용한 Kafka나 RabbitMQ 등을 사용하는데, 작업들을 큐에 쌓아놓고 Consumer가 큐에서 작업을 꺼내서 차례대로 처리하는 방식입니다.

큐는 프로세스의 round robin scheduler에도 사용되는데, dequeue한것을 다시 enqueue를 반복하는 방식으로 계속 순환이 가능합니다.

또한 트리에서 노드를 레벨 단위로 방문하는 BFS에서도 큐를 사용합니다.

ADT

int getSize()
bool isEmpty()

큐는 핵심은 삽입의 enqueue, 추출하는 dequeue 그리고 원소를 추출하지는 않고 dequeue될 원소를 확인할 수 있는 front가 있습니다.

// typename T
void enqueue(T& element)
T& dequeue()
T& front()

구현

큐의 구현은 연결 리스트와 배열등으로 가능합니다. 이때 배열을 이용 시에는 배열을 순환하는 특이한 방식을 사용하게 되는데, 그 내용은 방법은 아래와 같습니다.

위의 화살표와 같이 front와 rear의 index를 저장하는 frontIndex, rearIndex 두 가지의 변수를 둡니다. 또한 dequeue시에 frontIndex와 rearIndex의 밖으로 벗어난 원소를 따로 초기화해주지는 않습니다.

앞서 말했듯 배열을 순환하는 방식으로 사용되기에 계속해서 enqueue와 dequeue가 반복된다면 배열을 돌게 됩니다.

위는 rearindex가 한바퀴 순환한 상태인데, 이렇게 순환하여 frontIndex가 3, rearIndex가 0가 되었다면 큐의 범위는 3~7 + 0~0 가 되는것입니다.

C++에서 배열로 큐는 다음과 같이 구현할 수 있습니다.

class ArrayQueue {
  private:
    int *arr;
    int capacity;
    int frontIndex;
    int rearIndex;
    int size;

  public:
    ArrayQueue(int capacity) : capacity{capacity} {
        arr = new int[capacity];
        frontIndex = rearIndex = 0;
        size = 0;
    }
    ~ArrayQueue() { delete[] arr; }
    bool isEmpty() { return (size == 0); }
    bool isFull() { return (size == capacity); }
    int getSize() { return size; }
    int getFront() { return isEmpty() ? -1 : arr[frontIndex]; }
    int getRear() {
        return isEmpty() ? -1 : arr[(rearIndex - 1 + capacity) % capacity];
    }
    void enqueue(int data) {
        if (capacity == getSize())
            return;
        arr[rearIndex] = data;
        rearIndex = (rearIndex + 1) % capacity;
        size++;
    }
    int dequeue() {
        if (isEmpty())
            return -1;
        int ret = arr[frontIndex];
        frontIndex = (frontIndex + 1) % capacity;
        size--;
        return ret;
    }
};

보면 지속적으로 capacity로 나누어 주어 순환이 가능하게 하고 있는데 이를 modular 연산이라 합니다. 추가적으로 위의 코드와 같이 고정사이즈의 배열을 쓰기보다 Vector을 이용해서 2배씩 사이즈를 늘인다면 더욱 편하게 사용할 수 있습니다.

 

큐는 스택과 같이 연결리스트로도 만들 수 있는데, 연결리스트는 같은 시간복잡도를 가지긴 하나, 배열에 비해 다소 속도면에서 비효율이 발생할 수 있어 배열을 순환하는 방식으로 사용합니다.

효율

큐의 enqueue, dequeue 시간복잡도는 O(1), 공간 복잡도는 원소의 개수와 비례하는 O(n)입니다.