큐(Queue)

개념

큐는 선입선출(FIFO: First In First Out) 원칙을 따르는 선형 자료구조이다. 이는 가장먼저 삽입된 요소가 가장 먼저 제거된다는 의미이다.
일상생활에서 줄을 서는 것과 같은 원리로, 가장 먼저 줄을 선 사람이 가장 먼저 서비스를 받고 나가게 된다.

활용 예시

1. 프로세스 스케줄링
2. 너비 우선 탐색(BFS)
3. 데이터 버퍼링
4. 프린터 대기열
5. 메시지 큐

구현(원형 큐)

class Queue {
private:
  int* arr; // 큐를 저장할 배열
  int capacity; // 큐의 최대 크기
  int front; // 전단 인덱스
  int rear; // 후단 인덱스
  int count; // 현재 큐에 있는 요소의 수

public:
  // 생성자
  Queue(int size) {
    arr = new int[size];
    capacity = size;
    front = 0;
    rear = -1;
    count = 0;
  }

  // 소멸자
  ~Queue() {
    delete[] arr;
  }

  // 큐에 요소를 삽입
  void enqueue(int x) {
    if (isFull()) {
      cout << "큐 오버플로우! 데이터를 추가할 수 없습니다." << endl;
      return;
    }

    rear = (rear + 1) % capacity;
    arr[rear] = x;
    count++;
  }

  // 큐에서 요소 제거 및 반환
  int dequeue() {
    if (isEmpty()) {
      cout << "큐 언더플로우! 데이터가 없습니다." << endl;
      return -1;
    }

    int x = arr[front];
    front = (front + 1) % capacity;
    cout--;

    return x;
  }

  // 큐의 전단 요소를 반환
  int peek() {
    if (isEmpty()) {
      cout << "큐 언더플로우! 데이터가 없습니다." << endl;
      return -1;
    }

    return arr[front];
  }

  // 큐의 크기를 반환
  int size() {
    return count;
  }

  // 큐가 비어있는지 확인
  bool isEmpty() {
    return (size() == 0);
  }

  // 큐가 가득 찼는지 확인
  bool isFull() {
    return (size() == capacity);
  }
};

C++ 표준 라이브러리 큐(STL queue)

#include <iostream>
#include <queue>
using namespace std;

int main() {
  // queue 객체 생성
  queue<int> q;

  // 요소 삽입 (인큐)
  q.push(10);
  q.push(20);
  q.push(30);

  cout << "큐의 크기: " << q.size() << endl;
  cout << "큐의 전단 요소: " << q.front() << endl;
  cout << "큐의 후단 요소: " << q.back() << endl;

  // 요소 제거(디큐)
  cout << "\n요소 제거 시작:" << endl;
  while (!q.empty()) {
    cout << "제거된 요소: " << q.front() << endl;
    q.pop();
  }

  return 0;
}

시간 복잡도

연산	배열 기반(일반)	배열 기반(순환)	연결 리스트 기반
enqueue	O(1)	O(1)	O(1)
dequeue	O(n)	O(1)	O(1)
peek	O(1)	O(1)	O(1)
size	O(1)	O(1)	O(1)
isEmpty	O(1)	O(1)	O(1)
isFull	O(1)	O(1)	O(1)

변형 큐

우선순위 큐(Priority Queue)

요소들이 우선순위에 따라 제거되는 큐이다.

#include <iostream>
#include <queue>
using namespace std;

int main() {
  // 기본은 최대 힙(max heap)으로 구현됨
  priority_queue<int> pq;

  pq.push(30);
  pq.push(10);
  pq.push(20);

  cout << "우선순위 큐 요소 제거:" << endl;
  while (!pq.empty()) {
    cout << pq.top() << " "; // 가장 높은 우선순위(큰 값) 출력
    pq.pop();
  }

  return 0;
}

덱(Deque, Double-ended Queue)

양쪽 끝에서 삽입과 삭제가 모두 가능한 큐이다.

#include <iostream>
#include <deque>
using namespace std;

int main() {
  deque<int> dq;

  // 앞쪽에 요소 추가
  dq.push_front(10);

  // 뒤쪽에 요소 추가
  dq.push_back(20);

  // 앞쪽에 요소 추가
  dq.push_front(5);

  // 덱의 모든 요소 출력
  cout << "덱의 요소: ";
  for (int x: dq) {
    cout << x << " ";
  }

  return 0;
}