스택이란?

스택은 가장 나중에 들어온 자료가 가장 먼저 처리되는 LIFO(Last-In-First-Out) 자료구조이다.
구멍이 하나밖에 없는 병이라고 생각하면 이해하기 쉽다.

스택에서의 연산

🤍 pop(): 스택에서 가장 위에 있는 항목을 제거한다.
🧡 push(item): item 하나를 스택의 가장 윗 부분에 추가한다.
💛 peek(): 스택의 가장 위에 있는 항목을 반환한다.
💚 isEmpty(): 스택이 비어 있을 때에 true를 반환한다.

스택과 재귀 알고리즘

스택이 유용한 경우는 재귀 알고리즘을 사용할 때다. 재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어 주고, 재귀 함수를 빠져 나와 퇴각 검색(backtrack)을 할 때는 스택에 넣어 두었던 임시 데이터를 빼 줘야 한다. 스택은 이런 일련의 행위를 직관적으로 가능하게 해 준다.
스택은 또한 재귀 알고리즘을 반복적 형태(iterative)를 통해서 구현할 수 있게 해준다.

파이썬을 사용한 Stack 구현

파이썬에서의 스택 = list를 사용

☞ 파이썬은 스택 자료구조를 따로 제공하지 않는다. 다만 기본 클래스인 list를 통해 스택을 흉내 낼 수 있다.

Stack - init

파이썬에서는 리스트로 스택을 흉내 낸다. 따라서 스택 자료구조를 초기화할 때에는 빈 리스트를 만들어준다.

# 빈 stack(리스트) 초기화
stack = []
stack

Stack - push

스택에 원소를 넣을 때에는 append 메서드를 이용해 리스트의 가장 마지막에 원소를 넣도록 한다.

# stack에 원소 추가
stack = [1,2,3]
stack.append(4)
print(stack)

Stack - pop

스택에서 원소를 제거할 때에는 pop 메서드를 이용해 리스트의 가장 마지막 원소를 제거해준다. 이때, pop 메서드에 의해 제거한 원소를 리턴 받을 수 있다.

# stack에서 원소 제거
stack = [1,2,3]
top = stack.pop()
print(top)
print(stack)

Stack - top

스택에서 원소를 제거하지 않고 가져오기만 할 때에는 [-1]을 이용하도록 한다.

# stack의 top 가져오기
stack = [1,2,3]
top = stack[-1]
print(top)
print(stack)