Chương 8 - Queue + Stack

Stack (LIFO) và Queue (FIFO) là cặp đôi “ngược nhau”. Stack giải được mọi bài có cấu trúc lồng (parentheses, recursion, nested structure), Queue phục vụ duyệt theo lớp (BFS, sliding window). Chương này tập trung stack - bài queue thuần sẽ gặp lại ở Chương 10 (BFS). Cuối chương có 1 bài teaser về monotonic stack - pattern mạnh sẽ được khai thác sâu ở Chương 18.

Mục tiêu chương

Sau chương này, bạn sẽ:

• Biết khi nào dùng stack: nested structure, undo, monotonic.
• Biết khi nào dùng queue: BFS, sliding window, scheduler.
• Phân biệt Min Stack (aux stack vs encoded difference).
• Gateway sang Monotonic Stack (Ch 18) và String Parser (Ch 32).

Khi nào dùng pattern này?

Stack rất hợp khi: - Có cấu trúc lồng / balanced (ngoặc, tag HTML, nested expression). - Cần “undo” - bước trước phải xử lý xong sau bước hiện tại (DFS iterative). - Bài “next greater element”, “largest rectangle”, “daily temperatures” → monotonic stack (Chương 18).

Queue rất hợp khi: - Cần duyệt theo lớp / BFS (Chương 10). - Bài “sliding window max” → monotonic deque (Chương 18). - Producer-consumer, task scheduler.

Template code

from collections import deque
from typing import List

# 1) Stack với list (built-in trong Python, O(1) amortized).
stack: List[int] = []
stack.append(x)        # push
top = stack[-1]        # peek
val = stack.pop()      # pop

# 2) Queue với collections.deque - O(1) push/pop ở cả 2 đầu.
queue: deque[int] = deque()
queue.append(x)        # enqueue (đẩy vào cuối)
val = queue.popleft()  # dequeue (lấy đầu)

# 3) Stack lưu (index, value) - pattern monotonic.
stack: list[tuple[int, int]] = []        # (index, value)
for i, v in enumerate(arr):
    while stack and stack[-1][1] < v:
        idx, _ = stack.pop()
        # ... xử lý idx ...
    stack.append((i, v))

Bài tự luyện cuối chương

• LC 32 - Longest Valid Parentheses
• LC 71 - Simplify Path
• LC 84 - Largest Rectangle in Histogram (Chương 18)
• LC 225 - Implement Stack using Queues
• LC 622 - Design Circular Queue
• LC 933 - Number of Recent Calls
• LC 946 - Validate Stack Sequences

---

8.1 Valid Parentheses (LC 20)

Đề bài

Cho chuỗi s chỉ chứa ()[]{}. Trả về True nếu chuỗi hợp lệ: - Mỗi dấu ngoặc mở có dấu đóng tương ứng. - Các dấu ngoặc đóng đúng thứ tự (LIFO).

Ví dụ

Input:  s = "()"            → Output: True
Input:  s = "()[]{}"        → Output: True
Input:  s = "(]"            → Output: False
Input:  s = "([)]"          → Output: False    (lồng sai)
Input:  s = "{[]}"          → Output: True

Ràng buộc

• 1 <= len(s) <= 10^4

Clarifying questions

• Có chỉ chứa ngoặc không? → Theo đề: chỉ ()[]{}.
• Chuỗi rỗng? → True (theo quy ước).

Hướng tiếp cận

Stack pattern kinh điển. Duyệt từng ký tự: - Nếu là ngoặc mở → push. - Nếu là ngoặc đóng → check stack top có phải cặp tương ứng không. Nếu không, hoặc stack rỗng → return False. Nếu có → pop.

Cuối cùng stack phải rỗng (mọi ngoặc đã match).

Hình minh hoạ với s = "{[()]}":

ch   action          stack sau action
─────────────────────────────────────
{    push            ['{']
[    push            ['{', '[']
(    push            ['{', '[', '(']
)    pop, match (    ['{', '[']
]    pop, match [    ['{']
}    pop, match {    []

Stack rỗng → True ✓

Code Python 3

class Solution:
    def isValid(self, s: str) -> bool:
        pairs = {')': '(', ']': '[', '}': '{'}
        stack: list[str] = []
        for ch in s:
            if ch in pairs:                # ngoặc đóng
                if not stack or stack.pop() != pairs[ch]:
                    return False
            else:                          # ngoặc mở
                stack.append(ch)
        return not stack

Phân tích độ phức tạp

• Thời gian: O(n). Bộ nhớ: O(n).

Bình luận

• Bẫy thường gặp:
  • Quên check not stack trước khi pop → IndexError với "]".
  • Quên check stack rỗng ở cuối → "(" cũng trả True.
• Follow-up:
  • LC 32 - Longest Valid Parentheses: tìm dãy con dài nhất hợp lệ (DP hoặc stack với index).
  • LC 22 - Generate Parentheses (Chương 3, đã giải bằng backtracking).

Bài tự luyện liên quan

• LC 32 - Longest Valid Parentheses.
• LC 22 - Generate Parentheses.
• LC 678 - Valid Parenthesis String.

---

8.2 Min Stack (LC 155)

Đề bài

Thiết kế stack hỗ trợ 4 thao tác đều O(1): - push(x) - pop() - top() - peek - getMin() - trả về min hiện có trong stack

Ví dụ

Input (LC-style operation arrays):
  ops  = ["MinStack","push","push","push","getMin","pop","top","getMin"]
  args = [[],        [-2],   [0],  [-3],  [],     [],   [],   []]

Output: [null, null, null, null, -3, null, 0, -2]

Giải thích từng bước:
  MinStack()  → khởi tạo
  push(-2);  push(0);  push(-3)
  getMin()   → -3
  pop()      → bỏ -3
  top()      → 0
  getMin()   → -2

Ràng buộc

• Số op ≤ 3·10^4
• -2^31 <= val <= 2^31-1

Clarifying questions

• pop() khi stack rỗng? → Theo LC: không xảy ra (caller giữ invariant).

Hướng tiếp cận

Vấn đề: getMin() O(1) ⇒ phải lưu min đâu đó. Nhưng khi pop min ra, phải biết min mới - đây là cốt lõi.

Cách 1 - Aux stack song song giữ min_so_far.

Stack phụ mins mỗi ô = min của tất cả các phần tử dưới (kể cả nó) trong main stack. Khi push, push min(x, mins[-1]). Khi pop, pop cả 2 stack.

Cách 2 - 1 stack lưu (value, current_min).

Tương đương cách 1 nhưng gộp thành tuple. Cùng overhead.

Hình minh hoạ - Cách 1 với push(-2), push(0), push(-3), pop():

push(-2):  stack=[-2]      mins=[-2]
push(0):   stack=[-2, 0]   mins=[-2, -2]    (min(0, -2)=-2)
push(-3):  stack=[-2,0,-3] mins=[-2,-2,-3]   (min(-3, -2)=-3)

getMin() → mins[-1] = -3   ✓
pop():    stack=[-2, 0]    mins=[-2, -2]
getMin() → mins[-1] = -2   ✓

Code Python 3

class MinStack:
    def __init__(self):
        self.stack: list[int] = []
        self.mins: list[int] = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        cur_min = val if not self.mins else min(val, self.mins[-1])
        self.mins.append(cur_min)

    def pop(self) -> None:
        self.stack.pop()
        self.mins.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.mins[-1]

Phân tích độ phức tạp

• Thời gian: O(1) cho mọi op. Bộ nhớ: O(n).

Bình luận

• Tối ưu space? Có cách O(1) extra space khi mọi value đều dương và biết trước range, dùng “encoded difference” - phức tạp, không thực tế. Tốt nhất cứ dùng 2 stack.
• Bẫy: push 0 / số âm - code trên xử lý tự nhiên.
• Follow-up: MaxStack (LC 716) - tương tự nhưng có thêm popMax(), cần dùng DLL + ordered map.

Bài tự luyện liên quan

• LC 716 - Max Stack.
• LC 232 - Implement Queue using Stacks (bài 8.3).
• LC 895 - Maximum Frequency Stack.

---

8.3 Implement Queue using Stacks (LC 232)

Đề bài

Thiết kế Queue (FIFO) chỉ dùng 2 stack. Hỗ trợ push, pop, peek, empty.

Ví dụ

Input (LC-style operation arrays):
  ops  = ["MyQueue","push","push","peek","pop","empty"]
  args = [[],       [1],   [2],   [],    [],   []]

Output: [null, null, null, 1, 1, false]

Giải thích từng bước:
  MyQueue()  → khởi tạo
  push(1);  push(2)
  peek()    → 1   (FIFO: phần tử đẩy vào trước ra trước)
  pop()     → 1
  empty()   → false

Ràng buộc

• 1 <= x <= 9
• Số op ≤ 100

Clarifying questions

• O(1) worst-case? → Không thể với 2 stack thuần; O(1) amortized.

Hướng tiếp cận

Ý tưởng - 2 stack: in (input) và out (output). - push(x): push vào in. - pop / peek: nếu out rỗng → “đổ” toàn bộ in sang out (đảo thứ tự vì stack). Sau đó pop/peek từ out.

Phân tích amortized: Mỗi phần tử bị move giữa 2 stack tối đa 1 lần. Worst-case 1 op = O(n), nhưng amortized = O(1).

Hình minh hoạ với push(1), push(2), push(3), pop(), push(4), pop():

push(1): in=[1]              out=[]
push(2): in=[1, 2]           out=[]
push(3): in=[1, 2, 3]        out=[]

pop(): out rỗng → đổ in sang out
       in=[]                  out=[3, 2, 1]    (1 ở top)
       out.pop() → 1
       in=[]                  out=[3, 2]

push(4): in=[4]              out=[3, 2]

pop(): out không rỗng → out.pop() → 2
       in=[4]                out=[3]

→ FIFO: 1 ra trước (đúng thứ tự push)

Code Python 3

class MyQueue:
    def __init__(self):
        self.in_st: list[int] = []
        self.out_st: list[int] = []

    def push(self, x: int) -> None:
        self.in_st.append(x)

    def pop(self) -> int:
        self._shift()
        return self.out_st.pop()

    def peek(self) -> int:
        self._shift()
        return self.out_st[-1]

    def empty(self) -> bool:
        return not self.in_st and not self.out_st

    def _shift(self) -> None:
        """Khi out rỗng, đổ toàn bộ in sang out."""
        if not self.out_st:
            while self.in_st:
                self.out_st.append(self.in_st.pop())

Phân tích độ phức tạp

• Push: O(1). Pop / Peek: O(1) amortized (worst O(n)).

Bình luận

• Bẫy thường gặp: đổ in → out mỗi lần pop, kể cả khi out còn → sai thứ tự FIFO. Chỉ đổ khi out rỗng.
• Follow-up:
  • LC 225 - Implement Stack using Queues: ngược lại, dùng 1 queue với trick rotate.
  • Nếu phải O(1) worst-case → không thể với 2 stack thuần.

Bài tự luyện liên quan

• LC 225 - Implement Stack using Queues.
• LC 622 - Design Circular Queue.
• LC 1670 - Design Front Middle Back Queue.

---

8.4 Evaluate Reverse Polish Notation (LC 150)

Đề bài

Cho mảng tokens biểu diễn biểu thức Reverse Polish Notation (postfix). Mỗi token là số nguyên hoặc 1 trong 4 phép + - * /. Trả về kết quả (chia lấy phần nguyên hướng về 0).

Ví dụ

Input:  tokens = ["2","1","+","3","*"]
Output: 9
Giải thích: (2 + 1) * 3 = 9.

Input:  tokens = ["4","13","5","/","+"]
Output: 6
Giải thích: 4 + (13 / 5) = 4 + 2 = 6.

Input:  tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22

Ràng buộc

• 1 <= len(tokens) <= 10^4
• tokens[i] là số -200..200 hoặc một phép tính.

Clarifying questions

• Chia số âm? → Truncate towards 0 (int(a/b)).
• Token có thể có space? → Theo LC: không.

Hướng tiếp cận

RPN ↔︎ stack - kinh điển. Duyệt: - Số → push. - Phép → pop 2 phần tử (b lấy trước, a lấy sau), tính a op b, push kết quả.

Cuối cùng stack còn 1 phần tử = kết quả.

Hình minh hoạ với ["2","1","+","3","*"]:

token   action                      stack
─────────────────────────────────────────────
"2"     push 2                      [2]
"1"     push 1                      [2, 1]
"+"     pop b=1, a=2; push 3        [3]
"3"     push 3                      [3, 3]
"*"     pop b=3, a=3; push 9        [9]

Kết quả: 9

Code Python 3

from typing import List
import operator

class Solution:
    OPS = {
        '+': operator.add,
        '-': operator.sub,
        '*': operator.mul,
        '/': lambda a, b: int(a / b),   # chia hướng về 0
    }

    def evalRPN(self, tokens: List[str]) -> int:
        stack: list[int] = []
        for tk in tokens:
            if tk in self.OPS:
                b = stack.pop()
                a = stack.pop()
                stack.append(self.OPS[tk](a, b))
            else:
                stack.append(int(tk))
        return stack[0]

Phân tích độ phức tạp

• Thời gian: O(n). Bộ nhớ: O(n).

Bình luận

• Bẫy chia số âm: Python -7 // 2 == -4 (floor), nhưng đề yêu cầu truncate towards zero → int(-7 / 2) == -3. Dùng int(a / b) để đúng.
• Thứ tự pop quan trọng: b (right operand) pop trước, a (left) pop sau. Phép - và / không giao hoán.
• Follow-up:
  • Infix → Postfix (Shunting Yard).
  • Bài LC 224 / 227 - Basic Calculator (I, II) (Chương 32).

Bài tự luyện liên quan

• LC 224 - Basic Calculator.
• LC 227 - Basic Calculator II.
• LC 772 - Basic Calculator III.

---

8.5 Daily Temperatures (LC 739) - teaser monotonic stack

Đề bài

Cho mảng temperatures các nhiệt độ. Với mỗi ngày i, tìm xem bao nhiêu ngày sau đó mới có nhiệt độ cao hơn ngày i. Nếu không có, trả 0.

Ví dụ

Input:  temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]
Giải thích:
  day 0: 73 → ngày 1 (74) cao hơn → 1
  day 2: 75 → phải đợi tới ngày 6 (76) → 6-2=4
  day 6: 76 không có gì cao hơn → 0

Ràng buộc

• 1 <= len <= 10^5
• 30 <= temperatures[i] <= 100

Clarifying questions

• Nhiệt độ trùng? → Yêu cầu strictly higher → dùng < không phải <=.

Hướng tiếp cận

Brute force - O(n²). Với mỗi i, quét forward tìm cái lớn hơn. TLE khi n = 10^5.

Tối ưu - Monotonic decreasing stack - O(n).

Ý tưởng: Duy trì stack các index mà temperature giảm dần (từ đáy lên đỉnh). Khi gặp ngày i có nhiệt cao hơn top của stack → đó chính là “answer” cho ngày ở top. Pop và ghi result[top] = i - top.

Hình minh hoạ với [73, 74, 75, 71, 69, 72, 76, 73]:

i  temp   action                                stack (idx)    result
─────────────────────────────────────────────────────────────────────────
0  73     push 0                                [0]            [_, _, _, _, _, _, _, _]
1  74     74 > 73 → pop 0, result[0]=1-0=1     [1]            [1, _, _, _, _, _, _, _]
          push 1
2  75     75 > 74 → pop 1, result[1]=2-1=1     [2]            [1, 1, _, _, _, _, _, _]
          push 2
3  71     71 < 75 → push 3                     [2, 3]
4  69     69 < 71 → push 4                     [2, 3, 4]
5  72     72 > 69 → pop 4, result[4]=5-4=1     [2, 3, 5]
          72 > 71 → pop 3, result[3]=5-3=2
          push 5
6  76     76 > 72 → pop 5, result[5]=6-5=1     [6]
          76 > 75 → pop 2, result[2]=6-2=4
          push 6
7  73     73 < 76 → push 7                     [6, 7]

Còn lại trong stack: [6, 7] → result giữ 0.
Kết quả: [1, 1, 4, 2, 1, 1, 0, 0]  ✓

Stack invariant: index trong stack có temperature giảm dần từ đáy lên đỉnh. Mỗi index được push 1 lần, pop tối đa 1 lần → tổng O(n).

Code Python 3

from typing import List

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        result = [0] * n
        stack: list[int] = []   # các index có temperature giảm dần
        for i, t in enumerate(temperatures):
            while stack and temperatures[stack[-1]] < t:
                j = stack.pop()
                result[j] = i - j
            stack.append(i)
        return result

Phân tích độ phức tạp

• Thời gian: O(n) - mỗi index được push/pop tối đa 1 lần.
• Bộ nhớ: O(n).

Bình luận

• Tại sao monotonic stack work? Khi t[i] lớn hơn 1 phần tử ở stack, mọi phần tử dưới nữa (nếu cũng nhỏ hơn t[i]) đều đã có sẵn 1 ứng viên là i. Stack giảm dần nên ta chỉ cần pop các ô < t[i] từ trên xuống.
• Bẫy: dùng <= thay vì < → ngày sau bằng nhiệt sẽ tính là “ấm hơn”, sai đề.
• Liên kết: Đây là ngôn ngữ của Chương 18 (Monotonic Queue + Stack): Next Greater, Largest Rectangle, Sliding Window Max, … - cùng template.

Bài tự luyện liên quan

• LC 496 - Next Greater Element I.
• LC 503 - Next Greater Element II (mảng vòng).
• LC 84 - Largest Rectangle in Histogram (Chương 18).

---

8.6 Decode String (LC 394)

Đề bài

Cho chuỗi s mã hoá theo dạng k[encoded_string] - nghĩa là encoded_string sẽ được lặp k lần. Decode chuỗi.

Ví dụ

Input:  s = "3[a]2[bc]"
Output: "aaabcbc"

Input:  s = "3[a2[c]]"
Output: "accaccacc"   (lồng)

Input:  s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"

Ràng buộc

• 1 <= len(s) <= 30
• 1 <= k <= 300 (số nguyên)

Clarifying questions

• Số lặp có thể nhiều chữ số (10+)? → Có.
• Lồng tối đa bao nhiêu cấp? → Theo LC: ≤ 30 cấp.

Hướng tiếp cận

Cấu trúc lồng ⇒ dùng stack. Mỗi khi gặp [, ta “lưu” số k và chuỗi đang build vào stack, rồi reset chuỗi build. Khi gặp ], pop ra (prev_str, k) và nối prev_str + k * cur_str.

Cách 2 - Đệ quy. Mỗi k[...] thành 1 lần gọi đệ quy. Code gọn hơn nhưng tốn stack (đệ quy có thể vượt giới hạn với chuỗi lồng sâu).

Hình minh hoạ - Cách stack với "3[a2[c]]":

ch    action                                     stack         cur
─────────────────────────────────────────────────────────────────
'3'   k = 3                                      []           ""
'['   push (k, cur); reset k, cur                [(3, "")]    ""
'a'   cur += 'a'                                 [(3, "")]    "a"
'2'   k = 2                                      [(3, "")]    "a"
'['   push (k=2, cur="a"); reset k, cur          [(3, ""), (2, "a")]  ""
'c'   cur += 'c'                                 [(3, ""), (2, "a")]  "c"
']'   (prev_k=2, prev_str="a") = pop;
      cur = prev_str + prev_k * cur = "a" + "cc" [(3, "")]    "acc"
']'   (prev_k=3, prev_str="") = pop;
      cur = "" + 3 * "acc" = "accaccacc"         []           "accaccacc"

Kết quả: "accaccacc"  ✓

Code Python 3

class Solution:
    def decodeString(self, s: str) -> str:
        stack: list[tuple[str, int]] = []   # (prev_str, prev_k)
        cur, k = "", 0
        for ch in s:
            if ch.isdigit():
                k = k * 10 + int(ch)
            elif ch == '[':
                stack.append((cur, k))
                cur, k = "", 0
            elif ch == ']':
                prev_str, prev_k = stack.pop()
                cur = prev_str + cur * prev_k
            else:
                cur += ch
        return cur


class SolutionRecursive:
    """Cách 2 - đệ quy. Code clean nhưng tốn stack."""

    def decodeString(self, s: str) -> str:
        self.i = 0
        return self._decode(s)

    def _decode(self, s: str) -> str:
        result = ""
        k = 0
        while self.i < len(s) and s[self.i] != ']':
            ch = s[self.i]
            if ch.isdigit():
                k = k * 10 + int(ch)
                self.i += 1
            elif ch == '[':
                self.i += 1
                inner = self._decode(s)
                result += k * inner
                k = 0
                self.i += 1     # skip ']'
            else:
                result += ch
                self.i += 1
        return result

Phân tích độ phức tạp

• Thời gian: O(N) với N là độ dài chuỗi output (mỗi ký tự được tạo 1 lần).
• Bộ nhớ: O(N).

Bình luận

• Bẫy thường gặp:
  • Đọc số nhiều chữ số: k = k * 10 + int(ch) (vì 10[ab] có k = 10).
  • Quên reset k = 0 sau khi push.
  • Thứ tự prev_str + cur * prev_k - chuỗi đã build trước [ đứng bên trái.
• Follow-up:
  • LC 726 - Number of Atoms (Chương 32): cùng pattern stack lồng nhưng parse công thức hoá học.
  • LC 1190 - Reverse Substrings Between Each Pair of Parentheses.

Bài tự luyện liên quan

• LC 726 - Number of Atoms.
• LC 1190 - Reverse Substrings Between Each Pair of Parentheses.
• LC 856 - Score of Parentheses.

Tóm tắt chương & Quyết định

Stack mental models

Mục đích	Stack chứa gì	Bài ví dụ
Match cặp đối xứng	Mở ngoặc / token chờ đóng	LC 20, 1249
Lưu token trước đó chưa hoàn tất	Số / chuỗi cần “expand” sau	LC 394 Decode
Undo / context	Phép tính cha	LC 224 Calculator
Monotonic	Index/value tăng/giảm	Chương 18
Iterative DFS	Frame call	Tree iterative inorder

Decode String (LC 394) - trace 3[a2[c]]

Bước	Char	num	cur	numStack	strStack
0	3	3	""	[]	[]
1	[	0	""	[3]	[""]
2	a	0	"a"	[3]	[""]
3	2	2	"a"	[3]	[""]
4	[	0	""	[3,2]	["", "a"]
5	c	0	"c"	[3,2]	["", "a"]
6	]	0	"acc" (a + c×2)	[3]	[""]
7	]	0	"accaccacc" (×3)	[]	[]

RPN (LC 150) - thứ tự operand

Pop b trước, a sau, tính a op b. Nhầm thứ tự là bug điển hình với - và /.

Min Stack so sánh

• Pair stack (val, current_min): code đơn giản, O(n) bộ nhớ.
• Aux stack chỉ push khi val ≤ current min, pop khi top main == top aux: tiết kiệm bộ nhớ khi nhiều giá trị lớn.

---