이번 글에서는 스택(stack)에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김황남 교수님 강의와 위키피디아를 정리하였음을 먼저 밝힙니다. 파이썬 코드는 이곳을 기본으로 하되 조금 수정하였습니다. 그럼 시작하겠습니다.

concept

스택이란 목록 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 자료구조의 일종입니다. 이때 자료를 넣는 것을 ‘밀어넣는다’는 의미의 푸시(push), 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 합니다. 팝으로 꺼내진 자료는 가장 최근에 보관한 자료가 됩니다(Last In First Out, LIFO) 책이 쌓여있는(stack) 걸 상상하면 직관적으로 이해할 수 있는데요. 스택은 책더미 속에서 가장 나중에 올려놓은 책부터 꺼낼 수 있는 것과 같은 이치입니다.

6, 4, 2를 차례로 푸시하고, 두번 팝 한 다음에 7을 푸시한다고 가정해보겠습니다. 다음 그림과 같습니다.

operation

스택의 핵심 연산(operation)은 푸시와 팝입니다. 푸쉬를 구현한 파이썬 코드는 다음과 같습니다.

class Stack(object):
    def __init__(self, limit = 10):
        self.stack = []
        self.limit = limit

    # for printing the stack contents
    def __str__(self):
        return ' '.join([str(i) for i in self.stack])

    # for pushing an element on to the stack
    def push(self, data):
        if len(self.stack) >= self.limit:
            print('Stack Overflow')
        else:
            self.stack.append(data)

위 코드상으로는 스택 길이를 limit라는 변수로 제어하고 있습니다. 물론 스택 길이를 굳이 제어하지 않아도 됩니다. 정해진 스택 길이 limit를 만족하는 상태인 스택에 추가 요소를 푸쉬할 경우 스택 오버플로우(stack overflow) 경고메세지를 출력합니다.

팝을 구현한 파이썬 코드는 다음과 같습니다. 스택 길이가 0 이하라면 팝을 할 수 없으므로 스택 언더플로우(stack underflow) 문제가 발생합니다. 이 코드에선 -1을 출력하도록 했습니다.

    # for popping the uppermost element
    def pop(self):
        if len(self.stack) <= 0:
            return -1
        else:
            return self.stack.pop()

스택의 핵심 연산은 아니지만 정의해놓으면 편리한 것이 바로 픽(peek)입니다. 스택의 경우 그 정의상 팝을 해야만 스택에 최근 저장된 자료를 확인할 수 있는데요. 픽은 팝을 하지 않고도 최근 저장된 자료를 엿볼(peek) 수 있습니다.

    def peek(self):
        if len(self.stack) <= 0:
            return -1
        else:
            return self.stack[len(self.stack) - 1]

파이썬 코드에서 이미 눈치 채셨겠지만 스택은 리스트, 연결리스트 등 다양한 자료구조로 구현이 가능합니다. 위 파이썬 코드의 경우 리스트를 활용해 스택이 구현됐습니다. 리스트를 활용할 경우 푸쉬 연산은 리스트에 새 자료를 붙이는(append) 형태로, 팝 연산은 파이썬 자체의 팝(pop) 연산이 적용됐습니다. 그런데 스택의 정의에만 맞다면 위 형태 말고도 다양하게 구현할 수 있습니다. 리스트든 연결리스트든 팝, 푸쉬, 픽 연산의 계산복잡성은 $O(1)$입니다.

활용 : 재귀함수

스택은 프로그래머도 모르는 사이에 여러 곳에서 쓰이고 있습니다. 재귀함수 호출이 모두 스택 형태로 이뤄지게 됩니다. 이와 관련해 다음 그림을 보겠습니다.

함수 $A$를 실행하다가 $B$를 호출하고, 다시 $B$를 실행하다가 $B$를 호출하고, $C$와 $D$도 마찬가지의 과정을 거쳤다고 칩시다. 그러면 함수 실행 결과를 반환하는 과정은 호출 순서의 정반대가 됩니다. 다시 말해 $D$의 연산 결과를 받아야지만 $C$가 이를 바탕으로 계산을 마칠 수 있고, 이는 $B$와 $A$도 마찬가지입니다.

각 함수의 메모리 주소값이 스택에 저장되어 있고, 스택은 Last In First Out 원칙을 따르기 때문에 함수 결과의 반환 순서는 호출 결과의 반대가 되는 것입니다.

활용 : 사칙연산

숫자와 숫자 사이에 연산자를 넣어 표기하는 방법을 중위표기법(infix notation)이라 합니다. 예컨대 아래의 표기는 2와 3을 ‘더한다’는 뜻이 됩니다.

2 + 3

중위표기법은 괄호 연산자가 필요없는 전위표기법(+ 2 3)이나 후위표기법(2 3 +)과는 다르게 괄호가 매우 중요합니다. 연산 수행 순서를 명시적으로 나타내야 할 때가 발생하기 때문이죠. 예컨대 아래의 표기에서는 2와 3을 더하는 연산이 먼저 수행됩니다.

(2 + 3) × 4

그런데 후위표기법에서는 위와 같은 식을 아래와 같이 쓰게 돼 괄호가 필요 없습니다.

2 3 + 4 ×

연산의 우선순위(the priority of operands, precednece rule)은 모호하게 해석할 수 있는 수식에서 어느 연산을 먼저 계산할 것인가를 결정하는 명시적인 규칙입니다. 중위표기법에서는 다음과 같은 순위가 표준적으로 쓰입니다. 자세한 내용은 이곳을 참고하시면 좋을 것 같습니다.

(, ) > ×, / > +, -

중위표기법은 사람에게는 친숙하지만 컴퓨터로 구문분석하기가 어렵습니다. 이 때문에 프로그램 내부에서는 연산자를 연산 대상의 뒤에 쓰는 후위표기법(postfix notation)이 쓰인다고 합니다. 후위표기법은 괄호가 없고 수식 계산시 식을 앞에서 읽어 나가면서 차례대로 처리를 하면 됩니다. 이 때 쓰이는 것이 바로 스택입니다. 컴퓨터가 중위표기법으로 표현된 수식을 계산하는 과정은 크게 두 단계로 나눠서 생각해볼 수 있습니다.

1. 전위표기법으로 표현된 수식을 후위표기법으로 변환
2. 후위표기법으로 표현된 수식을 계산

중위표기법으로 쓰인 다음 식을 계산한다고 칩시다. 이를 후위표기법으로 변환하면 다음과 같습니다.

1번 과정의 일반적 절차는 다음과 같습니다.

• 계산대상 숫자가 나오면 output 변수에 저장한다.
• 왼쪽 괄호 $($가 나오면 스택에 푸쉬(저장)한다.
• 오른쪽 괄호 $)$가 나오면 스택에 이미 저장돼 있는 왼쪽 괄호 $($ 사이에 있는 모든 요소를 팝을 한다.
• 덧셈, 곱셈기호 등 연산자가 나오면 해당 연산자보다 연산 우선순위가 낮거나 같은 연산자가 나올 때까지 스택에서 팝을 해서 output에 저장하고, 해당 연산자를 스택에 푸쉬한다.
• 식의 끝에 다다르면 스택에 있는 모든 요소를 팝을 한다.

위 절차에 따라 위 식을 후위표기법으로 변환해 보겠습니다. 아래 표와 같습니다.

후위표기법으로 표현된 수식을 계산하는 2번 과정의 일반적 절차는 다음과 같습니다.

• 숫자를 만나면 스택에 푸쉬한다.
• 연산자를 만나면 두 개 요소를 팝을 하고, 두 요소에 연산자에 해당하는 연산을 적용한 후, 그 값을 다시 푸쉬한다.

예컨대 다음과 같은 식을 계산한다고 칩시다. (답은 40)

중위표기법 : 5×4+6+7×2

후위표기법 : 54×6+72×+

1번 작업의 계산복잡성은 $O(n)$, 2번 작업 역시 $O(n)$이 됩니다. 연산자와 숫자 개수를 모두 합쳐 $n$개일 경우 모든 요소를 한번씩은 다 훑어야 하기 때문입니다.