큐(Queue)는 FIFO(First In First Out, 선입선출) 방식으로 동작하는 선형 자료구조입니다. 즉, 가장 먼저 들어온 데이터가 가장 먼저 나가는 순서를 항상 유지합니다.
배열(Array)은 동일한 데이터 타입의 요소들을 연속된 메모리 공간에 저장하는 자료구조입니다.
큐에서는 삽입(insertion)과 삭제(deletion) 연산이 큐의 양쪽 끝에서 서로 반대 방향으로 수행되기 때문에, 스택에 비해 구현이 다소 복잡합니다.
배열 기반 큐의 기본 원리
큐를 배열로 구현할 때는 크기가 n인 배열 queue를 생성하고, top과 end라는 두 개의 변수를 사용합니다.
처음에는 배열이 비어 있으므로 top과 end는 모두 인덱스 0을 가리킵니다. 큐에 요소가 추가될 때(삽입)마다 end 변수의 값이 1씩 증가하며, end 값은 배열의 최대 길이인 n까지 커질 수 있습니다.
반대로 큐에서 요소를 제거할 때(삭제)에는 top 변수의 값이 증가하며, top은 end 값까지만 증가할 수 있습니다.
큐 연산의 종류와 구현 방법
1. Enqueue (요소 추가)
Enqueue는 큐에 새로운 요소를 추가하는 연산입니다. 요소를 추가하기 전에 큐가 가득 찼는지 먼저 확인해야 합니다. end 값이 n보다 작다면 queue[end] 위치에 요소를 저장하고 end를 1 증가시킵니다.
오버플로우(Overflow) 조건은 배열이 가득 찬 경우, 즉 end == n일 때 발생합니다.
2. Dequeue (요소 삭제)
Dequeue는 큐에서 요소를 삭제하는 연산입니다. 삭제 전에 큐가 비어 있는지 확인해야 하며, 이때 top과 end의 값을 비교합니다. top == end이면 배열이 비어 있는 상태입니다.
요소가 존재한다면, 배열의 모든 요소를 왼쪽으로 한 칸씩 이동시켜 가장 앞의 요소를 제거합니다.
3. Front (첫 번째 요소 확인)
Front는 큐의 첫 번째 요소, 즉 queue[top]을 확인하는 연산입니다. 이 연산은 배열이 비어 있지 않을 때만 수행할 수 있습니다.
4. Display (전체 출력)
Display는 큐에 저장된 모든 요소를 순회하면서 화면에 출력하는 연산입니다.
알고리즘
ENQUEUE : Step 1 : if (end == n), print : "OVERFLOW". Exit // 오버플로우 발생 시 종료 Step 2 : queue[end] = data; end++ // 요소 저장 후 end 증가 DEQUEUE : Step 1 : if (top == end), print : "Empty Queue". Exit // 큐가 비었으면 종료 Step 2 : shift all elements one position left; End--; // 요소를 한 칸씩 왼쪽으로 이동
C++ 구현 예제
아래는 앞서 설명한 내용을 바탕으로 작성한 C++ 코드입니다. 구조체(struct)로 큐를 정의하고, Enqueue, Dequeue, Display, Front 연산을 모두 포함했습니다.
#include <bits/stdc++.h>
using namespace std;
struct Queue {
int top, end, n;
int* queue;
Queue(int c){
top = end = 0;
n = c;
queue = new int[n];
}
~Queue() { delete[] queue;
}
void Enqueue(int data){
if (n == end) {
printf("\nQueue is full\n");
return;
}
else {
queue[end] = data;
end++;
}
return;
}
void Dequeue(){
if (top == end) {
printf("\nQueue is empty\n");
return;
}
else {
for (int i = 0; i < end - 1; i++) {
queue[i] = queue[i + 1];
}
end--;
}
return;
}
void Display(){
int i;
if (top == end) {
printf("\nQueue is Empty\n");
return;
}
for (i = top; i < end; i++) {
printf(" %d <-- ", queue[i]);
}
return;
}
void Front(){
if (top == end) {
printf("\nQueue is Empty\n");
return;
}
printf("\nFront Element is: %d", queue[top]);
return;
}
};
int main(void){
Queue q(4);
q.Display();
q.Enqueue(12);
q.Enqueue(89);
q.Enqueue(65);
q.Enqueue(34);
q.Display();
q.Enqueue(92);
q.Display();
q.Dequeue();
q.Dequeue();
q.Display();
q.Front();
return 0;
}실행 결과
Queue is Empty 12 <-- 89 <-- 65 <-- 34 <-- Queue is full 12 <-- 89 <-- 65 <-- 34 <-- Front Element is: 65
위 결과를 단계별로 살펴보면 다음과 같습니다. 처음에는 큐가 비어 있어 "Queue is Empty"가 출력됩니다. 이후 12, 89, 65, 34 네 개의 요소를 삽입하면 순서대로 정상적으로 표시됩니다. 큐의 최대 용량이 4이므로 다섯 번째 삽입 시도(92)에서는 "Queue is full" 오버플로우 메시지가 출력됩니다. 두 번의 Dequeue 이후에는 앞쪽 두 요소가 제거되고, 마지막으로 Front 연산을 통해 현재 큐의 첫 번째 요소가 65임을 확인할 수 있습니다.
참고: 시간 복잡도와 개선 방향
- Enqueue: O(1)
- Dequeue: O(n) — 남은 모든 요소를 한 칸씩 앞으로 이동해야 하기 때문입니다.
- Front: O(1)
- Display: O(n)
Dequeue 시 요소 이동으로 인한 성능 저하를 줄이려면 배열을 환형으로 활용하는 환형 큐(Circular Queue)를 도입하거나, 실무에서는 C++ 표준 라이브러리의 std::queue를 사용하는 것이 좋습니다.