큐(Queue)란?
큐는 FIFO(First In First Out, 선입선출) 구조로 동작하는 대표적인 선형 자료구조입니다. 새로운 데이터는 한쪽 끝인 후단(rear)에서 삽입되고, 삭제는 반대쪽 끝인 전단(front)에서 이루어집니다. 덕분에 가장 먼저 들어간 데이터가 가장 먼저 나오게 되며, 작업 대기열, 프린터 스풀, 메시지 처리처럼 순서가 중요한 다양한 분야에서 활용됩니다.
이번 글에서는 배열(Array)을 기반으로 큐를 직접 구현하는 C++ 프로그램을 단계별로 살펴보겠습니다.
큐의 주요 연산
- EnQueue(int data) – 후단(rear)에 새로운 요소를 삽입합니다.
- DeQueue() – 전단(front)에서 요소를 삭제합니다.
알고리즘
큐의 삽입과 삭제는 각각 다음과 같은 절차로 진행됩니다.
Enqueue(삽입)
- 큐가 가득 차 있는지 확인하고, 가득 찼다면 "Overflow"를 출력합니다.
- 그렇지 않으면 rear 위치에 요소를 삽입합니다.
- rear 값을 갱신합니다.
Dequeue(삭제)
- 큐가 비어 있는지 확인하고, 비어 있다면 "Underflow"를 출력합니다.
- 그렇지 않으면 front 위치의 요소를 삭제합니다.
- 나머지 요소들을 앞으로 이동시키고 rear 값을 갱신합니다.
C++ 구현 예제 코드
#include <bits/stdc++.h>
using namespace std;
struct Q {
int f, r, capacity;
int* q;
Q(int c) {
f = r = 0;
capacity = c;
q = new int[c];
}
~Q() { delete[] q; }
void Enqueue(int d) {
if (capacity == r) { // 큐가 가득 찼는지 확인
printf("\nQueue is full\n");
return;
} else {
q[r] = d; // 후단(rear)에 데이터 삽입
r++; // rear 값 갱신
}
return;
}
void Dequeue() {
if (f == r) { // 큐가 비었는지 확인
printf("\nQueue is empty\n");
return;
} else {
for (int i = 0; i < r - 1; i++) {
q[i] = q[i + 1]; // 요소를 한 칸씩 앞으로 이동
}
r--; // rear 값 갱신
}
return;
}
void Display() { // 큐의 내용을 출력
if (f == r) {
printf("\nQueue is Empty\n");
return;
}
for (int i = f; i < r; i++) {
printf(" %d <-- ", q[i]);
}
return;
}
void Front() { // 전단(front) 요소 확인
if (f == r) {
printf("\nQueue is Empty\n");
return;
}
printf("\nFront Element is: %d", q[f]);
return;
}
};
int main(void) {
Q qu(3);
qu.Display();
cout << "after inserting elements" << endl;
qu.Enqueue(10);
qu.Enqueue(20);
qu.Enqueue(30);
qu.Display();
qu.Dequeue();
qu.Dequeue();
printf("\n\nafter two node deletion\n\n");
qu.Display();
qu.Front();
return 0;
}
코드 설명
- 구조체 Q – front(f), rear(r), 큐의 용량(capacity), 그리고 동적 할당된 배열 포인터(q)를 멤버로 가집니다.
- 생성자 – 크기를 인자로 받아 배열을 동적 할당하고, f와 r을 0으로 초기화합니다.
- 소멸자 – delete[]로 동적 메모리를 해제하여 메모리 누수를 방지합니다.
- Enqueue() – capacity와 r이 같으면 큐가 가득 찬 상태이므로 "Queue is full"을 출력하고, 아니라면 rear 위치에 데이터를 저장한 뒤 r을 증가시킵니다.
- Dequeue() – f와 r이 같으면 큐가 비어 있는 상태이므로 "Queue is empty"를 출력하고, 아니라면 모든 요소를 한 칸씩 앞으로 이동시킨 후 r을 감소시킵니다.
- Display() – front부터 rear-1까지의 모든 요소를 순서대로 출력합니다.
- Front() – 현재 전단(front)에 있는 요소를 출력합니다.
실행 결과
Queue is Empty
10 <-- 20 <-- 30 <--
after two node deletion
30 <--
Front Element is: 30
마무리
이처럼 배열을 이용하면 큐를 간단하게 구현할 수 있습니다. 다만 위 구현은 Dequeue를 수행할 때마다 남은 요소를 앞으로 당겨야 하므로 O(n)의 시간 복잡도를 가집니다. 실무 환경에서는 요소 이동 없이 효율적으로 동작하는 환형 큐(Circular Queue)나 표준 라이브러리의 std::queue를 사용하는 것이 더 좋은 선택입니다.