A를 넣고 B를 넣은 뒤 하나를 꺼냅니다. 이어 C를 넣고 또 하나를 꺼낸다면, 마지막에 무엇이 남을까요?
스택에는 A가, 큐에는 C가 남습니다. 꺼낸 값의 순서도 서로 달라요. 마지막 상태만 보고 입력 문자 A·B·C를 역순 또는 그대로 나열하면 중간에 삭제된 원소를 다시 포함할 수 있습니다.
스택은 마지막에 들어온 원소를 먼저 꺼내는 LIFO, 큐는 먼저 들어온 원소를 먼저 꺼내는 FIFO입니다.1 이 순서를 같은 연산에 적용해보겠습니다.
삭제한 값은 다음 상태에 없습니다
아래 표는 스택을 아래→위, 큐를 앞→뒤로 적었습니다. 물리적인 메모리 주소의 방향을 나타내는 표는 아니에요.
| 연산 | 스택에 남은 값 | 큐에 남은 값 |
|---|---|---|
| A 넣기 | A | A |
| B 넣기 | A, B | A, B |
| 하나 꺼내기 | A | B |
| C 넣기 | A, C | B, C |
| 하나 꺼내기 | A | C |
스택의 첫 삭제는 위의 B를 꺼냈습니다. 큐의 첫 삭제는 앞의 A를 꺼냈어요. 그 뒤 C가 들어왔을 때 이미 다른 원소가 남아 있었기 때문에 마지막 결과도 갈립니다.
꺼낸 값만 나열하면 스택은 B, C이고 큐는 A, B입니다. 남은 값의 표와 출력한 값의 목록은 같은 자료가 아니에요. 문제에서 pop의 반환값을 출력하라고 했는지, 연산 뒤 내부 상태를 쓰라고 했는지 읽어야 합니다.
이 표를 코드에 옮길 때도 어느 끝에서 원소를 제거했는지 보입니다.
from collections import deque
stack = []
queue = deque()
stack.append("A")
stack.append("B")
print(stack.pop()) # B
stack.append("C")
print(stack.pop()) # C
print(stack) # ['A']
queue.append("A")
queue.append("B")
print(queue.popleft()) # A
queue.append("C")
print(queue.popleft()) # B
print(list(queue)) # ['C']
파이썬 리스트의 append와 pop은 오른쪽 끝을 스택의 top으로 쓸 수 있습니다. deque의 append와 popleft는 뒤에 넣고 앞에서 꺼내는 큐 동작에 맞아요.12 방향은 구현에서 정했지만 먼저 나갈 원소의 관계는 LIFO와 FIFO로 남습니다.
이름이 비슷한 메서드도 꺼내는 끝이 달라요
deque에는 pop과 popleft가 모두 있습니다. queue라는 변수 이름을 붙였다고 pop이 자동으로 FIFO 삭제가 되는 것은 아닙니다.
from collections import deque
q = deque(["A", "B"])
print(q.pop()) # B
print(list(q)) # ['A']
pop은 오른쪽 끝의 B를 꺼냅니다. popleft를 썼다면 왼쪽 끝의 A였겠죠. 자료구조의 의도는 이름이 아니라 실제 연산으로 구현됩니다.
맨 위나 맨 앞을 읽기만 하는 연산도 삭제와 다릅니다. stack[-1]로 B를 확인하고 C를 넣었다면 스택은 A, B, C예요. 읽은 순간 B를 지웠다고 계산하면 이후 상태가 어긋납니다.
빈 리스트나 빈 deque에서 원소를 꺼내면 파이썬에서는 IndexError가 발생합니다.12 추상 자료구조 문제에서 별도의 오류 처리를 정의했다면 그 명세를 따라야 해요. ‘빈 상태’라는 말만으로 반환값을 마음대로 정할 수는 없습니다.
대기열이 꽉 찼을 때도 명세가 필요해요
deque에 maxlen을 주면 길이가 제한됩니다. 제한 길이가 꽉 찬 뒤 append로 새 값을 넣으면 반대쪽 끝의 값이 버려집니다.2
from collections import deque
recent = deque(["A", "B"], maxlen=2)
recent.append("C")
print(list(recent)) # ['B', 'C']
A가 처리 완료되어 나간 것이 아닙니다. 이 컨테이너의 길이 제한 때문에 제거된 거예요. 처리하지 않은 작업을 모두 보존해야 하는 대기열이라면 이 동작을 단순히 ‘큐니까 FIFO’라고 설명하는 것으로 충분하지 않습니다.
스택·큐의 순서를 배우는 단계와, 용량 초과·빈 상태에서 무엇을 할지 정하는 단계가 이어지는 지점입니다. 일반적인 LIFO·FIFO 정의에는 모든 구현의 용량 처리까지 자동으로 들어 있지 않습니다.