[algo] 스택과 큐란?

스택과 큐 기본 구조

관련 문제

1. 탑
   https://www.acmicpc.net/problem/2493

# 탑 (백준 2493번)
import sys

N = int(sys.stdin.readline())
top = list(map(int, sys.stdin.readline().split()))
stack = []
answer = []
for i in range(len(top)):
    while stack: # 비교할 대상이 앞에 있을 때
        if stack[-1][1] > top[i]:
            answer.append(stack[-1][0] + 1) # 해당 스택의 인덱스 + 1
            break # 수신할 탑을 정해줬으므로 더이상 while문을 돌 필요가 없음!! (break 해주기)
        else:
            stack.pop()
    if not stack: # 비교할 대상이 앞에 없으므로 0
        answer.append(0)
    stack.append([i, top[i]])

print(*answer)

2. 크게 만들기
   https://www.acmicpc.net/problem/2812

import sys
N, K = map(int, sys.stdin.readline().split())
tmp = sys.stdin.readline()
num = []
for i in range(N):
    num.append(int(tmp[i]))

stack = []
cnt = K
for i in range(len(num)):
    # cnt가 0보다 크다는 조건으로 cnt가 0이 되었을 때 더이상 팝하지 못하게 했음
    # pop 횟수 초과 시 자동으로 밑에서 stack에 append만 됨!!
    while stack and cnt > 0:
        if stack[-1] >= num[i]:
            break
        else:
            stack.pop()
            cnt -= 1
    # stack에 append는 모든 원소를 넣는 것
    stack.append(num[i])
    
for i in range(N-K):
    print(stack[i], end = "")