큐(Queue)란 무엇인가?
큐(Queue)는 선입선출(FIFO, First In First Out) 방식으로 동작하는 대표적인 자료구조입니다. 즉, 가장 먼저 삽입된 데이터가 가장 먼저 삭제되는 구조를 가지며, 너비 우선 탐색(BFS, Breadth First Search)과 같은 그래프 탐색 알고리즘을 비롯해 다양한 분야에서 널리 활용됩니다.
ADT(추상 자료형)의 개념
ADT(Abstract Data Type, 추상 자료형)는 값의 집합과 연산의 집합으로 그 동작이 정의되는 특수한 형태의 자료형입니다. '추상'이라는 표현이 붙는 이유는 사용자가 이 자료형을 활용해 다양한 연산을 수행할 수 있지만, 해당 연산이 내부적으로 어떻게 구현되어 있는지는 완전히 숨겨져 있기 때문입니다. ADT는 기본(primitive) 자료형들로 구성되지만, 연산 로직 자체는 외부에 노출되지 않습니다.
큐 ADT의 주요 연산
- isFull() — 큐가 가득 찼는지 여부를 확인합니다.
- isEmpty() — 큐가 비어 있는지 여부를 확인합니다.
- enqueue(x) — 큐의 뒤쪽(rear)에 요소 x를 삽입합니다.
- dequeue() — 큐의 앞쪽(front)에서 요소 하나를 삭제합니다.
- front() — 큐의 맨 앞에 위치한 요소를 반환합니다.
- size() — 큐에 현재 저장된 요소의 개수를 반환합니다.
C++ 예제 코드
다음은 C++ STL의 queue 컨테이너를 사용하여 위에서 소개한 연산들을 직접 실습하는 예제입니다.
#include<iostream>
#include<queue>
using namespace std;
int main(){
queue<int> que;
if(que.empty()){
cout << "Queue is empty" << endl;
} else {
cout << "Queue is not empty" << endl;
}
// 큐에 요소 삽입
que.push(10);
que.push(20);
que.push(30);
que.push(40);
que.push(50);
cout << "Size of the queue: " << que.size() << endl;
// 요소 삭제 및 출력
while(!que.empty()) {
int item = que.front(); // 맨 앞의 요소 읽기
que.pop();
cout << item << " ";
}
}
실행 결과
Queue is empty Size of the queue: 5 10 20 30 40 50
코드 동작 원리
프로그램이 시작되면 큐에는 아무 데이터도 없으므로 empty() 함수가 true를 반환하여 "Queue is empty"가 출력됩니다. 이후 push()를 통해 10부터 50까지 총 5개의 정수를 순서대로 삽입하고, size() 함수로 큐에 저장된 요소 개수인 5를 확인할 수 있습니다.
마지막으로 while 반복문 안에서 front()로 큐의 맨 앞 요소를 읽어낸 뒤 pop()으로 제거하는 과정을 큐가 빌 때까지 반복합니다. 그 결과 삽입한 순서 그대로인 10 20 30 40 50이 출력되는데, 이것이 바로 큐의 선입선출(FIFO) 특성을 보여주는 핵심 부분입니다.