스택(Stack)
추상적 자료구조(ADT)라고 한다. 자료구조의 방법이 코드로 정의된 것이 아니라 그 구조의 행동 양식만 정의되어 있다.- 프로그래밍 언어에 존재하지 않으므로 직접 구현해야 한다.
LIFO(Last In, First Out): 나중에 들어온 게 먼저 나간다.- 팬케이크를 층으로 쌓아 먹을 경우 제일 위에(나중에) 쌓인 팬케이크 먼저 먹는다, 브라우저 뒤로가기, Ctrl + Z (실행 취소)
- 배열이
수직으로 되어있다. - 파이썬
리스트(List)를 활용한다. - push는
.append()을 활용 - pop은
.pop()을 활용 - pop() : 맨 마지막 index 값을 출력해주고 제거시킨다.
활용 예시
프로그래머스 Level2 올바른 괄호
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from collections import deque
def solution(parseq):
stack = deque()
for p in parseq:
if p == '(':
stack.append(p)
elif p == ')':
if len(stack) == 0:
return False
stack.pop()
if len(stack) > 0:
return False
return True
1
2
3
4
5
6
7
8
9
10
11
12
def solution(parseq):
stack = []
for p in parseq:
if p == '(':
stack.append(p)
elif len(stack) == 0:
return False
elif p == ')' and stack[-1] == '(':
stack.pop()
if len(stack) > 0:
return False
return True
최근 & (조건) → 주식 고점
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
stock = [8, 7, 6, 7, 5, 4, 5, 3, 2, 1, 2, 4, 6, 5, 7, 10] # 주식 가격
high_stack = [] # 고점만을 담을 리스트
ggeol = [] # 팔 걸 모먼트(아 팔았어야 했는데...)
for i, item in enumerate(stock):
# 현재 가격이 예전의 고점보다 낮아지면 pop 하지 않음
# 현재 가격이 예전의 고점보다 같거나 크다면 pop을 함
while len(high_stack) > 0 and stock[high_stack[-1]] <= stock[i]:
high_stack.pop(-1)
if len(high_stack) == 0: # 고점이 없으면 -1을 입력
ggeol.append(-1)
else: # 고점이 있으면
ggeol.append(high_stack[-1])
if i == 0 and stock[i] > stock[i + 1]: # index 0번째 가격이 고점이라면
high_stack.append(i)
elif i == len(stock) - 1 and stock[i] > stock[i - 1] # index 마지막번째 가격이 고점이라면
high_stack.append(i)
elif stock[i] > stock[i - 1] and stock[i] > stock[i + 1] # 직전, 직후 가격보다 크면(고점)
high_stack.append(i)
return ggeol
# high_stack : [0, 3, 6, 12, 15] -> 값이 아닌 index 번호
# ggeol : [-1, 0, 0, 0, 3, 3, 3, 6, 6, 6, 6, 6, 3, 12, 0, -1]