스택, 큐, 덱

mingsso·2023년 4월 14일

Algorithm

목록 보기

9/35

1️⃣ 개념

스택

한쪽 끝에서만 자료를 넣고 뺄 수 있음 -> 후입선출
원소의 추가, 제거 = O(1)
제일 상단의 원소 확인 = O(1)
제일 상단이 아닌 나머지 원소들의 확인, 변경이 원칙적으로 불가능함
원소가 추가되고 제거되는 곳을 top이라고 부름

# 오큰수 = Ai보다 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수 구하기
# 스택 문제는 대부분 이런 형태의 코드인듯?
stack.append(0)

for i in range(1, n):   # 역순 아님
	while stack and A[stack[-1]] < A[i]:
    	answer[stack.pop()] = A[i]
        
    stack.append(i)    # 인덱스 저장

후위표기식

중위표기식 -> 후위표기식

st = input()

answer = []
stack = []
prior = {'*': 3, '/': 3, '+': 2, '-': 2, '(': 1}

for i in range(len(st)):
	if st[i].isdigit():   
    	answer.append(st[i])
    elif st[i] == '(':
    	stack.append(st[i])
    elif st[i] == ')':
    	while stack[-1] != '(':
        	answer.append(stack.pop())
        stack.pop()   # '('가 나타나면 pop
    else:
    	while stack and prior[st[i]] <= prior[stack[-1]]:
        	answer.append(stack.pop())
        stack.append(st[i])

while stack:
	answer.append(stack.pop())

계산 방법

숫자는 스택에 그냥 추가하기
연산자가 나오면 숫자 2개를 pop해서 계산하고, 계산한 값은 다시 스택에 넣음

큐

한쪽 끝에서만 자료를 넣고 반대쪽 끝에서 자료를 꺼낼 수 있음 -> 선입선출
원소의 추가, 제거 = O(1)
제일 앞/뒤의 원소 확인 = O(1)
제일 앞/뒤가 아닌 나머지 원소들의 확인, 변경이 원칙적으로 불가능함
추가되는 곳을 rear, 제거되는 곳을 front라고 함

덱

양쪽 끝에서 자료들을 넣고 뺄 수 있는 자료구조로, 스택과 큐를 모두 구현할 수 있음
원소의 추가, 제거 = O(1)
제일 앞/뒤의 원소 확인 = O(1)
제일 앞/뒤가 아닌 나머지 원소들의 확인, 변경이 원칙적으로 불가능함

from collections import deque

dq = deque()
dq.index(i)   # 덱에서도 인덱스 함수 사용 가능!

2️⃣ 문제 풀이

* 프로그래머스 다리를 지나는 트럭

https://school.programmers.co.kr/learn/courses/30/lessons/42583

# 이런 식으로 스택 사용할 수도 있음 
stack = [0] * bridge_length
total -= stack.pop(0)
stack.append(truck_weights[idx])

* ⭐️ 프로그래머스 주식가격

https://school.programmers.co.kr/learn/courses/30/lessons/42584

초 단위로 기록된 주식 가격이 담긴 배열 prices가 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지 리턴하기
[1, 2, 3, 2, 3] -> [4, 3, 1, 1, 0]

def solution(prices):
    n = len(prices)
    answer = [i for i in range(n-1, -1, -1)]
    
    # 주식 가격이 떨어질 경우 찾기
    stack = []
    for i in range(n):
        while stack and prices[stack[-1]] > prices[i]:
            j = stack.pop()
            answer[j] = i - j
        stack.append(i)   # 인덱스를 스택에 넣어줌 
        
    return answer

* 프로그래머스 수식 최대화 (Level 2)

https://school.programmers.co.kr/learn/courses/30/lessons/67257

연산자의 우선순위를 재정의(+ > - > * ) 해서 만들 수 있는 가장 큰 수 구하기

# 계산하기
# exp = deque(['100', '-', '200', '*', '300', '-', '500', '+', '20'])

for p in prior:
	stack = []
    while len(exp) != 0:
    	op = exp.popleft()
        if op == p:
        	result = str(eval(stack.pop() + op + exp.popleft()))
            stack.append(result)
        else:
        	stack.append(op)
	exp = deque(stack)