[algorithm] Stack (python)

Stack

• 먼저 들어 온 데이터가 나중에 나가는 형식의 자료구조 (선입후출) (FILO)
• 입구와 출구가 동일한 형태로 스택을 시각화할 수 있다.
• ex) 쌓아올린 박스

 

스택 구현 예제

파이썬에서는 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()

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

# output
>>> [1, 3, 2, 5]
>>> [5, 2, 3, 1]