[궁금시리즈] 4-5. Queue와 Stack는 언제 사용해야 할까?
지금까지 List
그런데 다음과 같은 상황을 생각해 보자.
은행에서 번호표를 뽑고 기다리는 사람들.
1번
2번
3번
4번
누가 먼저 서비스를 받아야 할까?
당연히 가장 먼저 온 사람이 먼저 처리되어야 한다.
반대로 실행 취소(Undo) 기능은 어떨까? 가장 마지막에 수행한 작업부터 되돌려야 한다.
이처럼 데이터를 저장하는 순서뿐만 아니라 꺼내는 순서가 중요한 경우가 있다.
이 문제를 해결하기 위해 만들어진 자료구조가 Queue
Queue는 무엇일까?
Queue는
먼저 들어온 데이터가 먼저 나가는(FIFO, First In First Out) 자료구조이다.
예를 들어
Queue<string> queue = new();
queue.Enqueue("A");
queue.Enqueue("B");
queue.Enqueue("C");
현재 상태는
앞
↓
[A][B][C]
↑
뒤
여기서
queue.Dequeue();
를 호출하면
A
가 제거된다. 남은 상태는
[B][C]
이다. 즉, 먼저 들어온 데이터가 먼저 처리된다.
Queue는 어디에서 사용할까?
대표적인 예는 작업 대기열(Job Queue)
플레이어 요청
↓
Queue
↓
서버 처리
요청이 들어온 순서대로 처리해야 한다.
프린터 출력
문서1
↓
문서2
↓
문서3
먼저 출력 요청한 문서부터 인쇄된다.
게임 이벤트
예를 들어
몬스터 생성
↓
데미지 계산
↓
아이템 지급
순서대로 처리해야 하는 작업도 Queue를 사용하기 좋다.
Stack은 무엇일까? Stack은
나중에 들어온 데이터가 먼저 나가는(LIFO, Last In First Out) 자료구조이다.
예를 들어
Stack<string> stack = new();
stack.Push("A");
stack.Push("B");
stack.Push("C");
상태는
위
[C]
[B]
[A]
아래
여기서
stack.Pop();
을 호출하면 C가 먼저 나온다.
즉,
가장 마지막에 들어온 데이터가 가장 먼저 처리된다.
Stack은 어디에서 사용할까?
대표적인 예는 실행 취소(Undo)
예를 들어
그리기
↓
색칠
↓
지우기
Undo를 누르면 가장 마지막 작업인
지우기부터 취소되어야 한다.
함수 호출(Call Stack) C#에서 메서드를 호출하면 내부적으로 Stack을 사용한다.
예를 들어
A();
↓
B();
↓
C();
실행 순서는
A
↓
B
↓
C
이지만 반환은
C
↓
B
↓
A
순으로 이루어진다. 이것이 Stack 구조이다.
DFS(깊이 우선 탐색) 트리나 그래프를 탐색할 때도 Stack이 자주 사용된다.
Queue와 Stack의 공통점 둘 다 데이터를 저장하는 컬렉션이다. 하지만 중간에 데이터를 삽입하거나 삭제하는 것이 목적이 아니다.
항상 한쪽 끝에서만 데이터를 넣고 꺼낸다. 그래서 내부 동작이 단순하고 매우 빠르다.
List와 무엇이 다를까?
예를 들어
List<int> list = new();
는
list[3];
처럼 원하는 위치에 접근할 수 있다. 하지만 Queue는
queue.Dequeue();
만 가능하다.
Stack은
stack.Pop();
만 가능하다. 즉, 자료구조 자체가 잘못된 사용을 막아 준다.
예를 들어 Queue에서중간 데이터를 꺼낼 수 있다면 FIFO라는 규칙이 깨진다.
그래서 아예 그런 기능을 제공하지 않는다.
Peek는 무엇일까?
가끔 데이터를 꺼내지는 않고 확인만 하고 싶을 때가 있다.
Queue에서는
queue.Peek();
Stack에서는
stack.Peek();
를 사용한다.
예를 들어
Queue
[A][B][C]
Peek는
A
를 반환하지만 제거하지는 않는다. Stack도 맨 위의 데이터를 반환만 한다.
실무에서는 언제 사용할까?
다음 기준으로 생각하면 된다. Queue
- 순서대로 처리해야 하는 작업
- 이벤트 처리
- 네트워크 패킷 처리
- 작업 대기열
Stack
- Undo 기능
- 함수 호출
- DFS
- 뒤로 가기 기능
실제 .NET에서는 어떻게 구현되어 있을까?
Queue
Queue<T>
↓
T[]
Stack<T>
↓
T[]
하지만 데이터를 관리하는 방식이 다르다. Queue는 앞과 뒤를 나타내는 인덱스를 관리하는 원형 버퍼(Circular Buffer) 구조를 사용한다.
Head → [ ][ ][ ][ ] ← Tail
앞에서 데이터를 꺼내더라도 나머지 데이터를 모두 앞으로 이동하지 않는다.
대신 Head와 Tail 위치만 변경한다. 덕분에 Enqueue()와 Dequeue()는 대부분 매우 빠르게 수행된다. Stack은 훨씬 단순하다. 배열의 끝에 데이터를 추가하고, 끝에서 제거하기만 하면 된다.
Push
↓
배열 끝에 추가
↓
Pop
↓
배열 끝에서 제거
이 때문에 Push()와 Pop()도 대부분 매우 빠르게 수행된다.
실무에서 자주 하는 실수
많은 개발자가 Queue 대신
List<T>
를 사용하면서
list.RemoveAt(0);
를 반복한다. 하지만 RemoveAt(0)은 모든 요소를 한 칸씩 앞으로 이동해야 한다.
[A][B][C][D]
↓
[B][C][D]
이 과정에서 데이터 이동이 발생한다. 반면 Queue는 Head 위치만 변경하므로 데이터를 이동하지 않는다. 즉, FIFO 구조라면 List보다 Queue가 훨씬 적합하다.
마무리
Queue
Queue는 먼저 들어온 데이터를 먼저 처리해야 하는 상황에, Stack은 가장 최근 데이터를 먼저 처리해야 하는 상황에 적합하다. 이처럼 자료구조는 단순히 데이터를 담는 그릇이 아니라 문제를 해결하는 규칙을 표현하는 도구이다. 적절한 자료구조를 선택하면 코드가 더 단순해지고, 잘못된 사용도 자연스럽게 방지할 수 있다. 다음 글에서는 LinkedList<T>는 언제 사용하는 것이 좋을까?를 알아보며 배열 기반 컬렉션과 연결 리스트의 차이를 살펴보겠다.
핵심 정리
- Queue
는 FIFO(First In First Out) 구조이다. - Stack
는 LIFO(Last In First Out) 구조이다. - Queue는 작업 대기열, 이벤트 처리, 네트워크 패킷 처리 등에 적합하다.
- Stack은 Undo 기능, 함수 호출, DFS 등에 적합하다.
- Peek()는 데이터를 제거하지 않고 확인만 한다.
- Queue와 Stack은 내부적으로 배열을 사용하지만 관리 방식이 다르다.
- FIFO가 필요하다면 List
보다 Queue 가 더 적합하다.