큐(Queue)는 ‘줄을 서다’라는 뜻을 가지고 있습니다. 큐는 먼저 들어간 데이터가 먼저 나오는 자료구조입니다. 역시 스택과 마찬가지로 생활 속에서 쉽게 예를 찾아볼 수 있습니다. 맛집에서 줄을 선 순서대로 식당에 입장할 때를 생각해보면 됩니다. 먼저 줄을 선 사람이 먼저 입장합니다. 이런 큐의 특징을 선입선출 또는 FIFO(First in First out)이라고 합니다. 그리고 스택과 마찬가지로 큐도 삽입하는 연산을 푸시, 꺼내는 연산을 팝이라고 합니다.
큐 개념을 이해하고, 이를 바탕으로 ADT를 작성하는 방법을 배워봅시다.
[코딩 테스트] C++ 큐 | 개념, ADT, 동작
1. 큐에서 데이터가 이동하는 과정 살펴보기
그림을 통해 큐에서 원소가 이동하는 과정을 이해해봅시다.
01단계 빈 큐를 하나 선언했습니다.
02단계 원소 2를 삽입합니다. 빈 큐이므로 제일 앞에 삽입합니다. 이어서 5를 삽입합니다. 5는 2다음으로 삽입했으니 2보다는 뒤에 있습니다.
03단계 스택과 달리 팝을 하면 5가 아니라 2가 먼저 나옵니다. 이어서 팝을 한 번 더 진행하면 5가 빠져나옵니다. 스택을 공부했다면 큐에서 데이터가 이동하는 과정은 이 정도 설명이면 쉽게 이해할 수 있을 겁니다.
2. 큐의 특성을 활용하는 분야
먼저 들어온 것을 먼저 처리하는 큐의 동작 방식은 프로그래밍 언어에서 많이 활용되고 있습니다. 대표적으로 여러 이벤트가 발생했을 때 발생한 순서대로 처리할 때 큐가 활용됩니다. 실생활에서도 큐의 특성은 자연스럽게 사용되고 있습니다. 영화관에서 줄을 서는 사람들을 처리해야 할 때 먼저 줄을 선 사람을 먼저 처리하는 것이 그 예죠. 그 밖의 큐의 특성을 활용하는 분야는 다음과 같습니다.
- 작업 대기열 : 네트워크 통신을 할 때 다수의 클라이언트에서 서버에 작업을 요청하면 서버는 요청이 들어온 순서대로 작업을 처리합니다. 이때 큐를 활용할 수 있습니다.
- 이벤트 처리 : 어떤 애플리케이션이나 시스템에서 사용자의 이벤트, 예를 들어 키보드 입력이나 마우스 움직임을 처리할 때 큐를 활용할 수 있습니다.
3. 큐의 ADT
여기서도 스택과 마찬가지로 큐의 ADT를 정의해보고 큐가 실제로 동작하는 원리를 살펴보겠습니다.
큐의 ADT는 다음과 같습니다. 여기서도 표와 그림으로 설명하겠습니다.
그림은 큐의 ADT를 나타낸 겁니다. 큐의 외부와 내부에 네모 모양으로 표현한 연산과 데이터 상태가 보입니다. 이 그림은 스택에서 제시했던 그림이므로 쉽게 이해할 수 있을 겁니다. 달라진 점은 스택의 top이 front와 rear로 바뀐 겁니다. front는 큐의 앞, rear는 큐의 뒤를 의미합니다. 큐는 앞에서 데이터를 빼고(팝), 뒤에서 데이터를 넣으므로(푸시) 이렇게 앞과 뒤의 데이터 최종 위치를 기억할 변수가 필요합니다. 지금의 경우 아무런 데이터도 넣은 상태가 아니므로 front와 rear 모두 -1입니다.
※ 배열의 인덱스는 0부터 시작하므로 아무것도 넣지 않은 상황을 표현하기 위해 초깃값을 -1로 했습니다.
3.1 큐의 세부 동작에 대해 조금 더 자세히 알아보기
구체적인 예와 함께 큐에서 연산이 수행되면 어떻게 되는지 알아보겠습니다.
01단계 다음은 isFull( ) 연산으로 ① 현재 큐가 가득 찼는지 확인하고 큐가 가득 차지 않았으므로 (isFull이 False) ② rear를 +1한 다음 rear가 가리키는 위치에 ③ 3을 푸시하는 모습입니다.
※ 반대로 isFull 연산이 True이면 데이터를 푸시하지 않습니다.
02단계 이 상태에서 팝을 하면 어떻게 될까요? ① 우선 isEmpty( ) 연산을 통해 큐가 비었는지 확인합니다. isEmpty( ) 연산은 front, rear의 값이 같은지 확인해서 큐에 원소가 없는데 팝하는 동작을 방지합니다. ② 만약 비어 있지 않다면(isEmpty가 False) front를 +1합니다. 이렇게 하면 front, rear가 0으로 같아지므로 ③ isEmpty( ) 연산 시 큐가 빈 것(isEmpty( )가 True)으로 처리되어 실제 배열의 데이터를 삭제하지 않고도 데이터를 삭제한 것처럼 관리할 수 있습니다.
03단계 계속해서 푸시를 해봅시다. ① 5를 푸시하면 IsFull( ) 연산을 수행해 큐가 가득 찼는지 검사하고, 가득 차지 않았다면 푸시합니다. ② 연거푸 6과 8을 푸시하면 다음과 같이 front는 0, rear는 3일 겁니다.
04단계 이제 큐가 가득 찼을 때 푸시하면 어떻게 되는지 봅시다. ① rear가 3이므로 maximize -1과 같습니다. 다시 말해 ② isFull( ) 연산은 True이므로 푸시하지 못합니다.
큐가 가득 찬 상태에서 하나 생각해볼 내용이 있습니다. 마지막 푸시에서 실제 data에 저장한 데이터는 3, 5, 6, 8로 4개지만 큐는 5, 6, 8로 3개입니다. 다시 말해 큐는 front의 다음부터 rear까지를 큐가 관리하는 데이터로 생각해야 합니다. 그런데 가만히 생각해보면 실제 data의 공간은 4개인데 큐가 관리하는 데이터는 3개이므로 실질적으로는 메모리 공간을 낭비한 상황입니다. 이렇게 된 이유는 큐를 한 방향으로 관리하고 있기 때문입니다. 이렇게 하면 front 이전의 공간을 활용하지 못합니다. 다시 말해 front 이전을 기준으로 큐의 사용할 수 있는 부분과, 사용할 수 없는 부분이 나뉘었습니다.
💡합격 조언: 큐를 원형으로 개선하기
이를 개선하려면 위에서 설명한 형태의 큐가 아니라 다른 형태의 큐가 필요합니다. 책에서 설명한 선형 큐는 front와 rear가 한 방향으로 이동하죠. 원형 큐는 이 점을 개선해서 낭비하는 공간을 없애기 위해 원형으로 front와 rear가 돕니다. 원형 큐는 선형 큐보다 구현하기는 조금 복잡하지만 메모리 공간을 절약한다는 장점이 있습니다.
하지만 STL의 자료구조는 내부에서 메모리 관리를 해주기 때문에 코딩 테스트에서는 STL에서 제공하는 큐를 사용해도 충분합니다. 다만 원형 큐의 개념을 알아두면 좋을 것 같아서 간략하게 설명했습니다. 원형 큐의 상세한 내용이 궁금하다면 인터넷으로 원형 큐를 검색하여 좀 더 공부해보세요.
3.2 큐 구현하기
C++의 STL에서는 큐를 제공합니다. 따라서 코드 예를 보고 사용법만 익히면 쉽게 활용할 수 있을 겁니다. STL에서 제공하는 큐의 push( ), pop( ), front( ), empty( ) 연산은 모두 시간 복잡도 O(1)입니다.
#include <iostream>
#include <queue>
using namespace std;
int main() {
queue<int> q; // 큐 생성
// 푸시 연산
q.push(10);
q.push(20);
q.push(30);
// 큐의 맨 앞 요소 출력
cout << "Front: " << q.front() << endl;
// 반복문을 사용하여 큐가 빌 때까지 팝
while (!q.empty()) {
cout << q.front() << "을 큐에서 삭제했습니다." << endl;
q.pop();
}
// 큐가 비어 있는지 확인
cout << "큐가 비어있나요? " << (q.empty() ? "Yes" : "No") << endl;
return 0;
}
// 출력값
// Front: 10
// 10을 큐에서 삭제했습니다.
// 20을 큐에서 삭제했습니다.
// 30을 큐에서 삭제했습니다.
// 큐가 비어 있나요? Yes
지금까지 큐 개념을 이해하고, ADT를 작성하는 방법을 배워보았습니다.
저자 박경록
매일 퇴근과 점심 메뉴를 고민하는 9년차 시스템 S/W 개발자입니다. 수학, 알고리즘 같은 실생활과 가깝고도 먼 학문을 좋아하고, 명확하지만 개선 여지가 있는 문제들에 대해 논의하고 사고를 개선해 나가는 과정을 좋아합니다.
