Queue(큐)는 다양한 프로그래밍 환경에서 반복적으로 등장하는 기본 자료구조입니다. 동작 방식은 단순하지만 실제 시스템 구조 속에서 핵심적인 역할을 담당합니다. 가장 중요한 특징은 FIFO(First-In, First-Out), 즉, 먼저 들어간 값이 먼저 나온다는 점입니다.
이번 글에서는 큐의 개념과 특징을 정리하고, C# 배열을 이용해 원형 큐(circular queue) 방식으로 직접 구현하는 방법을 살펴보겠습니다.
1. 큐 구조와 동작 방식
큐는 한쪽 끝에서만 데이터가 삽입되고(Enqueue), 반대쪽 끝에서만 데이터가 제거되는(Dequeue) 구조입니다. 삽입과 제거 위치가 서로 다르며, 항상 먼저 들어온 데이터가 먼저 나가는 FIFO 규칙을 따릅니다.
“줄 서기” 상황에 비유하면 이해하기 쉽습니다.
- 먼저 온 사람이 줄 맨 앞에 섭니다.
- 나중에 온 사람은 앞에 온 사람 뒤에 섭니다.
- 입장할 때는 맨 앞에 있는 사람부터 순서대로 들어갑니다.
큐에서도 마찬가지로,
- 새로운 데이터는 항상 뒤쪽(tail)에 추가되고
- 데이터를 꺼낼 때는 항상 앞쪽(head)에서 제거됩니다.
※ 참고로 head / tail 대신 front / rear라는 용어를 사용하는 경우도 많습니다.
※ 동작을 시각적으로 확인해보기
아래 링크는 큐(Queue)의 Enqueue / Dequeue 동작을 단계별로 시각화해 주는 도구입니다. 참고하면 데이터가 어떤 방향으로 들어오고, 어떤 순서로 빠져나가는지 직관적으로 이해할 수 있습니다.
https://www.cs.usfca.edu/~galles/visualization/QueueArray.html
2. 큐가 활용되는 대표적인 사례
큐는 구조가 단순하지만 다음과 같은 기능의 핵심 요소로 자주 활용됩니다.
- 요청(이벤트) 처리
네트워크 요청, 입력 이벤트, 로그 등은 들어온 순서대로 처리해야 합니다. 이런 요청들을 큐에 쌓아 두었다가 하나씩 꺼내며 처리합니다. - 너비 우선 탐색(BFS)
그래프 탐색에서 인접 노드를 방문할 때, 탐색 대상을 큐에 넣고 순서대로 꺼내면서 탐색을 확장합니다. - 프린터 출력 작업
출력 버튼을 누를 때마다 작업이 큐에 쌓이고 순서대로 인쇄합니다. - 키 입력 처리
격투 게임처럼 입력 순서가 중요한 경우, 입력 버퍼를 큐로 구현할 수 있습니다.
정리하면, “들어온 순서가 중요한 모든 상황”에서 큐가 자연스럽게 등장한다고 볼 수 있습니다.
3. 큐가 제공하는 기능 (구현 기준)
배열 기반 큐는 일반적으로 다음과 같은 핵심 연산을 제공합니다.
- Enqueue : 데이터를 큐의 뒤쪽(tail)에 삽입
- Dequeue : 큐의 앞쪽(head)에 있는 데이터를 제거하며 반환
- Peek : 가장 앞에 있는 데이터 조회(제거하지 않음)
- Count : 현재 저장된 데이터 수
- IsEmpty : 큐가 비어 있는지 여부
※ 배열 기반으로 구현할 때는 내부 배열의 용량이 가득 찼을 때 자동으로 크기를 늘리는 동적 확장(Resize) 기능도 함께 고려해야 합니다.
4. 큐의 내부 동작 방식
큐는 내부적으로 데이터를 담는 배열과, 앞/뒤 위치를 나타내는 head, tail 인덱스, 그리고 현재 요소 개수를 나타내는 count로 구현할 수 있습니다. 이 구조를 활용하면 원형 큐(circular queue) 방식으로 효율적으로 동작시킬 수 있습니다.
단순한 배열 큐에서는 head가 증가하면서 앞부분이 비어도 재사용하지 못하므로 공간 낭비가 생깁니다. 이를 해결하려고 앞쪽 데이터를 매번 한 칸씩 당기는(shift) 방식도 가능하지만, 모든 데이터를 이동해야 하므로 O(n) 비용이 발생해 실무에서는 거의 사용하지 않습니다. 이런 비효율을 제거하기 위해 고안된 구조가 바로 원형 큐(circular queue) 입니다
✔ 초기 상태
- 큐는 비어 있음
- head = 0, tail = 0, count = 0
✔ A추가 (Enqueue)
- 현재 tail 자리에 A 추가
- tail 위치 1 증가, count 1 증가
- head = 0, tail = 1, count = 1
✔ B, C 추가 (Enqueue)
- 같은 방식으로 B, C 추가
- head = 0, tail = 3, count = 3
✔ A 제거 (Dequeue)
- 현재 head에서 A 제거
- head 위치 1 증가, count 1 감소
- head = 1, tail = 3, count = 2
✔ D 추가 (Enqueue)
- 현재 tail 위치(3)에 D 저장
- 이후 tail = (tail + 1) % 4(배열 길이) = 0 (배열 끝에서 다시 0으로 돌아감)
- head = 1, tail = 0, count = 3
✔ B, C 제거 (Dequeue)
- head = 3, tail = 0, count = 1
✔ D 제거 (Dequeue)
- head = (head + 1) % 4(배열 길이) = 0
- 큐가 전부 비워진 상태
- head = 0, tail = 0, count = 0
※ 'head, tail이 배열 끝을 넘어가면 (% 배열 길이) 연산으로 0으로 되돌아온다.'
이것이 원형 큐의 핵심 개념입니다.
5. C# 배열로 큐 직접 구현하기
아래 코드는 배열을 기반으로 큐를 제네릭 형태로 구현한 예제입니다. 내부적으로 원형 큐 구조를 사용하여 Enqueue와 Dequeue가 O(1)에 가깝게 동작하도록 설계했습니다.
using System;
namespace Daebak.Common.Collections
{
public class Queue<T>
{
private T[] _items; // 내부 배열
private int _head; // 첫 번째 요소 인덱스
private int _tail; // 마지막 요소 다음 인덱스
private int _count; // 큐에 들어 있는 요소 개수
public int Count => _count;
public Queue(int capacity = 10)
{
_items = new T[capacity];
_head = 0;
_tail = 0;
_count = 0;
}
public void Clear()
{
Array.Clear(_items, 0, _items.Length);
_head = 0;
_tail = 0;
_count = 0;
}
public void Enqueue(T item)
{
// 배열이 가득 찼으면 두 배로 확장
if (_count == _items.Length)
{
Resize();
}
_items[_tail] = item; // 현재 tail 위치에 아이템 추가
_tail = (_tail + 1) % _items.Length; // tail 증가 (원형 큐)
++_count;
}
public T Dequeue()
{
if (_count == 0)
{
throw new InvalidOperationException("Queue is empty!!");
}
T item = _items[_head]; // 현재 head 위치의 아이템 얻기
_items[_head] = default; // head 위치 비우기
_head = (_head + 1) % _items.Length; // head 증가 (원형 큐)
--_count;
return item;
}
public T Peek()
{
if (_count == 0)
{
throw new InvalidOperationException("Queue is empty!!");
}
return _items[_head];
}
public bool IsEmpty()
{
return _count == 0;
}
private void Resize()
{
int newSize = _items.Length * 2;
T[] newArray = new T[newSize];
// head부터 순서대로 복사
for (int i = 0; i < _count; ++i)
{
newArray[i] = _items[(_head + i) % _items.Length];
}
// Resize 후에는 head 기준으로 0부터 순서대로 재배치되기 때문에,
// 새로운 배열에서 tail은 항상 count와 같아짐.
_items = newArray;
_head = 0;
_tail = _count;
}
}
}- Resize 메서드에서 새로운 배열을 기존 배열의 두 배 크기로 생성하고, head 기준으로 순서대로 복사한 뒤 인덱스를 재설정합니다.
6. 유니티(Unity) 환경에서 테스트해 보기
Unity 프로젝트에서 구현한 큐가 정상적으로 동작하는지 확인하려면 다음과 같은 테스트 스크립트를 사용할 수 있습니다.
using UnityEngine;
using Daebak.Common.Collections;
public class Test_Queue : MonoBehaviour
{
void Start()
{
Queue<int> q = new Queue<int>(3); // capacity 3으로 시작해 Resize 테스트 쉽게 함
Debug.Log("=== Enqueue 3개 ===");
q.Enqueue(1);
q.Enqueue(2);
q.Enqueue(3);
Debug.Log($"Peek: {q.Peek()}"); // 1
Debug.Log("\n=== Dequeue 2개 ===");
Debug.Log(q.Dequeue()); // 1
Debug.Log(q.Dequeue()); // 2
Debug.Log($"\nCount: {q.Count}"); // 1
Debug.Log("\n=== Enqueue 2개 (원형 구조 확인) ===");
q.Enqueue(4);
q.Enqueue(5);
Debug.Log($"\nCount: {q.Count}"); // 3
Debug.Log("\n=== Enqueue 1개로 Resize 발생 ===");
q.Enqueue(6); // (기존 배열 가득 → Resize)
Debug.Log($"\nCount after resize: {q.Count}"); // 4
Debug.Log("\n=== 모든 요소 Dequeue ===");
while (!q.IsEmpty())
{
Debug.Log(q.Dequeue());
}
Debug.Log("\nQueue is empty.");
}
}실행 결과
=== Enqueue 3개 ===
Peek: 1
=== Dequeue 2개 ===
1
2
Count: 1
=== Enqueue 2개 (원형 구조 확인) ===
Count: 3
=== Enqueue 1개로 Resize 발생 ===
Count after resize: 4
=== 모든 요소 Dequeue ===
3
4
5
6
Queue is empty.
마무리
큐는 요청 처리, 스케줄링, 탐색 알고리즘, 버퍼 처리 등 다양한 영역에서 활용되는 기본 자료구조입니다. 직접 구현해 보면 head/tail 인덱스의 의미, 원형 큐 방식의 장점, 동적 확장 구조를 명확하게 이해하는 데 도움이 됩니다.
※ 다음 글에서는 List(리스트) 구조를 살펴보며, 선형 자료구조에서 데이터 접근 방식이 어떻게 확장되는지를 중심으로 정리합니다.
'자료 구조' 카테고리의 다른 글
| Unity 개발자를 위한 C# HashSet(해시셋) 구현 (0) | 2025.12.07 |
|---|---|
| Unity 개발자를 위한 C# Deque(덱) 구현 (0) | 2025.12.06 |
| Unity 개발자를 위한 C# LinkedList(링크드 리스트) 구현 (0) | 2025.12.05 |
| Unity 개발자를 위한 C# List(리스트) 구현 (0) | 2025.12.05 |
| Unity 개발자를 위한 C# Stack(스택) 구현 (0) | 2025.11.24 |
