[자료구조][파이썬/Python] 스택(Stack)

스택(Stack)

• 스택(Stack)은 데이터 값을 저장하는 기본적인 구조로, 일차원의 선형 자료구조이다.
• 기본적으로 값을 저장하는 연산 push와 저장된 값을 꺼내는 연산 pop이 제공되어야 한다.
• 부가적으로 스택의 길이를 반환하는 연산이나 스택이 비어있는지 확인하는 연산, 스택의 가장 위에 있는 값이 무엇인지 확인하는 연산을 추가할 수도 있다.
• 가장 나중에 들어간 값이 가장 먼저 나오게 되는 원칙(Last In First Out, LIFO)을 따른다.

 

클래스로 구현하기

일반적으로 클래스로 구현하는 방법은 (1) 양방향 연결리스트(Doubly Linked List)를 통해 구현하는 방법, (2) Python 내 리스트 메서드로 구현하는 방법이 존재한다. 다만, 실제로 코딩테스트 문제를 풀 때 어떻게 빠르게 스택을 사용할 수 있을지에 초점을 두기 때문에 클래스로 구현하는 것은 생략하도록 하겠다. 바로 아래에 나와 있는 pythonds 모듈 관련 내용에서 링크를 클릭하면 (2)에 대한 코드가 나오니 참고하면 좋을 것 같다.

 

Python의 모듈을 이용하기

python 내장 모듈에는 stack을 위한 기능이 따로 없다고 알고 있다. 물론 모듈 queue에서 LifoQueue를 사용한다면 스택과 동일한 기능을 큐를 만들 수 있으나 이는 스레드 환경을 위한 모듈로, 일반적인 코딩을 할 때에는 그렇게 권장하지 않는다. 대신 외장 모듈인 pythonds이 존재한다. 추상화되어 있는 스택을 자세히 살펴보고 싶은 사람은 여기서 확인해보자. 해당 모듈에서는 스택을 리스트로 구현했다. 솔직히 이건 코딩테스트에서는 써먹을 수 없을 것 같고(사실 그럴 필요도 없고), 학부생들이 과제할 때 참고 정도는 할 수 있을 것 같다.

 

제공하는 연산은 다음과 같다.

• 'isEmpty' : 스택이 비어있는지 확인하는 연산. 비어있다면 True를, 비어있지 않다면 False를 return
• 'items' : 스택에 어떤 요소들이 들어있는지 출력해주는 연산. 리스트 형태로 출력
• 'peek' : 스택의 최상단(리스트로 생각하면 리스트의 가장 오른쪽)에 있는 요소를 출력해주는 연산
• 'pop' : 스택의 최상단(리스트로 생각하면 리스트의 가장 오른쪽)에 있는 요소를 꺼내고 return해주는 연산
• 'push' : 스택에 새로운 요소를 저장하는 연산
• 'size' : 스택에 요소가 몇 개 들어있는지 출력해주는 연산

# 모듈 사용 예시
from pythonds.basic.stack import Stack
s = Stack()

print(dir(s)) # Stack에서 사용할 수 있는 연산 출력. 9번 라인만 확인하면 됨.

# ['__class__', '__delattr__', '__dict__', '__dir__', '__doc__', '__eq__', '__format__', 
#  '__ge__', '__getattribute__', '__gt__', '__hash__', '__init__', '__init_subclass__', 
#  '__le__', '__lt__', '__module__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', 
#  '__repr__', '__setattr__', '__sizeof__', '__str__', '__subclasshook__', '__weakref__', 
#  'isEmpty', 'items', 'peek', 'pop', 'push', 'size']

s.push(1)
s.push(2)
s.push(3)
s.push(5)
print(s.items) # [1, 2, 3, 5]
print(s.peek()) # 5
print(s.size()) # 4
print(s.pop()) # 5. 주의할 점은 peek랑 달리 3을 스택에서 제거하고 return
print(s.size()) # 3
print(s.isEmpty()) # False

 

Python의 리스트 관련 메서드 활용하기

스택의 기본 원리만 확실히 인지했다면 클래스고 모듈이고 다 필요없다. 그냥 리스트만으로도 충분히 실용적으로 사용할 수 있다. 위 코드를 모듈 없이 그대로 재현하면 다음과 같다.

s = []
s.append(1)
s.append(2)
s.append(3)
s.append(5)
print(s) # [1, 2, 3, 5]
print(s[-1]) # 5
print(len(s)) # 4
print(s.pop()) # 5
print(len(s)) # 3
print(len(s) == 0) # False

너무 당연한 말이지만 pythonds 모듈도 리스트 메서드 기반으로 만들어놓은 것이라 그냥 우리가 직접 리스트 관련 메서드를 사용하는 것과 모듈을 사용하는 것의 결과가 완벽히 동일하다.

 

스택의 push는 리스트의 append 메서드로, pop은 리스트의 pop연산으로 대신할 수 있으며 그 외의 부수적인 연산들도 전부 손쉽게 생각해낼 수 있는 것들이다.