[Python 알고리즘] # 스택

스택 (Stack)

스택(stack)은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있도록 제한된 자료구조이다. 스택에 새로 추가한 원소는 원래 있던 원소의 위에 쌓이는 형태가 되므로 늦게 들어갈 수록 먼저 나온다. 이를 후입선출(LIFO) 구조라고 한다.

📝 스택 기본연산

• push()
  스택에 원소를 추가한다.
• pop()
  스택 가장 위에 있는 원소를 삭제하고 그 원소를 반환한다.
• top()
  스택 가장 위에 있는 원소를 삭제하지 않으며 그 원소를 반환한다.
• empty()
  스택이 비어있는지를 확인하고 비어있다면 1, 아니면 0을 반환한다.

📝 스택 구현

파이썬은 스택 자료구조는 따로 제공하지 않기 때문에 기본 자료형인 리스트를 통해 스택을 구현할 수 있다.

• Stack - init
  파이썬에서는 리스트로 스택을 흉내낸다. 따라서 스택 자료구조를 초기화할 때에는 빈 리스트를 생성해준다.

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

• Stack - push
  스택에 원소를 넣을 때는 append 메소드를 이용하여 리스트의 가장 마지막에 원소를 넣도록 한다.

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

stack
# [1, 2, 3, 4]

• Stack - pop
  스택에서 원소를 제거할 때는 pop 메소드를 이용해 리스트의 가장 마지막 원소를 제거해준다. 이 과정에서 pop 메소드에 의해 제거한 원소를 반환받을 수 있다.

# 스택에서 원소 제거 후 반환
stack = [1, 2, 3]
top = stack.pop()

print(top)
stack

# 3
# [1, 2]

• Stack - top
  스택에서 원소를 제거하지 않고 리스트 인덱스의 [-1]을 이용하여 반환받을 수 있다.

# 스택의 top 반환하기
stack = [1, 2, 3]
top = stack[-1]

top

# 3