💡파이썬 스택(Stack) 이론 및 예제

스택(Stack)이란?

스택은 흔히 두 가지 의미로 사용됩니다. 자료구조로써의 스택, 프로세스 메모리 구조로써의 스택 메모리입니다.

본 포스트에서는 자료구조로써의 스택에 대한 내용을 다루고 있으니, 스택 메모리에 대해 궁금하신 분은 저의 이전 포스팅을 참고해주세요. (무려 2년 3개월 전 포스팅... 시간 참 빨라요)

돌맹이 Stack

• 알고리즘 코딩테스트에서 가장 자주 활용되는 자료구조 중 하나 (DFS문제에서 자주 활용)
• 가장 나중에 들어온 데이터를 가장 먼저 처리하는 후입선출(LIFO, Last In First Out) 방식
• 입출력이 한쪽에서만 일어남
• 스택의 크기가 제한되어 있음 - 데이터의 크기만큼 크기가 결정됨. 따라서 C에서는 push, pop 할때마다 메모리 재할당(realloc)이 필요하지만 파이썬에서는 신경 안써도 됩니다. 파이썬 메모리 관리자가 알아서 해줍니다.

복잡하면 그냥 위 이미지의 돌맹이 탑을 연상하면 됩니다. (프링글스에도 많이 비유되곤 합니다.)

(돌탑을 무너뜨리지 않으려면) 중간의 돌맹이를 바로 빼올 수는 없습니다.

중간의 돌맹이를 빼오기 위해서는, 가장 위의 돌부터 하나씩 빼야 합니다. 한꺼번에 집어서 다 빼도 되긴 하죠

사용자는 가장 위의 데이터(돌맹이)만 집을 수 있고, 새로운 데이터 또한 가장 위에만 쌓을 수 있습니다.

사실 이는 잘못된 비유입니다. 엄밀히 말하면 스택은 위에서 아래로 쌓는 것....(이또한 위의 스택 메모리 포스팅 참조)

 

파이썬으로 스택 구현하기

파이썬에서 스택을 구현하는 방법은 대표적으로 다음 두 가지 정도가 있습니다.

• list 활용(강추★) : 별도의 import가 필요 없고, 가장 간단하고, 스택답게 잘 활용하면 아래 자료형과 성능 차이도 거의 없습니다. 그리고 가끔 야매로 중간값 활용할 수 있습니다.
• deque 활용 : 다음에 포스팅할 Queue(큐)로 많이 활용되나, 양방향 처리를 지원하므로 Stack으로도 활용 가능

list로 스택을 구현하는 방법도 두 가지가 있습니다.

• class로 구현해서 사용

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

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

    def pop(self):
        if len(self.stack) == 0:
            return None
        return self.stack.pop()

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

    def is_empty(self):
        return len(self.stack) == 0

 

• 그냥 사용

a = []			# a = Stack()
a.append('a')	# a.push('a')
a.pop()			# a.pop()
a[-1]			# a.peek()
len(a) == 0		# a.is_empty()

 

그냥 사용시, 빈 list를 pop하면 에러가 발생하기 때문에 pop할때마다 len(a) != 0 확인을 해주어야 합니다.

IndexError

따라서 스택을 자주 사용하는 프로그램이라면 클래스 구현, 아니라면 그냥 쓰면 되겠습니다.

 

예제

boj의 오큰수 문제가 스택을 활용한 유명한 문제 중 하나입니다.

풀이 방법은 다양하겠지만, 스택 활용을 잘 생각해보면 아주 간단히 풀 수 있는(15줄 이내) 문제이니 풀어보시고 다른 사람들의 풀이도 꼭 참고해보시길 바랍니다.