[DS] 4. 큐

큐(Queue)?

std::queue<int> q;

데이터의 입출력이 선입선출로 일어나는 자료구조.

추상 자료형

데이터 : 선입선출(FIFO, First-In First-Out)의 형태를 갖는 요소들의 모음.

연산 :

함수	설명
enqueue(x)	데이터 x를 맨 뒤에 추가.
dequeue()	맨 앞 요소를 삭제+반환. (큐가 비어있지 않으면)
peek()	맨 앞에 있는 요소를 반환. (큐가 비어있지 않으면)
isEmpty()	큐가 비어있다면 true, 아니라면 false 반환.
isFull()	큐가 가득 찼으면 true, 아니라면 false 반환.
size()	데이터들의 갯수를 반환한다.
display()	모든 데이터들을 출력한다.

---

사용법 (std::queue)

메서드

함수	설명
push(x)	맨 뒤에 데이터 x를 삽입한다.
emplace(x)	맨 뒤에 데이터 x를 삽입한다. 단, 내부에서 객체를 생성하여 할당한다.
pop()	맨 앞의 데이터를 삭제한다. 반환 타입 void.
size()	데이터들의 갯수를 반환한다.
empty()	큐가 비어있다면 true, 아니라면 false 반환.
front()	맨 앞에 있는 요소를 반환. (큐가 비어있지 않으면)
back()	맨 뒤에 있는 요소를 반환. (큐가 비어있지 않으면)
swap(q)	인자로 큐 q를 받아, 서로가 가리키는 주소 정보(포인터)를 서로 맞바꾼다.

std::stack과 마찬가지로, emplace는 push와 다르게, 인자를 받아 직접 내부에서 객체 생성 후 할당한다. 때문에, 상수를 인자로 받게 되면 불필요한 복사/이동 연산의 과정이 생략되어 오버헤드가 적다.

다만 내부적으로 생성자에 직접 인자를 전달하기에, explicit 키워드가 걸려있어도 생성자를 정상적으로 호출한다. 이로 인해 의도치 않은 타입 생성이 일어날 수 있기에 사용에 주의가 필요하다.

예제 코드

Queue

#include <iostream>
#include <queue>

int main()
{
  std::queue<int> q;

  q.push(10);                      // 데이터 삽입
  q.push(20);
  q.push(30);

  while (!q.empty())               // 데이터 추출(삭제)
  {
    std::cout << q.front() << " "; // 출력
    q.pop();                       // 삭제
  }

  return 0;
}

10 20 30

---

구현

선형 큐 예제 코드 (고정 배열 기반)

코드를 보면 알겠으나, 이는 일단 구현을 했다 정도이지 실제로 쓰기는 어렵다.

이유는 삽입/반출을 계속할 시 데이터가 뒤로 점차 밀리게 되고, 어느 순간 맨 끝에 다다랐다면 맨 앞으로 전부 옮겨주어야 하는데, 이 데이터를 일일히 옮기는 시프트 작업이 상당히 비효율적이기 때문이다.

이 문제점을 보완한 방법으로 아래의 원형 큐가 존재한다.

#include <iostream>
constexpr int MAX_QUEUE_SIZE = 5; // 최대 데이터 수

template <typename T>
class LinearQueue
{
protected:
  int frontIndex;                 // 맨 앞 데이터의 index 값
  int rearIndex;                  // 맨 뒤 데이터의 index 값
  T data[MAX_QUEUE_SIZE];         // 저장할 배열

public:
  LinearQueue() : frontIndex(0), rearIndex(-1) {}  // 생성자
  ~LinearQueue() {}                                // 소멸자
  bool isEmpty() { return frontIndex > rearIndex; }
  bool isFull()  { return size() == MAX_QUEUE_SIZE; }
  int size()     { return (rearIndex - frontIndex + 1); }

  void enqueue(T x) 
  { // (가득 차지 않았다면) 데이터를 맨 뒤에 넣는다.
    if (isFull()) { std::cout << "Queue is Full" << std::endl; return; }
    if (rearIndex == MAX_QUEUE_SIZE - 1)
    { // 만약 방금 삽입한 데이터가 맨 끝에 다다랐다면, 한칸씩 앞으로 옮긴다.
      int currentSize = size();
      for (int i = 0; i < currentSize; ++i)
        data[i] = data[frontIndex + i];
      frontIndex = 0;
      rearIndex = currentSize - 1;
    }
    data[++rearIndex] = x;
  }

  T dequeue() 
  { // (비어있지 않다면) 맨 앞의 데이터를 삭제+반환한다. 정확히는 삭제가 아닌 없는취급.
    if (isEmpty()) { std::cout << "Queue is Empty" << std::endl; return T(); }
    return data[frontIndex++];
  }

  T peek()
  { // (비어있지 않다면) 맨 앞의 데이터를 반환한다.
    if (isEmpty()) { std::cout << "Queue is Empty" << std::endl; return T(); }
    return data[frontIndex];
  }

  void display() {
    for (int i = frontIndex; i <= rearIndex; ++i) {
      std::cout << data[i] << " ";
    }
    std::cout << "\n";
  }
};

int main()
{
  LinearQueue<int> q;
  
  q.enqueue(10);
  q.enqueue(20);
  q.enqueue(30);
  std::cout << q.dequeue() << " "; // 10
  q.enqueue(40);
  std::cout << q.dequeue() << " "; // 20
  q.enqueue(50);
  q.enqueue(60);                   // shift 후 삽입
  
  while (!q.isEmpty())
    std::cout << q.dequeue() << " ";
}

10 20 30 40 50 60

Linear Queue

원형 큐 예제 코드 (고정 배열 기반)

위의 선형 큐에서의 시프트 연산을 할 필요가 없도록 고친 구조이다. 고정 배열의 맨 뒤와 맨 앞을 실제로 이은 것 처럼 동작하도록 제작되었기에, 원형 큐라고 불린다. (도넛 모양과 유사하므로)

포화 상태와 공백 상태를 구별할 수 있어야 하므로, 0번째 index는 의도적으로 비워둔다. (frontIndex와 rearIndex를 통해 상태를 구분하는데, 모든 칸에 데이터를 채우게 된다면 포화 상태와 공백 상태 모두 frontIndex == rearIndex == 0 이 된다.)

이 때문에 결과적으로 사용 가능한 공간은 MAX_QUEUE_SIZE - 1이 된다.

#include <iostream>
constexpr int MAX_QUEUE_SIZE = 5; // 최대 데이터 수

template <typename T>
class CircularQueue
{
protected:
  int frontIndex;                 // 맨 앞 데이터의 index 값
  int rearIndex;                  // 맨 뒤 데이터의 index 값
  T data[MAX_QUEUE_SIZE];         // 저장할 배열
  
public:
  CircularQueue() : frontIndex(0), rearIndex(0) {} // 생성자
  ~CircularQueue() {}                              // 소멸자
  bool isEmpty()   { return frontIndex == rearIndex;  }
  bool isFull()    { return (rearIndex + 1) % MAX_QUEUE_SIZE == frontIndex;  }
  int size()       { return (rearIndex - frontIndex + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE; }
  
  void enqueue(T inputData)
  { // (가득 차지 않았다면) 데이터를 맨 뒤에 넣는다.
    if (isFull()) { std::cout << "Queue is Full!" << std::endl; return;}
    rearIndex = (rearIndex + 1) % MAX_QUEUE_SIZE;
    data[rearIndex] = inputData;
  }

  T dequeue()
  { // (비어있지 않다면) 맨 앞의 데이터를 삭제+반환한다. 정확히는 삭제가 아닌 없는취급.
    if (isEmpty()) { std::cout << "Queue is Empty!" << std::endl; return T(); }
    frontIndex = (frontIndex + 1) % MAX_QUEUE_SIZE;
    return data[frontIndex];
  }

  T peek()
  { // (비어있지 않다면) 맨 앞의 데이터를 반환한다.
    if (isEmpty()) { std::cout << "Queue is Empty!" << std::endl; return T(); }
    return data[(frontIndex + 1) % MAX_QUEUE_SIZE];
  }

  void display()
  { // 모든 데이터를 출력한다.
    std::cout << "Data : ";
    int i = frontIndex;
    while (i != rearIndex) {
      i = (i + 1) % Capacity;
      std::cout << data[i] << " ";
    }
    std::cout << std::endl;
  }
};

int main()
{
  CircularQueue<int> q;

  q.enqueue(10);
  q.enqueue(20);
  q.enqueue(30);
  q.enqueue(40);

  std::cout << q.dequeue() << " "; // 10

  q.enqueue(50); // rearIndex: 4 -> 0

  while (!q.isEmpty())
    std::cout << q.dequeue() << " ";

  return 0;
}

10 20 30 40 50

Circular Queue

큐 예제 코드 (연결 리스트 기반)

포인터의 선행학습 이후 보기를 권장한다.

고정 배열과 달리 연결 리스트 기반이기에 고정된 갯수 제한이 없다.

#include <iostream>

template <typename T>
class LinkedQueue
{
private:
  struct Node
  { // 노드 구조체.
    Node(T val) : data(val), next(nullptr) {}
    T data;        // 데이터
    Node* next;    // 다음 노드의 주소
  };

  Node* frontNode; // 맨 앞 노드를 가리키는 주소값.
  Node* rearNode;  // 맨 뒤 노드를 가리키는 주소값.
  int count;       // 현재 데이터의 갯수.

public:
  LinkedQueue()  { frontNode = rearNode = nullptr; count = 0; } // 생성자
  ~LinkedQueue() { while (!isEmpty()) dequeue(); }              // 소멸자

  bool isEmpty() { return frontNode == nullptr; }
  int size()     { return count; }

  void enqueue(T inputData)
  { // 받아온 데이터로 새 노드를 만들고, 이를 맨 뒤 노드로 갱신한다.
    Node* newNode = new Node(inputData);
    if (isEmpty()) { frontNode = rearNode = newNode; }
    else {
      rearNode->next = newNode;
      rearNode = newNode;
    }
    count++;
  }

  T dequeue() 
  { // (비어있지 않다면) 맨 앞의 데이터를 삭제+반환한다.
    if (isEmpty()) { std::cout << "Queue is Empty!" << std::endl; return T(); }
    
    Node* temp = frontNode;      // 삭제 이전에 맨 앞 노드 저장
    T returnData = temp->data;   // 삭제 이전에 원본 데이터 깊은 복사
    frontNode = frontNode->next; // 맨 앞 노드 갱신
    if (!frontNode)              // 예외처리 
      rearNode = nullptr;        // └─ (맨 앞 노드가 nullptr이라면 비었을 것이므로, 맨 뒤 노드도 초기화)
    delete temp;                 // 삭제
    count--;                     // 갯수 갱신
    
    return returnData;
  }

  T peek()
  { // (비어있지 않다면) 맨 앞의 데이터를 반환한다.
    if (isEmpty()) { std::cout << "Queue is Empty!" << std::endl; return T(); }
    return frontNode->data;
  }

  void display()
  { // 모든 데이터를 출력한다.
    std::cout << "Data : ";
    Node* current = frontNode;
    while (current != nullptr) {
      std::cout << current->data << " ";
      current = current->next;
    }
    std::cout << std::endl;
  }
};

int main() {
  LinkedQueue<int> q;

  q.enqueue(10);
  q.enqueue(20);
  q.enqueue(30);

  std::cout << "Data : ";
  while (!q.isEmpty())
    std::cout << q.dequeue() << " ";
  std::cout << std::endl;
}

Data : 10 20 30

Linked-List Queue Enqueue

Linked-List Queue Dequeue

---

특징

삽입/반출의 시간복잡도가 $O(1)$으로 상당히 빠르다. 이 역시 당연하게도, 삽입의 기준점(맨 뒤의 노드)과 반출의 기준점(맨 앞의 노드)을 항상 알고 있기 때문이다.

표준 라이브러리의 std::queue는 내부적으로 deque를 사용해 구현된다. 이는 앞에서 다룬 std::stack도 마찬가지.

deque는 stack과 queue의 특성을 동시에 가지는 자료구조이며, std::deque 기준으로 내부적으로 일반 배열의 데이터로 이루어진, 청크 단위의 노드를, 중앙 포인터 배열로 관리하는 형태로 구현되어있다. 이로 인해 메모리를 조금 더 쓰는 대신, 캐시 효율성을 얻는다. 자세한 것은 이후에 다룬다.

사용례

• 프로그램들의 작업 순서 버퍼 처리(스케쥴링)
• 너비 우선 탐색 알고리즘 (BFS, Breadth-First Search)
• 게임/페이지 등에서의 대기열 처리
• 네트워크 요청 처리