A, B, C 작업을 차례로 넣었는데 첫 번째로 꺼낸 값이 C라면, 코드는 입력 순서를 거꾸로 처리하고 있다. 반대로 A가 먼저 나온다면 들어온 순서를 유지한다. 두 결과의 차이는 자료구조가 어느 끝에 넣고 어느 끝에서 꺼내는지에서 생긴다.
push와 pop, enqueue와 dequeue를 번역만 외우면 모두 '넣고 빼기'처럼 보인다. 같은 세 작업으로 스택과 큐를 나란히 실행해 보면 이름보다 중요한 동작 계약이 선명해진다.
같은 A B C가 왜 반대 순서로 나올까?
스택과 큐에 A → B → C 순서로 값을 추가했다고 하자.
| 구조 | 넣는 동작 | 꺼내는 동작 | 꺼내지는 순서 | 규칙 |
|---|---|---|---|---|
| 스택 | push | pop | C → B → A | LIFO, 나중에 들어온 값이 먼저 나감 |
| 큐 | enqueue | dequeue | A → B → C | FIFO, 먼저 들어온 값이 먼저 나감 |
스택은 접시를 위로 쌓고 위에서 다시 꺼내는 모습에 가깝다. 접근하는 한쪽 끝을 top이라고 부른다. C가 마지막에 올라왔으므로 첫 pop의 결과도 C다.
큐는 줄을 서는 모습에 가깝다. 새 값은 뒤쪽인 rear에 들어가고, 기존 값은 앞쪽인 front에서 나온다. A가 가장 먼저 기다렸으므로 첫 dequeue의 결과는 A다. '먼저 처리한다'는 말이 곧 빠르다는 뜻은 아니다. 여기서는 상대적인 순서만 말한다.
아래 그림처럼 스택은 top 한쪽을 함께 쓰고, 큐는 rear와 front를 나눠 쓴다. 같은 입력이 반대 순서로 나오는 이유가 이 두 위치에 있다.
push와 pop은 같은 끝을 사용한다
스택의 핵심은 추가와 제거가 같은 top에서 일어난다는 점이다.
push A [A]
push B [A, B]
push C [A, B, C] <- top
pop C [A, B]
pop B [A]
pop A []이 규칙은 최근 작업부터 되돌리는 실행 취소, 마지막에 연 괄호부터 닫는 구문 검사, 더 깊은 노드부터 돌아오는 깊이 우선 탐색에 잘 맞는다. 다만 '최근 항목을 먼저 처리해야 한다'는 요구가 없는데 스택을 쓰면 오래된 작업이 계속 뒤로 밀릴 수 있다.
enqueue와 dequeue는 서로 다른 끝을 사용한다
큐는 뒤에 넣고 앞에서 꺼낸다.
enqueue A front -> [A] <- rear
enqueue B front -> [A, B] <- rear
enqueue C front -> [A, B, C] <- rear
dequeue A front -> [B, C] <- rear
dequeue B front -> [C] <- rear
dequeue C []도착 순서를 보존해야 하는 대기 작업, 너비 우선 탐색, 생산자와 소비자 사이의 완충 구간에서 이 규칙이 자연스럽다. 하지만 실제 작업 시스템은 우선순위, 재시도, 예약 시각 때문에 단순 FIFO가 아닐 수 있다. 자료구조 이름만 보고 처리 순서를 추측하지 말고 시스템이 약속한 정렬 기준을 확인해야 한다.
같은 코드에서 결과를 직접 비교해 보자
Python에서는 메서드 이름이 push나 enqueue가 아니어도 같은 규칙을 표현할 수 있다. 스택은 리스트의 오른쪽 끝에 append()하고 같은 끝에서 pop()한다. 큐는 deque의 오른쪽 끝에 추가하고 왼쪽 끝에서 popleft()한다.
from collections import deque
items = ["A", "B", "C"]
stack = []
queue = deque()
for item in items:
stack.append(item)
queue.append(item)
stack_result = [stack.pop() for _ in range(len(stack))]
queue_result = [queue.popleft() for _ in range(len(queue))]
print("stack:", stack_result)
print("queue:", queue_result)실행 결과는 다음과 같다.
stack: ['C', 'B', 'A']
queue: ['A', 'B', 'C']두 컨테이너 모두 오른쪽에 값을 추가했다. 차이를 만든 것은 제거 위치다. 리스트의 pop()은 오른쪽 끝을, deque.popleft()는 왼쪽 끝을 제거한다.
append 다음에 pop을 쓰면 왜 큐가 아닐까?
대기열을 만든다고 변수 이름을 queue로 지어도 append() 뒤에 pop()을 쓰면 동작은 스택이다.
queue = []
queue.append("A")
queue.append("B")
queue.append("C")
print(queue.pop()) # C이 코드는 문법적으로 문제없고 C도 정상적으로 반환한다. 그래서 테스트 데이터가 한 건뿐이면 순서 버그를 발견하기 어렵다. 적어도 서로 구분되는 세 값을 넣고 전체 제거 순서를 검증해야 한다.
assert stack_result == ["C", "B", "A"]
assert queue_result == ["A", "B", "C"]메서드 이름을 읽는 것만으로 끝내지 않고 삽입 끝과 제거 끝을 표나 테스트로 고정하면 구현을 다른 자료구조로 바꿔도 계약을 지킬 수 있다.
빈 구조와 용량 제한은 별도 계약이다
스택이나 큐가 비어 있을 때 제거를 요청하면 반환할 값이 없다. 앞의 Python 예제에서 빈 리스트의 pop()과 빈 deque의 popleft()는 모두 IndexError를 낸다. 다른 API는 예외 대신 None, null, 특별한 상태값을 돌려줄 수 있다. 호출하는 쪽은 다음 네 가지를 확인해야 한다.
- 빈 상태를 미리 검사해야 하는가?
- 제거 실패가 예외인가, 반환값인가?
- 최대 용량이 있는가?
- 가득 찼을 때 대기, 실패, 오래된 값 제거 중 무엇을 하는가?
특히 작업 큐에서 가득 찬 값을 조용히 버리면 '호출은 성공했는데 작업이 사라진' 것처럼 보인다. 반대로 무한히 받기만 하면 메모리가 먼저 바닥날 수 있다. FIFO인지 확인하는 일과 과부하 정책을 정하는 일은 함께 보되 서로 다른 문제로 다뤄야 한다.
성능은 동사보다 내부 구조에서 결정된다
append, pop, dequeue라는 이름 자체가 성능을 보장하지 않는다. 연속 메모리를 쓰는 배열형 리스트의 맨 앞 값을 제거하면 뒤의 원소를 당겨야 할 수 있다. Python의 리스트도 끝의 append()와 pop()은 빠르지만 pop(0)은 나머지 항목을 이동시키므로 큐 구현에 비효율적이다. 공식 문서는 양쪽 끝의 추가와 제거가 대략 O(1)인 collections.deque를 큐에 사용하도록 설명한다.
복잡도 표기를 볼 때도 구현과 실행 환경을 함께 확인해야 한다. 다른 언어의 연결 리스트, 원형 버퍼, 동시성 큐는 같은 FIFO 인터페이스를 제공하면서 내부 비용과 용량 정책이 다를 수 있다.
API 이름이 다르면 무엇을 확인해야 할까?
라이브러리마다 스택과 큐의 동사는 다르다. 어떤 큐는 enqueue/dequeue 대신 offer/poll을 쓰고, 어떤 배열은 push/shift를 조합한다. 이름이 익숙하다는 이유로 동작을 단정하지 말고 다음 계약을 읽는다.
- 값은 어느 끝에 추가되는가?
- 값은 어느 끝에서 제거되는가?
- 제거한 값을 반환하는가?
- 빈 상태와 가득 찬 상태를 어떻게 알리는가?
- 순서 보장에 우선순위나 동시성 조건이 붙는가?
이 다섯 가지가 같다면 메서드 이름이 달라도 같은 추상화를 구현할 수 있다. 반대로 이름이 queue여도 우선순위가 개입하면 단순 FIFO와 결과가 달라진다.
핵심 요약
push/pop은 스택의 같은 끝인 top을 사용해 C → B → A처럼 LIFO 순서를 만든다. enqueue/dequeue는 rear에 넣고 front에서 꺼내 A → B → C처럼 FIFO 순서를 만든다. 구현을 고를 때는 이름보다 삽입 위치, 제거 위치, 빈 상태, 용량 제한과 실제 시간 복잡도를 확인하자.