5.1.1 스택 구현: 동적 배열을 이용하여 구현하기

스택을 어떻게 구현할지 고민해 보기 전에 먼저 파이썬에서는 어떻게 스택을 사용하고 있는지 살펴보겠습니다. 파이썬의 자료 구조에는 스택이라는 모듈이 따로 없습니다. 뒤에 살펴볼 큐는 모듈을 지원하는데 스택은 지원하지 않는다니 뭔가 억울합니다. 파이썬 공식 문서에서 그 이유를 이렇게 설명하고 있습니다.

“The list methods make it very easy to use a list as a stack, where the last element added is the first element retrieved (“last-in, first-out”). To add an item to the top of the stack, use append(). To retrieve an item from the top of the stack, use pop() without an explicit index.”

간단히 말하면 파이썬에서 스택은 리스트를 이용해서 간단하게 사용할 수 있는데 ADT의 push() 대신 리스트의 append()를, ADT의 pop() 대신 리스트의 매개변수 없이 사용하는 pop()을 사용하라고 합니다. 조금만 생각해 보면 이는 꽤나 합리적입니다. 3장의 동적 배열에서 맨 마지막에 데이터를 추가하거나 삭제하는 연산은 빅오가 O(1)이라고 했습니다. 이를 조금만 응용하면 이렇습니다. 리스트의 맨 마지막 요소를 top이라고 할 때, 리스트의 맨 마지막에 요소를 추가하는 연산은 push()가 되고 리스트의 맨 마지막에 있는 요소를 빼내는 것은 pop()이 되지요. push와 pop이 모두 O(1)이므로 매우 합리적입니다. 하지만 아무런 추상화 없이 리스트를 스택으로 사용한다면 가독성은 매우 떨어질 것입니다. 코드를 읽는 프로그래머들은 이 리스트가 동적 배열로서 리스트인지 스택으로서 리스트인지 코드를 꼼꼼히 분석해야 하기 때문입니다.