스택과 큐의 구현

본문

본문

매표소 대기 줄을 프로그램으로 흉내 내려고 리스트를 썼다. 새 손님은 append로 맨 뒤에 붙이고, 차례가 된 손님은 pop(0)으로 맨 앞에서 뺀다. 손님 1000명일 때는 잘 돌아갔는데, 10만 명을 넣자 프로그램이 거의 1분을 멈춰 있었다. 맨 뒤에서 빼는 pop()으로 바꾸면 순식간에 끝나지만, 그건 줄이 아니라 쌓아 둔 접시처럼 동작한다. 같은 리스트인데 앞에서 빼는 것과 뒤에서 빼는 것이 왜 이렇게 다를까?

원소의 수

그림 1. 원소 n개를 넣은 뒤 앞에서부터 모두 꺼낼 때, 리스트의 pop(0)과 앞 위치만 옮기는 원형 큐가 하는 일의 양(막대는 로그 길이).

먼저 알아야 할 것리스트와 인덱스(정보), 함수와 호출 스택(함수와 매개변수), 반복과 재귀(반복과 재귀 비교).

2.1.1스택과 큐

스택은 마지막에 넣은 것을 먼저 꺼내는 구조이고(후입 선출), 큐는 먼저 넣은 것을 먼저 꺼내는 구조이다(선입 선출). 스택은 쌓아 둔 접시, 함수의 호출 스택, 실행 취소 기록에 쓰이고, 큐는 대기 줄, 인쇄 대기열, 너비 우선 탐색에 쓰인다. 두 구조는 넣고 꺼내는 순서만 정한 추상 자료형이라, 같은 규칙을 여러 방법으로 구현할 수 있다. 그런데 구현 방법에 따라 같은 연산의 속도가 크게 다를 수 있다.

정리 2.1.1 리스트 끝과 앞의 연산

파이썬 리스트는 원소를 메모리에 빈틈없이 이어 저장한다. 맨 뒤에 붙이거나 맨 뒤에서 빼는 일은 다른 원소를 건드리지 않아 원소 수와 상관없이 빠르다. 그런데 맨 앞에서 빼면 나머지 원소를 모두 한 칸씩 앞으로 당겨야 해서, 원소가 \(m\)개이면 \(m\)번 옮긴다. 그래서 \(n\)개를 앞에서 모두 꺼내면 모두 \(\dfrac{n(n-1)}{2}\)번 옮긴다.

그림 1에서 원소 수를 바꾸어 보자. 1000명이면 pop(0)이 약 50만 번 옮겨도 금방 끝난다. 10만 명이면 약 50억 번으로, 1초에 1억 번 옮긴다 해도 50초가 걸린다. 앞 위치를 가리키는 변수 하나만 옮기는 원형 큐나 파이썬의 deque를 쓰면 10만 번이면 되어 1000분의 1초 남짓이다. 그래서 스택은 리스트의 끝을 쓰면 충분하지만, 큐는 앞에서 빼는 일이 많으므로 다른 구현을 써야 한다.¹

2.1.2원형 큐

원형 큐는 크기가 정해진 리스트의 양 끝을 이어 둥글게 쓴다고 생각하는 구현이다. 맨 앞 원소의 위치(front)와 다음에 넣을 위치(rear)를 변수로 기억해 두고, 넣을 때는 rear 자리에 놓고 rear를 한 칸 옮기며, 뺄 때는 front 자리의 값을 꺼내고 front를 한 칸 옮긴다. 끝에 이르면 나머지 연산으로 다시 0번 자리로 돌아간다. 원소는 한 번도 옮겨지지 않으므로 넣기와 빼기가 모두 원소 수와 상관없이 빠르다. 다만 리스트의 크기를 미리 정해야 하고, 꽉 차면 더 큰 리스트로 옮겨야 한다.

그림 2. 같은 규칙의 자료 구조도 구현에 따라 연산의 비용이 다르다.

2.1.3예제 풀이

예제 2.1.2

크기 5인 원형 큐에 front = 0, rear = 0에서 시작해 A, B, C를 넣고, 하나를 빼고, D, E, F를 넣었다. 각 단계의 front와 rear 값과, 마지막에 큐에 남은 원소를 앞에서부터 쓰여라. 위치는 (위치 + 1) % 5로 옮긴다.

A, B, C를 넣으면 0, 1, 2번 자리에 놓이고 rear는 3이 된다. 하나를 빼면 0번 자리의 A가 나오고 front는 1이 된다. D를 넣으면 3번 자리에 놓이고 rear는 4, E를 넣으면 4번 자리에 놓이고 rear는 (4 + 1) % 5 = 0이 된다.

F를 넣으면 0번 자리, 곧 A가 빠져 비어 있던 자리에 놓이고 rear는 1이 된다. 이제 front와 rear가 모두 1이므로 큐가 꽉 찼다. 남은 원소는 front부터 B, C, D, E, F이다. 원소는 한 번도 자리를 옮기지 않았고, front와 rear 두 변수만 움직였다. 그래서 원형 큐는 원소가 아무리 많아도 넣고 빼는 데 같은 시간이 든다.

아래 탐구 카드에서 리스트로 스택과 큐를 직접 만들고, 구현에 따라 실행 시간이 어떻게 달라지는지 재어 보자.

원형 큐에서는 꽉 찬 상태와 빈 상태가 모두 front = rear가 되어 구별되지 않는다. 그래서 한 칸을 일부러 비워 두거나, 원소 수를 따로 세는 변수를 둔다.

마무리

스택은 나중에 넣은 것을, 큐는 먼저 넣은 것을 먼저 꺼내는 추상 자료형이며, 같은 규칙도 구현에 따라 속도가 크게 다르다. 리스트는 끝에서 넣고 빼기는 빠르지만 앞에서 빼면 나머지를 모두 당겨야 해서, 큐를 리스트의 pop(0)으로 만들면 일이 원소 수의 제곱으로 늘어난다. 그래서 처음 질문의 큐는 손님이 많아지면 앞에서 뺄 때마다 수만 명을 한 칸씩 당기느라 느려지고, 원형 큐로 바꾸면 해결된다.

탐구 1

스택과 큐를 리스트로 만들면 무엇이 다를까?

스택(LIFO) · 큐(FIFO) · 배열과 연결 리스트 · 원형 큐

원소 수: 0
연산 횟수: 0
이번에 옮긴 원소: 0
누적 옮긴 원소: 0

‘옮긴 원소’는 꺼내기 때문에 메모리 안에서 자리를 옮겨야 하는 원소 수이다. 원형 큐는 칸 8개, 그림의 리스트는 칸 11개까지만 그린다.

질문은행 번호표는 먼저 뽑은 사람이 먼저 불리고, 웹 브라우저의 ‘뒤로 가기’는 가장 최근에 본 페이지부터 돌아간다. 두 규칙을 모두 파이썬 리스트로 만들 수 있을까? 만든다면 효율도 같을까?
복원파이썬 리스트는 원소를 메모리에 차례로 이어 놓은 배열(순차 구조)이다. 인덱스로 어느 칸이든 바로 찾을 수 있고, 맨 뒤에 붙이거나 빼는 일은 빠르다. 그러나 앞이나 중간에서 빼면 뒤의 원소들을 한 칸씩 당겨야 한다.
설명스택은 한쪽 끝(top)에서만 넣고(push) 꺼내는(pop) 구조로, 나중에 넣은 것이 먼저 나온다(후입선출, LIFO). 리스트의 맨 뒤를 top으로 쓰면 append와 pop()만으로 원소 이동 없이 구현된다. 큐는 뒤(rear)에 넣고(enqueue) 앞(front)에서 꺼내는(dequeue) 구조로, 먼저 넣은 것이 먼저 나온다(선입선출, FIFO). 리스트로 큐를 만들어 pop(0)으로 꺼내면 남은 원소를 모두 옮겨야 한다. 이를 피하는 방법이 두 가지 있다. 원형 큐는 크기가 정해진 배열에서 front 번호만 옮기고, 끝에 닿으면 % 연산으로 0번 칸으로 돌아간다. 연결 리스트는 각 노드가 다음 노드를 가리키게 하여, head를 다음 노드로 바꾸기만 하면 꺼내기가 끝난다.
연결실제로 문제를 풀 때는 라이브러리를 쓴다. 스택은 리스트 그대로, 큐는 collections.deque의 append와 popleft를 쓴다. deque는 양쪽 끝에서 넣고 빼는 일을 원소 이동 없이 처리한다. ‘무엇을 하는가’(push, pop, enqueue, dequeue)와 ‘어떻게 구현하는가’를 나누어 생각하는 것을 추상 자료형이라 한다.
적용네 가지 방식에서 각각 7개를 넣은 뒤 모두 꺼내고, 누적 옮긴 원소 수를 비교해 보자. 리스트 pop(0) 큐에서 n개를 넣고 모두 꺼내면 옮기는 원소는 몇 개인가? 원형 큐에서 6개 넣고 4개 꺼낸 뒤 다시 5개를 넣으면 rear는 몇 번 칸을 지나가는가?
판단원형 큐에서 front와 다음 rear가 같은 칸을 가리키는 경우는 큐가 비었을 때와 꽉 찼을 때 두 가지이다. 그래서 위 코드는 size를 따로 센다(한 칸을 늘 비워 두는 방법도 있다). 연결 리스트는 원소를 옮기지 않는 대신 노드마다 참조를 하나 더 저장하고, i번째 원소를 바로 찾을 수 없다. 어떤 구현이든 비어 있을 때 꺼내면 오류가 나므로 먼저 확인해야 한다.

확인조건이 달라지면

원소 10,000개가 들어 있는 리스트 큐에서 pop(0)으로 원소를 모두 꺼낸다. 그동안 자리를 옮기는 원소는 모두 몇 개쯤일까?

읽기 2

스택과 큐는 어디에 쓰이고, 무엇으로 구현할까?

읽기 · 추상 자료형 · 연산 비용 · deque

스택과 큐는 “넣고 꺼내는 순서”만 정한 규칙이다. 규칙은 같아도 구현에 따라 속도와 메모리가 달라진다. 실제 프로그램에서는 무엇을 골라 써야 할까?

1순서 규칙이 쓰이는 곳

	스택 (후입선출)	큐 (선입선출)
규칙	가장 최근 것을 먼저 처리	가장 오래 기다린 것을 먼저 처리
예	함수 호출 스택, 실행 취소(Ctrl+Z), 브라우저 뒤로 가기, 괄호 짝 검사, 수식 계산, 미로의 되돌아가기	프린터 대기열, 키보드 입력 버퍼, 운영체제의 작업 대기열, 메시지 처리, 가까운 곳부터 넓혀 가는 탐색(너비 우선 탐색)
핵심 연산	push, pop, peek(맨 위 보기), is_empty	enqueue, dequeue, peek(맨 앞 보기), is_empty

이렇게 연산의 이름과 뜻만 정하고 내부 구현은 감춘 자료 구조를 추상 자료형이라 한다. 쓰는 쪽은 연산만 알면 되고, 구현은 더 빠른 것으로 바꿔도 프로그램의 나머지는 고칠 필요가 없다.

2구현에 따른 연산 비용

n은 들어 있는 원소 수이다. ‘한 번’은 원소 수와 관계없이 거의 일정한 시간, ‘n에 비례’는 원소가 많을수록 오래 걸린다는 뜻이다.

구현	뒤에 넣기	뒤에서 꺼내기	앞에서 꺼내기	i번째 보기
파이썬 list	한 번 (평균)	한 번	n에 비례	한 번
원형 배열	한 번 (가득 차면 불가)	한 번	한 번	한 번
연결 리스트	한 번 (tail 유지)	단일 연결이면 n에 비례	한 번	n에 비례
collections.deque	한 번	한 번	한 번	양 끝은 빠르고 가운데는 느림

list의 append가 ‘평균’ 한 번인 까닭은, 미리 잡아 둔 칸이 다 차면 더 큰 공간을 잡아 전체를 옮기기 때문이다. 이 일은 가끔만 일어나서 평균을 내면 한 번 정도의 비용이 된다.

3문제를 풀 때는 라이브러리로

stack = []                   # 스택: 리스트 그대로
      stack.append('a'); stack.append('b')
      stack.pop()                  # 'b'

      from collections import deque
      q = deque()                  # 큐: deque
      q.append('a'); q.append('b')
      q.popleft()                  # 'a'
      len(q) == 0                  # 비었는지 확인 (또는 not q)

원리를 익힐 때는 리스트로 직접 만들어 보고, 실제 문제를 풀 때는 이렇게 검증된 라이브러리를 쓴다. queue.Queue도 있지만, 이것은 여러 스레드가 함께 쓰도록 잠금 장치를 더한 것이라 한 프로그램 안의 일반적인 큐로는 deque가 알맞다.

판단“연결 리스트가 배열보다 항상 빠르다”는 틀린 말이다. 연결 리스트는 앞에서 넣고 빼기가 빠른 대신, i번째 원소를 찾으려면 head부터 따라가야 하고 노드마다 참조를 저장할 메모리가 더 든다. 어떤 연산을 자주 하는지에 따라 알맞은 구현이 달라진다.

확인조건이 달라지면

문서 편집기의 ‘실행 취소’ 기록을 저장하려 한다. 기록은 최대 100개만 남기고, 넘치면 가장 오래된 기록을 버린다. 가장 알맞은 구현은?