B-1: 스택·큐·덱 — "쌓아 올리고, 줄 세우고, 양끝을 본다"

안녕하세요! 코딩테스트와 CS의 길잡이, 홍순구 튜터입니다.

지난 시간엔 배열·문자열·격자를 직접 주무르는 손을 만들었습니다. 격자 위를 걸으며 "다음에 갈 칸"을 살피는 시뮬레이션도 짰죠. 그때 잠깐 흘렸던 이야기가 있습니다. 격자를 한 칸씩 퍼져 나가며 탐색하려면 "다음에 갈 칸들"을 어딘가에 줄 세워 둬야 한다고요. 그 줄을 담는 그릇이 오늘 배울 큐(queue)입니다.

오늘부터 카테고리 B, 선형 자료구조로 들어갑니다. 데이터를 한 줄로 늘어놓는 그릇들이에요. 그 첫 주자가 스택·큐·덱 세 형제입니다. 셋 다 "한 줄로 늘어선 데이터를 넣고 뺀다"는 점은 같은데, 어느 끝에서 넣고 빼느냐가 다릅니다. 그 작은 차이가 LIFO와 FIFO라는 전혀 다른 성질을 만들고, 괄호 검사부터 BFS까지 코딩테스트의 절반을 떠받칩니다.

본격적으로 들어가기 전에, 우리가 앞으로 만날 자료구조 전체를 한 장의 지도로 펼쳐 둘게요. 지난 시간에 약속한 그림 ② 자료구조 지도입니다.

 ① 선형 (한 줄로 늘어섬)               ② 비선형 (가지 치고 이어짐)
   배열 (Array)              ← A-2       트리 (Tree / BST)    ← C-1
   스택·큐 (Stack / Queue)   ← 오늘 B-1   힙 (Heap)           ← C-2
   연결 리스트 (Linked List) ← B-2       그래프 (Graph)       ← C-3
   해시 (Hash, dict/set)     ← B-3
        │                                       │
        └────── 그 위에서 정렬·탐색·알고리즘(D·E·F)이 돈다 ──────┘

데이터를 담는 그릇(B·C)에 먼저 익숙해져야, 그 위에서 도는 알고리즘(D·E·F)이 막히지 않습니다. 오늘은 이 지도의 왼쪽 위, 선형 자료구조의 첫 칸을 채웁니다.

 오늘의 여정 — "쌓아 올리고, 줄 세우고, 양끝을 본다"

 [1] 스택 (LIFO)      →  접시 쌓기, 마지막에 넣은 게 먼저 나온다, push/pop O(1)
 [2] 큐 (FIFO)        →  줄 서기, 먼저 넣은 게 먼저 나온다, 리스트 pop(0) 함정
 [3] 덱 (deque)       →  양쪽 끝이 다 O(1), 실전 큐의 정답
 [4] 괄호 검사        →  스택으로 짝을 맞춘다 (코테 단골)
 [5] 후위 표기법      →  스택으로 수식을 계산한다
 [6] 모노토닉 스택    →  다음 큰 수를 O(n²)에서 O(n)으로
 [7] 큐·덱 활용       →  회문(덱 양끝) + BFS로 가는 다리

자, 데이터를 쌓고 줄 세우는 두 그릇을 손에 쥐러 가 봅시다. 출발합니다!

💡 오늘 수업의 핵심 — "스택(LIFO)과 큐(FIFO)를 직접 구현해 원리를 보고, 실전에선 deque로 양끝을 O(1)에 다루며, 괄호·후위·모노토닉·회문 같은 빈출 유형으로 굳힌다"

🎯 학습 목표

• 스택(LIFO)과 큐(FIFO)를 리스트로 직접 구현하고, push/pop/peek 같은 핵심 연산의 시간·공간 복잡도를 빅오로 짚습니다.
• 리스트로 짠 큐의 pop(0) O(n) 함정을 직접 보고, 실전에선 collections.deque 로 양끝을 O(1)에 처리합니다.
• 스택·큐·덱으로 괄호 검사·후위 표기법·모노토닉 스택·회문 같은 코테 빈출 유형을 풀어내고, 큐가 BFS의 엔진이 되는 길을 미리 봅니다.

Step 1: "접시를 쌓듯이" — 스택과 LIFO

식당에서 깨끗한 접시를 쌓아 둔 모습을 떠올려 보세요. 새 접시는 맨 위에 올리고, 꺼낼 때도 맨 위 접시부터 집습니다. 마지막에 올린 접시가 가장 먼저 나가는 거죠. 이걸 LIFO(Last In First Out), "나중에 들어온 게 먼저 나간다"라고 부릅니다. 이 규칙으로 데이터를 넣고 빼는 그릇이 스택(stack)입니다.

스택에는 딱 세 가지 동작만 있습니다. 맨 위에 쌓는 push, 맨 위를 꺼내는 pop, 맨 위를 꺼내지 않고 들여다보는 peek입니다. 셋 다 맨 위 한 곳에서만 일어나죠.

 스택에 1, 2, 3을 차례로 push 하면:

   ┌───┐
   │ 3 │  ← 맨 위 (마지막에 넣은 것, 가장 먼저 나간다)
   ├───┤
   │ 2 │
   ├───┤
   │ 1 │  ← 맨 아래 (처음 넣은 것, 가장 나중에 나간다)
   └───┘

 pop() 하면 맨 위 3이 먼저 나온다 → LIFO

파이썬에선 스택을 따로 만들 필요도 없이 리스트가 그대로 스택입니다. 리스트의 맨 끝에 붙이는 append가 push, 맨 끝을 떼는 pop()이 pop이거든요. 둘 다 맨 끝 한 곳만 건드리니 O(1)입니다. 원리를 또렷이 보기 위해, 리스트를 감싼 Stack 클래스로 직접 구현해 봅시다.

# structures/stack_queue.py

class Stack:
    """LIFO 스택. 파이썬 리스트의 끝(append/pop)을 그대로 쓴다.

    끝에서만 넣고 빼니 push·pop·peek 모두 O(1). 공간은 담은 원소 수만큼 O(n).
    """

    def __init__(self):
        self._items = []

    def push(self, value):
        """맨 위에 쌓는다. O(1)."""
        self._items.append(value)

    def pop(self):
        """맨 위를 꺼내 돌려준다. 비었으면 IndexError. O(1)."""
        if not self._items:
            raise IndexError("pop from empty stack")
        return self._items.pop()

    def peek(self):
        """맨 위를 꺼내지 않고 들여다본다. O(1)."""
        if not self._items:
            raise IndexError("peek from empty stack")
        return self._items[-1]

pop과 peek 앞에 "비었으면 막아 주는" 검사를 한 줄씩 뒀습니다. 빈 스택에서 꺼내려는 건 실수일 가능성이 크니, 조용히 엉뚱한 값을 주는 대신 IndexError로 분명히 알려 주는 거죠. 이 검사는 비교 한 번이라 O(1)이고, 빅오에 영향을 주지 않습니다.

1, 2, 3을 차례로 push한 뒤 세 번 pop하면 [3, 2, 1]이 나옵니다. 넣은 순서의 정반대죠. 이게 LIFO입니다.

🎯 코테에서는 "스택 수열"처럼 1부터 n까지의 수를 스택에 넣었다 뺐다 하며 특정 순서를 만들 수 있는지 묻는 유형으로 나옵니다. 또 함수가 자기를 부르는 재귀도 사실은 호출을 스택에 쌓는 구조라, 스택을 이해하면 재귀(E-1)가 한결 또렷해집니다.

💡 한 줄 정리

스택은 LIFO — 맨 위 한 곳에서만 넣고 빼니 push·pop·peek이 모두 O(1)이고, 파이썬 리스트가 그대로 스택이다.

Step 2: "줄을 서듯이" — 큐와 FIFO, 그리고 리스트의 함정

이번엔 은행 창구 앞 줄을 떠올려 보세요. 먼저 온 사람이 먼저 처리받고, 새로 온 사람은 줄 맨 뒤에 섭니다. 먼저 들어온 게 먼저 나가는 거죠. 이걸 FIFO(First In First Out), "먼저 들어온 게 먼저 나간다"라고 부릅니다. 이 규칙의 그릇이 큐(queue)입니다.

스택이 한 끝만 썼다면, 큐는 양 끝을 나눠 씁니다. 뒤로 줄을 세우는 enqueue(맨 뒤에 추가), 앞에서 내보내는 dequeue(맨 앞에서 제거)죠.

        dequeue                        enqueue
        (앞에서 나간다)                  (뒤에 줄 선다)
           ↓                              ↓
         [ 1 ][ 2 ][ 3 ][ 4 ]
           └ 먼저 넣은 1이 먼저 나간다 (FIFO)

큐도 리스트로 짜 봅시다. 그런데 여기에 빅오 함정이 하나 숨어 있어요. 맨 뒤에 붙이는 enqueue는 리스트의 append라 O(1)인데, 맨 앞을 빼는 dequeue를 리스트의 pop(0)으로 하면 O(n)이 됩니다.

# structures/stack_queue.py

class Queue:
    """FIFO 큐 — 리스트로 '순진하게' 짠 버전. 함정을 보여주려고 일부러 이렇게 둔다.

    enqueue(맨 끝 append)는 O(1)이지만, dequeue(맨 앞 pop(0))는 뒤 원소를
    전부 한 칸씩 당겨서 O(n)이다. 원소가 많으면 이 O(n)이 쌓여 시간 초과로 간다.
    실전 큐는 이 클래스 대신 collections.deque(popleft가 O(1))를 쓴다.
    """

    def __init__(self):
        self._items = []

    def enqueue(self, value):
        """맨 뒤에 줄 세운다. O(1)."""
        self._items.append(value)

    def dequeue(self):
        """맨 앞을 내보낸다. pop(0)이라 O(n) — 바로 이게 함정이다."""
        if not self._items:
            raise IndexError("dequeue from empty queue")
        return self._items.pop(0)

왜 pop(0)이 O(n)일까요? 리스트는 칸들이 메모리에 나란히 붙어 있다고 했죠(A-1·A-2). 맨 앞 칸을 빼면 그 자리가 비니까, 뒤에 있던 원소를 전부 한 칸씩 앞으로 당겨야 합니다. 원소가 n개면 n번을 당기죠. 그래서 O(n)입니다.

 pop(0) 으로 맨 앞을 빼면:

  [ 1 ][ 2 ][ 3 ][ 4 ]
    빠짐  ←  ←  ←        2, 3, 4를 전부 한 칸씩 당긴다 (n번)
  [ 2 ][ 3 ][ 4 ]

enqueue를 n번, dequeue를 n번 하는 큐 시뮬레이션이라면, dequeue 하나하나가 O(n)이라 전체가 O(n²)로 부풀어 시간 초과로 갑니다. 1, 2, 3을 enqueue한 뒤 세 번 dequeue하면 [1, 2, 3]이 넣은 순서 그대로 나오긴 합니다. 결과는 맞아요. 다만 느립니다. 이 함정을 어떻게 풀까요? 바로 다음 Step의 덱입니다.

🎯 코테에서는 격자를 한 칸씩 퍼져 나가는 탐색(BFS)에서 "다음에 갈 칸들"을 큐에 줄 세웁니다. 지난 시간 격자 시뮬레이션에서 "다음에 갈 칸"을 살폈죠? 그걸 순서대로 처리하려면 먼저 발견한 칸을 먼저 꺼내야 하고, 그게 정확히 FIFO입니다. 이 연결은 Step 7에서 다시 짚습니다.

💡 한 줄 정리

큐는 FIFO — 양 끝을 나눠 쓰는데, 리스트로 짜면 맨 앞 pop(0)이 O(n)이라 큰 입력에서 시간 초과를 부른다.

Step 3: "양쪽 끝이 다 빠른 그릇" — 덱과 collections.deque

큐의 함정은 리스트가 한쪽 끝만 빠르기 때문이었습니다. 그럼 양쪽 끝이 다 빠른 그릇을 쓰면 되겠죠. 그게 덱(deque), 풀어 쓰면 double-ended queue(양쪽 끝 큐)입니다. 파이썬 표준 라이브러리 collections에 deque로 들어 있어요.

deque는 양쪽 끝에서 넣고 빼는 네 동작이 모두 O(1)입니다.

              appendleft           append
                 ↓                    ↓
   popleft  ←  [ 1 ][ 2 ][ 3 ]  →  pop
   (왼쪽 끝)                         (오른쪽 끝)
        양쪽 끝 모두 넣고 빼기가 O(1)

그래서 실전에서 큐가 필요하면 리스트가 아니라 deque를 씁니다. enqueue는 append, dequeue는 popleft로 하면 둘 다 O(1)이죠. 앞 Step의 함정이 깔끔하게 사라집니다. 표준 라이브러리는 C로 구현돼 있어 직접 짠 것보다 빠르고 버그도 없습니다. 이게 두 트랙의 실전 쪽이에요 — 원리는 손으로 한 번 짜 보되, 실전 코테에선 deque를 믿고 씁니다.

# 실전 큐는 deque로 — enqueue=append, dequeue=popleft 모두 O(1)
from collections import deque

q = deque()
q.append(1); q.append(2); q.append(3)   # 줄 세우기
q.popleft()   # 1  (맨 앞이 O(1)로 나온다)
q.popleft()   # 2

덱 하나로 스택도, 큐도 다 됩니다. 오른쪽 끝만 쓰면(append/pop) 스택이고, 한쪽으로 넣고 반대쪽으로 빼면(append/popleft) 큐죠. 그래서 "스택이든 큐든 그냥 deque 쓰면 되지 않나?" 싶은데, 맞습니다. 다만 한 가지 잃는 것이 있어요.

deque는 양 끝이 빠른 대신, 가운데를 인덱스로 콕 집는 건 O(n)입니다. dq[3]처럼 가운데 원소를 바로 꺼내려면 끝에서부터 세어 가야 하거든요. 리스트는 정반대로 인덱싱이 O(1)이지만 앞쪽 삽입이 O(n)이었죠. 공짜 점심은 없습니다 — 무엇을 빠르게 하면 다른 무언가가 느려집니다.

🎯 코테에서는 "양 끝을 다 만져야 하는" 문제(슬라이딩 윈도우의 최댓값, 회문, BFS의 큐)면 deque, "가운데를 인덱스로 자주 들여다보는" 문제면 리스트입니다. 입력 크기와 필요한 연산을 보고 그릇을 고르는 게 첫 판단이에요.

💡 한 줄 정리

덱(collections.deque)은 양쪽 끝 넣고 빼기가 모두 O(1)이라 실전 큐의 정답이지만, 가운데 인덱싱은 O(n)으로 리스트와 정반대 트레이드오프를 가진다.

Step 4: "괄호의 짝을 맞춘다" — 스택의 첫 활용

이제 스택을 실전 문제에 써 봅시다. 가장 고전적이고, 코테에 가장 자주 나오는 스택 문제가 괄호 검사입니다. "({[]})" 처럼 여러 종류의 괄호가 섞인 문자열이 올바르게 짝지어졌는지 판정하는 거죠.

왜 스택일까요? 괄호는 가장 최근에 연 것이 가장 먼저 닫혀야 합니다. ({[ 순서로 열었으면 ]}) 순서로 닫혀야 맞죠. "가장 최근에 연 것"을 기억했다가 "가장 먼저" 꺼내 맞춰 보는 것 — 이게 바로 LIFO, 스택입니다.

규칙은 단순합니다. 여는 괄호를 만나면 스택에 push하고, 닫는 괄호를 만나면 스택 맨 위와 짝이 맞는지 보고 맞으면 pop합니다. 끝까지 갔을 때 스택이 비어 있으면 모든 짝이 맞은 거예요.

# structures/stack_queue.py

def is_balanced(s):
    """괄호 문자열의 짝이 맞는지. 여는 괄호는 쌓고, 닫는 괄호에서 짝을 맞춘다.

    여는 괄호를 만나면 push, 닫는 괄호를 만나면 맨 위와 짝이 맞는지 pop해 본다.
    끝에 스택이 비어 있어야 모든 짝이 맞은 것. 한 글자당 push/pop 한 번이라
    문자열 길이 n에 시간 O(n)·공간 O(n).
    예: is_balanced("({[]})") -> True, is_balanced("([)]") -> False
    """
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in ")]}":
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

pairs는 "닫는 괄호 → 짝이 되는 여는 괄호"를 적어 둔 딕셔너리입니다. 닫는 괄호 ch를 만나면 pairs[ch]로 "있어야 할 여는 괄호"를 알 수 있죠. 그게 스택 맨 위와 다르거나, 닫을 게 있는데 스택이 비었으면 짝이 어긋난 겁니다.

"({[]})"가 어떻게 도는지 한 글자씩 따라가 봅시다.

 "({[]})" 를 왼쪽부터 한 글자씩:

   (  → 여는 괄호, push        stack:  (
   {  → 여는 괄호, push        stack:  ( {
   [  → 여는 괄호, push        stack:  ( { [
   ]  → ] 의 짝은 [ ? 맨 위 [ 와 일치, pop    stack:  ( {
   }  → } 의 짝은 { ? 맨 위 { 와 일치, pop    stack:  (
   )  → ) 의 짝은 ( ? 맨 위 ( 와 일치, pop    stack:  (비었음)

 끝에 스택이 비었다 → 모든 짝이 맞다 → True

반대로 "([)]"는 어떨까요? (, [를 쌓은 뒤 )를 만나는데, 맨 위는 [라서 )의 짝 (와 다릅니다. 그 순간 False죠. 괄호 개수는 맞아도 순서가 엇갈리면 틀린 겁니다.

한 글자당 push 또는 pop을 한 번 하니, 문자열 길이 n에 시간 O(n)입니다. 스택에 최대 n개가 쌓일 수 있어 공간도 O(n)이고요.

🎯 코테에서는 "올바른 괄호" 유형으로 프로그래머스 Lv0~Lv2, LeetCode의 Valid Parentheses(#20)에 그대로 나옵니다. 변형으로 "짝이 안 맞는 괄호를 최소 몇 개 지우면 되나", "괄호로 코드 블록의 깊이를 구하라" 같은 문제가 있는데, 전부 이 push/pop 골격에서 출발합니다.

💡 한 줄 정리

괄호 검사는 "가장 최근에 연 게 가장 먼저 닫힌다"는 LIFO라 스택이 딱 맞고, 한 글자당 push/pop 한 번이라 O(n)이다.

Step 5: "거꾸로 쓴 수식을 계산한다" — 후위 표기법

우리가 평소 쓰는 3 + 4 * 2 같은 수식은 연산자가 두 숫자 가운데 있어서 중위 표기법(infix)이라고 합니다. 사람에겐 익숙하지만, 컴퓨터엔 골치예요. 곱셈을 덧셈보다 먼저 해야 한다는 우선순위와 괄호를 따져야 하거든요.

그래서 컴퓨터는 연산자를 숫자들 뒤에 두는 후위 표기법(postfix)을 좋아합니다. 3 + 4 * 2를 후위로 쓰면 3 4 + 2 *가 아니라... 잠깐, 우선순위를 따지면 3 4 2 * +가 되네요. 우선 우리는 더 간단한 예 (3 + 4) * 2를 후위로 쓴 3 4 + 2 *를 계산해 봅시다. 후위 표기법의 매력은 괄호도 우선순위도 필요 없다는 점이에요. 왼쪽부터 차례로 읽으며 스택 하나로 계산됩니다.

규칙은 이렇습니다. 숫자를 만나면 push, 연산자를 만나면 위의 두 수를 꺼내 계산한 뒤 결과를 다시 push합니다.

# structures/stack_queue.py

def eval_postfix(tokens):
    """후위 표기법(postfix) 수식을 계산한다. 피연산자는 쌓고, 연산자에서 둘을 꺼낸다.

    숫자는 push, 연산자(+, -, *, /)를 만나면 위의 두 수를 꺼내(나중에 쌓인 게 b,
    그 아래가 a) a op b를 계산해 다시 push한다. 토큰 수 n에 시간 O(n)·공간 O(n).
    예: eval_postfix(["3", "4", "+", "2", "*"]) -> 14   # (3 + 4) * 2
    """
    stack = []
    for token in tokens:
        if token in ("+", "-", "*", "/"):
            b = stack.pop()
            a = stack.pop()
            if token == "+":
                stack.append(a + b)
            elif token == "-":
                stack.append(a - b)
            elif token == "*":
                stack.append(a * b)
            else:
                stack.append(int(a / b))   # 0 쪽으로 자르는 정수 나눗셈
        else:
            stack.append(int(token))
    return stack.pop()

여기서 순서 하나만 조심하면 됩니다. 연산자를 만나 두 수를 꺼낼 때, 나중에 쌓인 게 b, 그 아래가 a입니다. 그래서 a - b, a / b처럼 순서가 중요한 연산에서 거꾸로 꺼내면 답이 틀려요. 스택은 LIFO니까 마지막에 넣은 게 먼저 나오는 걸 떠올리면 자연스럽습니다.

["3", "4", "+", "2", "*"]를 따라가 봅시다.

 ["3", "4", "+", "2", "*"]  =  (3 + 4) * 2

   "3"  → 숫자, push                stack:  3
   "4"  → 숫자, push                stack:  3 4
   "+"  → 4, 3 꺼내 3 + 4 = 7, push   stack:  7
   "2"  → 숫자, push                stack:  7 2
   "*"  → 2, 7 꺼내 7 * 2 = 14, push  stack:  14

 마지막에 스택에 남은 14가 정답

토큰을 한 번씩만 훑고, 각 토큰에서 push/pop을 상수 번 하니 토큰 수 n에 시간 O(n), 공간 O(n)입니다.

🎯 코테에서는 "후위 표기식 계산"이 그대로 나오기도 하고, 한 걸음 더 들어가 "중위 표기식을 후위로 바꾸기"(이것도 스택으로 연산자 우선순위를 다룹니다)가 나오기도 합니다. 계산기를 구현하는 문제의 속을 열어 보면 거의 항상 이 스택 골격이 들어 있어요.

💡 한 줄 정리

후위 표기법은 괄호도 우선순위도 없이 스택 하나로 왼쪽부터 계산되며(숫자는 push, 연산자는 두 수 꺼내 계산), 토큰 수에 O(n)이다.

Step 6: "다음 큰 수를 한 번에" — 모노토닉 스택

이제 스택 활용의 백미, 모노토닉 스택(monotonic stack)입니다. monotonic은 "단조로운", 즉 값이 한 방향으로만(계속 커지거나 계속 작아지게) 정렬된 스택이라는 뜻이에요. 이름은 거창하지만, 한 번 보면 "아, 이런 게 있었구나" 싶을 만큼 강력합니다.

문제는 이렇습니다. "각 원소의 오른쪽에서, 처음으로 자기보다 큰 수는 무엇인가?" 없으면 -1입니다. 예를 들어 [2, 1, 3, 1]이면 답은 [3, 3, -1, -1]이에요. 2의 오른쪽에서 처음 더 큰 수는 3, 1도 3, 마지막 3과 1은 오른쪽에 더 큰 수가 없어 -1이죠.

순진하게 풀면 각 원소마다 오른쪽을 끝까지 훑습니다. 원소가 n개고 각자 오른쪽을 훑으니 O(n²)예요. 입력이 10만이면 100억 번이라 시간 초과입니다(지난 시간 "1초 1억 연산" 잣대 기억하시죠).

모노토닉 스택은 이걸 O(n)으로 끌어내립니다. 핵심 발상은 "아직 답을 못 찾은 인덱스를 스택에 쌓아 두는" 거예요. 새 원소가 들어올 때, 그 원소보다 작은 값을 기다리던 인덱스들은 바로 지금 답을 찾은 겁니다.

# structures/stack_queue.py

def next_greater(nums):
    """각 원소의 '오른쪽에서 처음 나오는 더 큰 수'를 구한다. 없으면 -1.

    순진하게는 원소마다 오른쪽을 전부 훑어 O(n²). 모노토닉 스택은 '아직 답을
    못 찾은 인덱스'를 값이 내림차순이 되도록 쌓아 두고, 더 큰 수가 나타나는
    순간 한꺼번에 답을 채운다. 각 인덱스가 스택에 한 번 들어가고 한 번 나오니
    시간 O(n)·공간 O(n).
    예: next_greater([2, 1, 3, 1]) -> [3, 3, -1, -1]
    """
    n = len(nums)
    answer = [-1] * n
    stack = []                       # 아직 '다음 큰 수'를 못 찾은 인덱스들 (값 내림차순)
    for i in range(n):
        # 지금 값이 스택 맨 위 인덱스의 값보다 크면, 그 인덱스의 답이 바로 nums[i]
        while stack and nums[stack[-1]] < nums[i]:
            answer[stack.pop()] = nums[i]
        stack.append(i)
    return answer

스택에는 값이 아니라 인덱스를 담는 점에 주목하세요. 답을 채울 위치(answer[그 인덱스])를 알아야 하니까요. [2, 1, 3, 1]을 따라가 봅시다.

 nums = [2, 1, 3, 1],  answer 는 [-1, -1, -1, -1] 로 시작
 stack: 아직 '다음 큰 수'를 못 찾은 인덱스 (담긴 값이 내림차순)

 i=0 (값 2): 스택 비었음              → push 0        stack: [0]
 i=1 (값 1): nums[0]=2 < 1 ? 아니오    → push 1        stack: [0, 1]
 i=2 (값 3): nums[1]=1 < 3 ? 예 → answer[1]=3, pop
             nums[0]=2 < 3 ? 예 → answer[0]=3, pop
                                     → push 2        stack: [2]
 i=3 (값 1): nums[2]=3 < 1 ? 아니오    → push 3        stack: [2, 3]

 끝: 스택에 남은 2, 3은 오른쪽에 더 큰 수가 없었음 → answer 그대로 -1
 결과: [3, 3, -1, -1]

i=2에서 3이 들어오는 순간, 그동안 답을 기다리던 인덱스 0과 1이 한꺼번에 답을 찾는 게 보이시나요? 이게 모노토닉 스택의 마법입니다.

🎯 코테에서는 "다음 큰 수(NGE)"가 그대로 나오고, "며칠 뒤에 기온이 더 오르나"(LeetCode Daily Temperatures #739), "히스토그램에서 가장 큰 직사각형" 같은 변형으로 자주 출제됩니다. 2026년 코테 빈출 패턴 분석에서도 Monotonic Stack은 핵심 10여 개 패턴 안에 듭니다. "오른쪽/왼쪽에서 처음으로 큰/작은 것"이라는 말이 보이면 모노토닉 스택을 떠올리세요.

💡 한 줄 정리

모노토닉 스택은 "아직 답을 못 찾은 인덱스"를 단조 순서로 쌓아, O(n²) 완전탐색을 O(n)으로 끌어내리는 강력한 스택 활용 패턴이다.

Step 7: "큐로 퍼져 나가고, 덱으로 양끝을 본다" — BFS로 가는 다리

마지막으로 큐와 덱의 활용을 하나씩 보고, 다음 카테고리로 가는 다리를 놓겠습니다.

먼저 덱으로 회문(palindrome) 검사입니다. 회문은 "level", "noon"처럼 앞으로 읽으나 뒤로 읽으나 같은 문자열이죠. 지난 시간엔 슬라이싱 s[::-1]로 뒤집어 비교했는데, 이번엔 덱의 양 끝을 좁혀 가며 확인해 봅시다. 양 끝을 O(1)에 꺼낼 수 있으니 딱 맞는 도구예요.

# structures/stack_queue.py

def is_palindrome_deque(s):
    """덱의 양끝을 동시에 좁혀 가며 회문(앞뒤가 같은 문자열)인지 본다.

    A-2에선 슬라이싱(s[::-1])으로 봤다면, 여기선 deque로 양끝을 O(1)에 꺼내
    맞춰 본다. 양끝에서 popleft·pop을 번갈아 약 n/2번 → 시간 O(n)·공간 O(n).
    예: is_palindrome_deque("level") -> True, is_palindrome_deque("hello") -> False
    """
    dq = deque(s)
    while len(dq) > 1:
        if dq.popleft() != dq.pop():
            return False
    return True

왼쪽 끝(popleft)과 오른쪽 끝(pop)을 동시에 꺼내 비교합니다. 다르면 그 순간 회문이 아니죠. 같으면 안쪽으로 한 칸씩 좁혀 가고, 가운데서 만나면(len(dq) <= 1) 끝까지 다 맞은 겁니다.

 "level" 을 덱에 담고 양 끝을 좁혀 간다:

   [ l e v e l ]   왼쪽 l == 오른쪽 l ?  예 → 둘 다 꺼낸다
   [   e v e   ]   왼쪽 e == 오른쪽 e ?  예 → 둘 다 꺼낸다
   [     v     ]   가운데 v 하나 남음 (len 1) → 끝, 회문이다 → True

양 끝에서 약 n/2번 비교하니 시간 O(n), 덱에 n글자를 담으니 공간 O(n)입니다. 슬라이싱 방식과 빅오는 같지만, "양 끝에서 좁혀 간다"는 투 포인터 사고를 덱으로 구현해 본 셈이에요. 이 양 끝 좁히기는 나중에 투 포인터(D-4)에서 본격적으로 만납니다.

이제 큐가 왜 중요한지, 다리를 놓겠습니다. 지난 시간 격자 시뮬레이션에서 한 칸의 "상하좌우 이웃"을 살폈죠. 그럼 시작 칸에서 출발해 이웃의 이웃으로 점점 퍼져 나가며 모든 칸을 훑으려면 어떻게 할까요?

방법은 이렇습니다. "지금 칸의 이웃들"을 큐에 줄 세워 두고, 큐에서 하나씩 꺼내 처리하면서 그 칸의 이웃을 또 큐 뒤에 줄 세웁니다. 먼저 발견한 칸을 먼저 처리(FIFO)하니, 시작점에서 가까운 칸부터 차례로 퍼져 나가죠.

 큐로 격자를 퍼져 나간다 (시작 ●에서 가까운 칸부터):

   시작 ● 의 이웃을 큐에 줄 세운다  →  큐: [이웃들]
   큐 앞에서 한 칸 꺼내 처리        →  그 칸의 이웃을 다시 큐 뒤에 줄 세운다
   큐가 빌 때까지 반복             →  가까운 칸 → 먼 칸 순서로 모두 방문

   "먼저 발견 = 먼저 처리"(FIFO) 라서, 가까운 곳부터 물결처럼 퍼진다

이게 BFS(너비 우선 탐색)의 심장입니다. 가중치가 없는 미로에서 최단 경로를 구하는 바로 그 알고리즘이죠. 그 엔진이 큐라는 것, 오늘은 여기까지만 기억하면 됩니다. BFS 자체는 그래프 표현(C-3)을 배운 뒤 DFS·BFS 시간(E-2)에 직접 구현합니다. 참고로 BFS의 짝꿍인 DFS(깊이 우선 탐색)는 큐 대신 스택(또는 재귀)으로 도는데, 오늘 배운 두 그릇이 탐색 알고리즘의 양대 엔진인 셈이에요.

🎯 코테에서는 "최단 거리", "최소 횟수", "몇 단계 만에" 같은 말이 보이고 모든 이동 비용이 같으면 BFS(큐)를 의심합니다. 미로 탈출, 섬의 개수, 토마토 익히기 같은 격자 탐색 문제의 엔진이 바로 이 큐예요.

💡 한 줄 정리

덱의 양 끝 좁히기로 회문을 O(n)에 검사하고, 큐의 FIFO는 "가까운 곳부터 퍼져 나가는" BFS의 엔진이 된다 — 스택은 DFS의 엔진이고.

마무리

오늘은 데이터를 한 줄로 늘어놓는 두 그릇, 스택과 큐를 손에 쥐었습니다. 접시처럼 쌓고(LIFO), 줄처럼 세우고(FIFO), 양끝이 다 빠른 덱까지. 그리고 그 위에서 괄호를 맞추고, 수식을 계산하고, 다음 큰 수를 한 번에 찾고, 회문을 검사했어요. 작은 그릇 두 개가 얼마나 많은 문제를 푸는지 보셨죠.

오늘 배운 핵심 세 가지

• 💡 하나 — 스택은 LIFO, 큐는 FIFO. 어느 끝에서 넣고 빼느냐가 전부다. 스택은 맨 위 한 곳(push/pop/peek 모두 O(1)), 큐는 뒤로 넣고 앞에서 뺀다. 파이썬 리스트는 그대로 스택이 되지만, 큐로 쓰면 함정이 있다.
• 💡 둘 — 리스트는 끝만 O(1), 앞은 O(n). 큐는 deque로. 리스트 pop(0)은 뒤를 전부 당겨 O(n)이라 큰 입력에서 시간 초과를 부른다. 실전 큐는 collections.deque로 양끝을 O(1)에 쓴다. 대신 덱은 가운데 인덱싱이 O(n) — 공짜 점심은 없다.
• 💡 셋 — 스택·큐는 활용이 핵심이다. 괄호 검사(LIFO로 짝 맞추기), 후위 표기법(스택으로 계산), 모노토닉 스택(O(n²)을 O(n)으로), 회문(덱 양끝), 그리고 BFS의 엔진(큐)·DFS의 엔진(스택)까지. 모든 연산을 빅오로 되짚는 습관도 함께.

다음 시간 예고

오늘 덱을 보며 "원소를 작은 블록으로 이어 붙인 구조"라고 했죠. 그 "이어 붙인다"를 끝까지 밀고 가면 연결 리스트(linked list)가 됩니다. 다음 시간(B-2)에 노드(node)와 포인터(pointer)로 데이터를 직접 잇는 구조를 손으로 짜 봅니다.

오늘 리스트의 한계도 보셨어요. 맨 앞이나 가운데에 끼워 넣고 빼는 게 O(n)이라는 점이요. 연결 리스트는 바로 이 약점을 풀어, 중간 삽입·삭제를 O(1)에 해냅니다(대신 인덱싱을 잃죠 — 또 다른 트레이드오프!). 오늘 deque의 속이 사실 이중 연결 리스트에 가깝다고 한 그 말의 정체도 다음 시간에 직접 확인합니다.

과제

오늘 배운 스택·큐·덱을 직접 손으로 짜 보는 문제들입니다. 풀어 본 뒤 예시 답안과 맞춰 보세요. 각 풀이의 시간·공간 복잡도를 빅오로 적는 것도 잊지 마세요.

[기초] 한 종류 괄호의 짝 맞추기

(와 ) 한 종류만 들어 있는 문자열이 올바른 괄호 문자열인지 판정하는 함수를 작성하세요. 올바르다는 건, 모든 여는 괄호가 나중에 닫히고, 닫는 괄호가 자기 짝보다 먼저 나오지 않는다는 뜻입니다(예: "(())"는 True, "())("는 False). 스택으로 푸는 방법과, 스택 없이 카운터 하나로 푸는 방법을 둘 다 생각해 보고, 둘의 공간 복잡도가 어떻게 다른지 한 줄 적어 보세요.

[응용] 원형 큐로 카드 버리기

1부터 n까지 번호가 적힌 카드가 위에서부터 순서대로 쌓여 있습니다(맨 위가 1). 다음을 카드가 한 장 남을 때까지 반복합니다. 맨 위 카드를 버리고, 그다음 맨 위 카드를 맨 아래로 옮긴다. 마지막에 남는 카드의 번호를 돌려주는 함수를 작성하세요. collections.deque로 "버리기"는 popleft, "맨 아래로 옮기기"는 popleft 후 append로 구현하면 깔끔합니다. 왜 리스트 대신 덱을 쓰는 게 유리한지(pop(0) 함정을 떠올리며) 빅오로 설명하세요.

[심화] 며칠을 기다려야 더 따뜻해지나

매일의 기온을 담은 리스트 temps가 주어집니다. 각 날에 대해 "앞으로 며칠을 기다리면 오늘보다 따뜻한 날이 처음 오는가"를 담은 리스트를 돌려주세요. 그런 날이 없으면 0입니다(예: temps = [3, 1, 4, 2] → [2, 1, 0, 0]: 0번째 날 3도는 2일 뒤 4도, 1번째 날 1도는 1일 뒤 4도, 4도와 마지막 2도는 더 따뜻한 날이 없어 0).

순진하게 짜면 O(n²)입니다. 오늘 배운 모노토닉 스택으로 O(n)에 푸세요. 스택에 무엇을 담아야 "며칠 뒤"라는 거리를 구할 수 있을지가 핵심입니다(힌트: 값이 아니라 무엇을?). 입력이 10만 일이라면 O(n²)과 O(n) 중 무엇이 통과하는지 "1초 1억 연산" 잣대로 판정하세요.

생각해볼 주제

정답이 하나가 아닌 질문들입니다. 혼자 고민해도 좋고, 스터디에서 토론해도 좋아요.

1. 스택은 리스트로 충분한데, 큐는 왜 deque가 필요할까?

스택과 큐는 둘 다 "한 줄로 늘어선 데이터를 넣고 빼는" 그릇입니다. 그런데 스택은 파이썬 리스트로 짜도 아무 문제가 없고(append/pop이 다 O(1)), 큐는 리스트로 짜면 함정에 빠져 deque가 필요했죠. 무엇이 이 차이를 만들까요? "한쪽 끝만 쓰느냐, 양쪽 끝을 쓰느냐"와 "리스트가 어느 끝에서 빠른가"를 엮어서 설명해 보세요.

2. 모노토닉 스택의 while은 중첩 반복인데 왜 O(n)일까?

next_greater는 for 안에 while이 든 이중 반복문처럼 생겼는데도 O(n)이라고 했습니다. 비결은 "각 원소가 스택에 한 번 들어가고 한 번 나온다"는 분할 상환(amortized) 논리였죠. 그런데 이 논리를 어떻게 확신할 수 있을까요? "어떤 원소도 두 번 pop되지 않는다"를 스스로 납득되게 설명해 보세요. 그리고 이 분할 상환 사고가 통하지 않는, 즉 진짜로 O(n²)인 이중 반복문은 어떤 모양일지도 떠올려 보세요.

3. 양 끝이 빠르면 가운데가 느리다 — 공짜 점심은 없다

덱은 양 끝 넣고 빼기가 O(1)인 대신 가운데 인덱싱이 O(n)이고, 리스트는 인덱싱이 O(1)인 대신 맨 앞 삽입이 O(n)입니다. 무언가를 빠르게 만들면 다른 무언가가 느려지는, 이 트레이드오프는 자료구조 전반에 흐르는 원리예요. 왜 "모든 연산이 다 O(1)인 만능 자료구조"는 만들기 어려울까요? 그리고 실전에서 그릇을 고를 때, "이 문제에서 가장 자주 일어나는 연산이 무엇인가"가 왜 선택의 기준이 되는지 생각해 보세요.