■ 큐(Queue)
앞서 스택(Stack)은 먼저 들어온 것이 나중에 나가는 “선입후출(FILO)” 구조를 지녔다. 그리고 이걸 “쌓여있는 접시”, “프링글스 통 안의 감자칩”에 비유했었다,
반대로 큐(Queue)는 “줄을 서 있는 사람들”처럼 먼저 들어온 것이 먼저 나가는 “선입선출(FIFO)”의 구조를 지닌다.
- 큐의 개념은 일상생활에서도 쉽게 찾을 수 있다. 고무호스, 터널, 극장표 예매처 등은 모두 큐의 동작 방식과 유사한 구조이다.
▶ 큐의 추상 자료형
스택과 마찬가지로 큐의 추상 자료형도 정형화된 편이다.
- enqueue : 큐에 데이터를 넣는 연산.
- dequeue : 큐에서 데이터를 빼는 연산.
| 정의 | 의미 |
| void InitQueue(Queue* pq) | 큐의 초기화를 진행한다. |
| bool IsEmpty(Queue* pq) | 큐가 빈 경우 true, 비어있지 않은 경우 false를 반환한다. |
| void Enqueue(Queue* pq, Data data) | 큐에 데이터를 저장한다. |
| Data Dequeue(Queue* pq) | 저장순서가 가장 앞선 데이터를 삭제하고 반환한다. |
| Data Peek(Queue* pq) | 저장순서가 가장 앞선 데이터를 반환하되 삭제하지 않는다. |
스택에서 데이터를 넣고 빼는 연산을 가리켜 각각 push, pop이라 하는 것처럼, 큐에서 데이터를 넣고 빼는 연산을 각각 enqueue, dequeue라고 한다.
■ 큐의 설계
1. 배열 기반 구현
스택과 큐의 가장 큰 차이는 데이터를 꺼내는 위치, 즉 앞에서 꺼내느냐 뒤에서 꺼내느냐의 차이이다.
그래서 얼핏 보면, 앞서 만든 스택 자료구조에서 단순히 꺼내는 위치만 바꾸면 큐를 만들 수 있을 것처럼 보일 수 있지만, 실제로는 그렇지 않다.
F(Fornt)가 가리키는 것이 큐의 머리이고, R(Rear)이 가리키는 것이 큐의 꼬리이다.
- Enqueue를 하게 되면 R이 다음 칸을 가리키고 그 칸에 데이터가 저장된다.
Dequeue : f가 가리키는 데이터 반환 후, 데이터를 빈자리로 이동
Dequeue 연산을 할 때, 반환할 데이터를 항상 배열의 맨 앞(Index : 0)에 위치시켜 보자. 이 방식의 경우 아래와 같은 문제점이 생긴다.
- 항상 배열의 첫 번째 데이터만 Dequeue되므로, 굳이 F(fornt 인덱스)가 필요 없다.
- Dequeue가 일어날 때마다, 남아 있는 모든 데이터를 한 칸씩 앞으로 옮겨야 한다.
Dequeue : f가 가리키는 데이터 반환 후, f를 이동
이번엔 Dequeue 연산 시 F를 이동시키고 있다. 이 방식을 취하게 되면 Dequeue 연산에서 데이터의 이동이 필요하지 않다.
문자 E가 배열의 끝에 저장되어 더 이상 R을 옮길 수 없는 상황이다. 이 상황에서 어떻게 enqueue 연산을 진행할 수 있을까?
바로 R을 다시 배열의 맨 앞으로 이동시키면 된다!! (F 역시 마찬가지.)
- 이렇게 배열의 끝에 도달하면 다시 처음으로 돌아가 회전하는 방식의 구조를 “원형 큐(circular queue)라 한다.”
2. 원형 기반 큐
원형 큐도 앞서 보인 큐와 같이 첫 번째 데이터가 추가되는 순간 F, R이 동시에 그 데이터를 가리킨다. 이후 Dequeue연산을 두 번 진행하면 아래와 같다.
이제 구현만 하면 될 것 같지만, 현재 원형 큐에서 생각해 볼 문제가 아직 남아있다.
원형 큐에서 데이터가 모두 차 있는 경우와 비어 있는 경우는 모두 F가 R보다 한 칸 앞선 위치를 가리키는 형태를 갖는다.
- 따라서 F와 R의 위치 정보만으로 큐가 비어 있는 상태인지, 가득 찬 상태인지 구분할 수 없다.
이러한 문제를 해결하기 위해 배열의 크기가 N일 때, 최대 N - 1개의 데이터만 저장하도록 제한한다.
즉, 배열에 N-1개의 데이터가 채워졌을 경우를 “꽉 찬 상태”로 간주하고, 항상 하나의 빈 공간을 유지한다.
- enqueue 연산 시 R이 가리키는 위치를 한 칸 이동시킨 다음에 데이터를 저장한다.
- Dequeue 연산 시 F가 가리키는 위치를 한 칸 이동시킨 다음에 데이터를 반환한다.
따라서 R과 F가 같은 위치를 가리킨다면 큐가 “비어있는 상태” R이 가리키는 앞 위치가 F라면 큐가 “꽉 찬 상태”로 해석할 수 있다.
■ 원형 큐의 구현(배열 기반)
1. CircularQueue.h
#pragma once
constexpr int QUE_LENGTH = 100;
typedef int Data;
struct CircularQueue
{
Data data[QUE_LENGTH];
int front;
int rear;
}; typedef CircularQueue CQueue;
void InitQueue(CQueue* pq);
void Enqueue(CQueue* pq, Data item);
Data Dequeue(CQueue* pq);
Data Peek(CQueue* pq);
bool IsEmpty(const CQueue* pq);
[CircularQueue.h]
앞서 정의한 큐의 추상 자료형을 기반으로 위의 헤더파일을 정의하였다.
2. CircularQueue.cpp
헤더파일에 선언된 함수의 구현을 보일 차례인데, 그에 앞서 아래의 함수를 살펴보자. 함수는 간단하지만 원형 큐의 핵심이라 할 수 있다.
int NextIndex(int index)
{
return (index + 1 >= QUE_LENGTH - 1)
? 0 : index + 1;
}
이는 큐의 다음 위치에 해당하는 배열의 인덱스 값을 반환하는 함수이다.
pos 를 전달하면 pos + 1의 값을 반환하지만, 큐의 길이보다 하나 작은 값이 인자로 전달된다면 0을 반환한다.
- 이는 F와 R이 배열의 끝에 도달했으므로 앞으로 이동해야 함을 의미한다.
#include "CircularQueue.h"
#include <iostream>
using namespace std;
int NextIndex(int index);
void InitQueue(CQueue* pq)
{
pq->front = pq->rear = 0;
}
void Enqueue(CQueue* pq, Data item)
{
auto nextIndex = NextIndex(pq->rear);
// Queue가 가득 찼는지 확인
if(nextIndex == pq->front)
{
cout << "Queue is Full!" << endl;
return;
}
pq->rear = nextIndex;
pq->data[pq->rear] = item;
}
Data Dequeue(CQueue* pq)
{
if(IsEmpty(pq))
{
cout << "Queue is Empty!" << endl;
return -1;
}
pq->front = NextIndex(pq->front);
return pq->data[pq->front];
}
Data Peek(CQueue* pq)
{
if(IsEmpty(pq))
{
cout << "Queue is Empty!" << endl;
return -1;
}
return pq->data[NextIndex(pq->front)];
}
int NextIndex(int index)
{
return (index + 1 >= QUE_LENGTH - 1)
? 0 : index + 1;
}
bool IsEmpty(const CQueue* pq)
{
return pq->front == pq->rear;
}
Queue에 2~100의 숫자 중 짝수만 Enqueue() 하고, 그 뒤에 Queue가 빌 때까지 Dequeue()하였다. 스택과 다르게 먼저 들어간 숫자가 먼저 나오는 “선입선출(FIFO)”구조로 만들어진 것을 확인할 수 있다.
■ 연결 리스트 기반 큐의 구현
배열을 기반으로 구현된 Stack을 Queue로 변경하려고 하면, 앞에서 살펴본 것처럼 고려해야 할 문제가 한두가지가 아니다.
하지만 ”연결 리스트 기반의 큐”는 배열 기반 구조에 비해 이러한 제약이 적기 때문에, 구조적으로는 스택 구현 방식을 어느 정도 재활용할 수 있지만, 아래와 같은 본질적인 동작 방식의 차이는 존재한다.
- 스택은 Push와 Pop이 같은 위치에서 이루어지지만, 큐는 Queue와 Dequeue가 다른 위치에서 발생한다.
1. ListQueue.h
#pragma once
typedef int Data;
struct ListQueueNode
{
Data data;
ListQueueNode* next = nullptr;
}; typedef ListQueueNode Node;
struct ListQueue
{
Node* front = nullptr;
Node* rear = nullptr;
}; typedef ListQueue LQueue;
void InitQueue(LQueue* pq);
void Enqueue(LQueue* pq, Data item);
Data Dequeue(LQueue* pq);
Data Peek(LQueue* pq);
bool IsEmpty(const LQueue* pq);
위의 헤더파일에서 보이듯이 연결 리스트 기반 큐에서도 원형 큐와 마찬가지로 front와 rear을 유지해야 한다.
- enqueue연산과 dequeue 연산이 이뤄지는 위치가 다르기 때문.
2. ListQueue.cpp
void InitQueue(LQueue* pq)
{
if(pq->front != nullptr && pq->rear != nullptr)
{
// 기존 노드가 존재한다면 해제
while(IsEmpty(pq) == false)
{
Dequeue(pq);
}
}
pq->front = nullptr;
pq->rear = nullptr;
}
처음 큐를 생성하면 front와 rear이 가리킬 대상이 없으니, 초기에는 nullptr로 설정한다.
- 단, 데이터가 남아있는 상태에서 nullptr로 초기화 하면 기존 생성된 데이터에 접근할 수 없으니, Dequeue()를 호출하여 메모리 공간을 해제한다.
void Enqueue(LQueue* pq, Data item)
{
auto node = new Node();
node->data = item;
node->next = nullptr;
if(IsEmpty(pq) == true)
{
pq->front = node;
pq->rear = node;
}
else
{
pq->rear->next = node;
pq->rear = node;
}
}
큐에 아무런 데이터가 저장되지 않은 상태에서 데이터를 추가하면, F와 R모두 첫 번째 데이터를 가리켜야 한다.
- 이후에 추가되는 데이터는 R만 움직이면 되므로 가장 끝에 있는 노드(R이 가리키는 노드)가 새 노드를 가리키게 한 다음, R이 새 노드를 가리키게 만든다.
Data Dequeue(LQueue* pq)
{
if(IsEmpty(pq))
{
cout << "Queue is Empty!" << endl;
return -1;
}
auto delNode = pq->front;
auto retData = delNode->data;
pq->front = delNode->next;
delete delNode;
return retData;
}
Dequene 과정에서는 신경 써야 할 부분이 F 하나이므로, Enqueue처럼 다른 포인터(R)를 건드릴 필요는 없다.
- F가 다음 노드를 가리키게 한다.
- F가 이전에 가리키던 노드를 소멸시킨다.
#include "ListQueue.h"
#include <iostream>
using namespace std;
void InitQueue(LQueue* pq)
{
if(pq->front != nullptr && pq->rear != nullptr)
{
// 기존 노드가 존재한다면 해제
while(IsEmpty(pq) == false)
{
Dequeue(pq);
}
}
pq->front = nullptr;
pq->rear = nullptr;
}
void Enqueue(LQueue* pq, Data item)
{
auto node = new Node();
node->data = item;
node->next = nullptr;
if(IsEmpty(pq) == true)
{
pq->front = node;
pq->rear = node;
}
else
{
pq->rear->next = node;
pq->rear = node;
}
}
Data Dequeue(LQueue* pq)
{
if(IsEmpty(pq))
{
cout << "Queue is Empty!" << endl;
return -1;
}
auto delNode = pq->front;
auto retData = delNode->data;
pq->front = delNode->next;
delete delNode;
return retData;
}
Data Peek(LQueue* pq)
{
if(IsEmpty(pq))
{
cout << "Queue is Empty!" << endl;
return -1;
}
return pq->front->data;
}
bool IsEmpty(const LQueue* pq)
{
return pq->front == nullptr;
}
[ListQueue.cpp 전체 코드]
'C++ > 자료구조' 카테고리의 다른 글
| [C++, 자료구조] 덱(Deque) (1) | 2025.12.22 |
|---|---|
| [C++, 자료구조] stack의 응용 : 계산기 프로그램 (0) | 2025.11.11 |
| [C++, 자료구조] 스택(Stack) (1) | 2025.11.11 |
| [C++, 자료구조] 양방향 연결 리스트(Doubly Linked List) (0) | 2025.10.23 |
| [C++, 자료구조] 단일 연결 리스트(Singly Linked List) (0) | 2025.10.23 |