Stack
스택은 가장 나중에(최근에) 들어온 자료가 가장 먼저 처리되는 LIFO(Last-In-First-Out) 자료구조이다. 0개 이상의 요소를 가지는 선형리스트의 일종으로 데이터의 삽입과 제거가 한쪽 끝에서만 이루어진다. 즉, 스택의 중간에서는 데이터를 삭제할 수 없다.
사용사례
- 재귀 알고리즘
- 웹 브라우저 방문기록 (뒤로가기)
- undo (되돌리기, 실행취소) 기능
- 역순 문자열 만들기
- 수식의 괄호 검사
- 후위 표기법 계산
문제
스택 구현
| 연산 | 구현 |
|---|---|
| pop | stack.pop() |
| top | stack[-1] |
| size | len(stack) |
| empty | len(stack) == 0 |
| push | stack.append() |
init
- 파이썬은 스택 자료구조를 따로 제공하지 않는다. 따라서 기본 클래스인 list를 사용하여 스택을 구현한다.
빈 리스트를 만들어 스택을 초기화한다.
stack = []pop
- pop() 메서드를 이용해 리스트의 가장 마지막 원소를 제거하면서 제거된 원소를 리턴 받을 수 있다.
if cmd[0] == 'pop':
if len(stack) == 0:
print(-1)
else:
print(stack.pop())top
- stack[-1]로 리스트의 가장 마지막 원소를 제거하지 않고 가져오기만 한다.
elif cmd[0] == 'top':
if len(stack) == 0:
print(-1)
else:
print(stack[-1])size
- len() 메서드로 스택의 크기를 구한다.
elif cmd[0] == 'size':
print(len(stack))empty
elif cmd[0] == 'empty':
if len(stack) == 0:
print(1)
else:
print(0)push
- append() 메서드로 리스트의 가장 마지막에 원소를 넣는다.
else :
stack.append(int(cmd[1]))전체코드
import sys
n = int(sys.stdin.readline())
stack = []
for i in range(n):
cmd = sys.stdin.readline().split()
if cmd[0] == 'pop':
if len(stack) == 0:
print(-1)
else:
print(stack.pop())
elif cmd[0] == 'top':
if len(stack) == 0:
print(-1)
else:
print(stack[-1])
elif cmd[0] == 'size':
print(len(stack))
elif cmd[0] == 'empty':
if len(stack) == 0:
print(1)
else:
print(0)
else :
stack.append(int(cmd[1]))발생한 문제점 및 해결 방안
💡 시간단축을 위해 input()대신
sys.stdin.readline()을 사용하자.import sys sys.stdin.readline()
처음에 입출력 시간 초과 에러가 발생했는데 알고보니 input()의 문제였다.
input()의 경우 사용자의 입력을 받아서 → 문자열로 변환 → strip (양끝 공백 제거처리) 과정을 거친다.
반면 sys.stdin.readline()의 경우 개행 문자도 입력을 받을 수 있다고 한다. 단, 이때는 맨 끝의 개행문자까지 같이 입력받으므로 문자열을 저장하고 싶다면 rstrip()(오른쪽 공백제거)을 사용한다.
sys.stdin는 Spyder IDE 에서 작동하지 않는다.
Spyder IDE에서 실행했을 때 invalid literal for int() with base 10 에러가 발생했다.
구글링해보니 sys.stdin는 Spyder IDE에서 작동하지 않는다는 것을 알았고 기본 파이썬 쉘 IDE를 사용해서 해결했다.
참고
Android Developer.