Stack

스택(stack)은 배열의 끝에서만 데이터를 접근할 수 있는 선형 자료구조이다. 스택은 배열 인덱스 접근이 제한되며, 후입선출(last in, first out, LIFO) 구조이다. 요즘에는 없지만, 어렸을 때 택시에는 동전케이스가 항상 달려있었다. 동전 크기의 입구에 동전을 넣어두고 그 입구를 통해서 동전을 다시 꺼내는 방식의 케이스인데, 스택의 동작과 똑같다. 스택의 시간복잡도는 O(1)이며, 동작은 다음과 같다.

• push : 스택 맨 끝(혹은 맨 위)에 항목을 삽입한다.
• pop : 스택 맨 끝 항목을 반환하는 동시에 삭제한다.
• top/peek : 스택 맨 끝 항목을 조회한다.
• empty : 스택이 비어있는지 확인한다.
• size : 스택의 크기를 확인한다.

Python에서 리스트를 이용한 작업을 할 때, append()와 pop() 메서드를 많이 이용하는데, 이를 이용하여 스택을 구현할 수 있다.

class Stack(object) :
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return not bool(self.items)

    def push(self, value):
        self.items.append(value)

    def pop(self):
        value = self.items.pop()
        if value is not None :
            return value
        else :
            print('Stack is empty.')

    def size(self):
        return len(self.items)

    def peek(self):
        if self.items :
            return self.items[-1]
        else :
            print('Stack is empty.')

    def __repr__(self):
        return repr(self.items)

혹은 노드의 컨테이너로 스택을 구현할 수도 있다.

class Node(object) :
    def __init__(self, value = None, pointer = None):
        self.value = value
        self.pointer = pointer

class Stack(object) :
    def __init__(self):
        self.head = None
        self.count = 0

    def isEmpty(self):
        return not bool(self.head)

    def push(self, item):
        self.head = Node(item, self.head)
        self.count += 1

    def pop(self):
        if self.count > 0 and self.head :
            node = self.head
            self.head = node.pointer
            self.count -= 1
            return node.value
        else :
            print('Stack is empty.')

    def peek(self):
        if self.count > 0 and self.head :
            return self.head.value
        else :
            print('Stack is empty.')

    def size(self):
        return self.count

    def _printList(self):
        node = self.head
        while node :
            print(node.value, end=' ')
            node = node.pointer
        print()

스택을 구현하기 위한 코드는 복잡해 보이지만, 스택의 개념을 잘 이해한다면 쉽게 구현할 수 있다. 결국 핵심은 후입선출이라는 점이다. 실제로 스택은 깊이 우선 탐색(DFS)에서 유용하게 사용된다.

출처: 파이썬 자료구조와 알고리즘, 미아 스타인 지음, 최길우 옮김