스택 자료구조 이론 및 예제 (python)

 

파이썬에서 스택을 구현하려면 리스트 자료형을 사용하자

 

리스트 자료형은 가장 오른쪽에 원소를 삽입하는 append 메소드와 가장 오른쪽에서 원소를 꺼내는 pop 메소드를 지원한다. 이를 이용해서 스택과 같이 사용할 수 있다. 

append() 와 pop() 의 시간복잡도는 O(1) 이기 때문에 스택 자료구조를 활용하기 적합하다. 파이썬에서는 표준 라이브러리를 사용할 필요 없이 기본적으로 제공되는 객체에 리스트를 이용해서 바로 스택을 구현하면 된다. 

 

stack = []

# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()  
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

# arr[A:B:C] index A부터 index B까지 C의 간격으로 배열 생성
# C가 None이면 한 칸 간격
# stack의 처음부터 끝까지 -1칸 간격으로 (== 역순으로) 
print(stack[::-1]) # 최상단 원소부터 출력 -> 1 3 2 5
print(stack) # 최하단 원소부터 출력 -> 5 2 3 1