스택은 데이터를 임시 저장할 때 사용하는 자료구조로 데이터의 입력과 출력 순서는 후입선출(last-in-first-out)로 처리된다. 파이썬은 스택 자료형을 따로 지원하지 않지만 리스트가 사실상 스택의 모든 연산을 지원한다.

1. 스택

스택에 데이터를 넣는 작업을 push라고 하고, 스택에서 데이터를 꺼내는 작업을 pop이라고 한다. 데이터를 넣고 꺼내는 작업을 맨 위부터 수행하며 이 윗부분을 top이라고 하고, 아래부분을 bottom이라고 한다.

2. 스택의 시간 복잡도

Insertion/Deletion : O(1)

스택의 원소 삽입/삭제는 맨 위의 원소에 대해서만 이루어지므로 O(1)이다. 즉, 자료의 개수가 몇 개인지와 같은 다른 어떤 사항도 고려할 필요 없이 그냥 새로운 자료를 기존의 자료 맨 위에 올리기만 하면 된다. 자료를 삭제할 때도 마찬가지로 자료의 개수가 몇 개이던지 그냥 맨 위에 있는 자료를 pop하면 되므로 자료의 삭제 또한 O(1)으로 표기할 수 있다.

Search: 최소 O(1), 최대 O(N)

검색을 시작하면 맨 위 부터 맨 아래까지 순차적으로 검색하여 자료를 찾는다. 운이 좋게 가장 위의 데이터가 우리가 찾는 것이면 단 한 번의 검색으로 답을 찾을 수 있겠지만 O(1), 만약 맨 아래 데이터가 우리가 찾는 것이라면 맨 마지막까지 검색 과정을 거쳐야할 것이다. 그러므로 스택의 검색 횟수는 가장 최악의 경우인 O(n)으로 표기할 수 있다.

3. 스택의 활용

스택은 재귀 알고리즘에서 유용하게 사용되고, DFS에 사용된다.

4. Stack with Python

스택의 기본연산은 다음과 같다.

• push(): 스택에 원소를 추가
• pop(): 스택 가장 위에 있는 원소를 삭제하고 그 원소를 반환
• peek(): 스택 가장 위에 있는 원소를 반환 (삭제하지는 않음)
• empty(): 스택이 비어있다면 1, 아니면 0을 반환

push는 list.append(x), pop은 list.pop()을 사용하면 된다. pop()은 다음과 같이 활용할 수 있다.

pop()

pop()은 리스트의 맨 마지막 요소를 돌려주고 그 요소는 삭제한다.

a = [1,2,3]
a.pop()
# 3

a
# [1, 2]

pop(x)

pop(x)는 리스트의 x번째 요소를 돌려주고 그 요소는 삭제한다.

a = [1,2,3]
a.pop(1)
# 2

a
# [1, 3]

이를 활용해 스택의 기본연산을 구현하면 다음과 같다.

class Stack:

    def __init__(self):
        self.data = []

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

    def push(self, item):
        self.data.append(item)

    def pop(self):
        return self.data.pop()

    def peek(self):
        return self.data[-1]
    
    def isEmpty(self):
        return self.size() == 0

위처럼 직접 클래스를 구현해도 되고, 필요할 때 알맞는 함수를 가져다가 써도 된다.

stack = []
stack.append(5)
stack.append(2)
stack.append(3)
stack.pop() # 가장 오른쪽에서 하나를 꺼내기
stack.append(7)
stack.pop()

print(stack[::-1])  #최상단의 원소부터 출력
print(stack)  # 최하단의 원소부터 출력

# [2,5]
# [5,2]

아래는 정수를 저장하는 스택을 구현하고 입력으로 주어지는 명령을 처리하는 프로그램을 작성한 것이다.

import sys

n = int(input())
stack = []

for _ in range(n):
    cmd = sys.stdin.readline().split()
    
    if cmd[0] == 'push':
        stack.append(cmd[1])
    elif cmd[0] == 'pop':
        if len(stack) == 0:
            print(-1)
        else:
            print(stack.pop())
    elif cmd[0] == 'size':
        print(len(stack))
    elif cmd[0] == 'empty':
        if not stack:
            print(1)
        else:
            print(0)
    elif cmd[0] == 'top':
        if not stack:
            print(-1)
        else:
            print(stack[-1])