Stack

목록

• Stack이란?
• Python에서 Stack 구현 방법
• ✏️ 연습 문제

---

📚 Stack

후입선출(LIFO, Last In, First Out) 구조를 가진 자료구조

💡 가장 나중에 삽입된 데이터가 가장 먼저 삭제됩니다!

 

스택의 주요 연산

• push(x): 스택의 맨 위에 요소 x를 추가한다.
• pop(): 스택의 맨 위 요소를 제거하고 반환한다.
• top() / peek(): 스택의 맨 위 요소를 제거하지 않고 반환한다.
• size(): 스택에 포함된 요소의 개수를 반환한다.
• isEmpty(): 스택이 비어 있는지 확인한다.

---

Python에서 Stack 구현 방법

Python에서는 내장 자료구조인 list 를 사용해 스택을 구현할 수 있습니다.

스택 정의

Python의 list를 사용해 stack을 선언합니다.

stack = [] # or list()

Push

리스트의 append()는 push와 동일한 기능을 수행합니다.

스택의 맨 위에 요소를 추가합니다.

stack.append(3) 
stack.append([1, 2]) 
stack.append("4")
stack.append("56")

# stack = [3, [1, 2], "4", "56"]

Pop

리스트의 pop()은 pop와 동일한 기능을 수행합니다.

스택의 맨 위에 있는 요소를 제거하고 값을 반환합니다.

stack.pop() # stack = [3, [1, 2], "4"]
print(stack.pop()) # 출력 : "4", stack = [3, [1, 2]]

Top / Peek

스택의 맨 위에 있는 요소를 반환만 합니다.

print(stack[-1]) # 출력 : [1, 2], stack = [3, [1, 2]]

Size

len()은 스택에 포함된 요수의 개수를 반환합니다.

print(len(stack)) # 출력 : 2

IsEmpty

빈 리스트이거나, 요소의 개수를 통해 스택이 비었는지 쉽게 확인할 수 있습니다.

print(stack) # 출력 : [3, [1, 2]]
stack.pop()
stack.pop()
print(stack) # 출력 : []

if not stack or len(stack) == 0:
    print("스택이 비었음!")

---

✏️ 연습 문제

Silver III : BOJ 01935, 후위 표기식2

https://www.acmicpc.net/problem/1935

💡 수식을 차례대로 Stack에 저장하고, 부호를 입력 받았을 때 필요한만큼 꺼내 계산해보세요

 

Silver II : BOJ 10799, 쇠막대기

https://www.acmicpc.net/problem/10799

💡오른쪽 괄호를 만나면 어떤 작업을 수행해야 할까요?

 

Gold IV : BOJ 02800, 괄호 제거

https://www.acmicpc.net/problem/2800

💡괄호의 쌍에 대한 조합 문제를 해결하고, 문자열 결과를 출력하세요