1-1. Stack이란
LIFO(Last In, First Out) : 후입선출
스택(Stack)은 연결리스트를 기반으로 한 자료구조로 상당히 단순한 자료구조입니다.
Stack에서는 다음 연산을 사용합니다.
push: 원소를 넣는 연산 \(O(1)\)pop: 가장 상위 원소를 빼는 연산 \(O(1)\)
그리고 마지막에 들어간 원소(상위 원소)를 top 이라고 하고, 대부분의 언어에서 빈 stack에서 pop, top을 하면 런타임에러가 발생합니다.
항상 가장 상위 원소를 호출하거나 삭제하므로 가장 먼저 들어온 것이 가장 나중에 나오는 선입후출 구조를 가지고 있습니다.
가장 마지막에 들어온 정보를 유지하는 연산은 다음과 같은 task에 활용할 수 있습니다.
- undo, 되돌리기 (Ctrl+Z)
- 후위표기법(postfix notation) 수식 계산
- 괄호 체크
- 메모리 연산, 재귀함수 호출
Python에서는 Stack 자료구조를 List를 사용하기에 append와 pop으로 사용합니다.
import sys
input = sys.stdin.readline
stk = []
for i in range(int(input())):
S = input().split()
if S[0] == 'push': stk.append(S[1])
elif S[0] == 'pop': print(stk.pop() if len(stk) else -1)
elif S[0] == 'size': print(len(stk))
elif S[0] == 'empty': print(int(len(stk)==0))
elif S[0] == 'top': print(stk[-1] if len(stk) else -1)