Stack — LIFO từ chồng đĩa đến JVM call stack

TL;DR: Stack là cấu trúc dữ liệu LIFO (Last In, First Out) — phần tử vào sau sẽ ra trước, thao tác chỉ xảy ra ở một đầu duy nhất. Push, pop, peek đều O(1). Cùng một cơ chế làm browser Back/Forward hoạt động, Ctrl+Z trong editor, balanced bracket check trong compiler, và JVM call stack. Trong Java, không bao giờ dùng java.util.Stack cũ — nó synchronized và kế thừa API sai từ Vector. Dùng Deque<T> stack = new ArrayDeque<>() thay thế.

Bạn mở browser, click liên tiếp 5 link: A → B → C → D → E. Bấm Back: E biến mất, D hiện ra. Bấm tiếp: C, rồi B, rồi A — luôn theo thứ tự ngược lại. Cùng cơ chế đó làm Ctrl+Z trong editor (lệnh cuối undo trước), làm function call return trong JVM (frame gần nhất được giải phóng trước), làm balanced bracket check trong compiler (đóng ngoặc phải khớp mở ngoặc gần nhất). Stack là CTDL O(1) insert và remove ở một đầu — bài này phân biệt khi nào pick stack thay queue hoặc list, cách implement đúng, và pitfall production khi dùng java.util.Stack legacy.

1. Analogy — Chồng đĩa

Hình dung chồng đĩa trong bếp:

• Đặt đĩa vào: bạn đặt lên trên cùng.
• Lấy đĩa ra: bạn lấy cái trên cùng.
• Không thể lấy đĩa ở giữa mà không xáo trộn cả chồng.

Đây là LIFO — Last In, First Out. Cái vào sau cùng ra trước tiên.

2. Operations và complexity

Tất cả đều O(1) vì thao tác chỉ xảy ra ở một đầu cố định — không cần traverse, không cần shift.

graph LR
    A(["push(10)"])
    B(["push(20)"])
    C(["pop() → 20"])
    D(["peek() → 10"])

    A --> B --> C --> D

Sơ đồ trạng thái stack qua 4 thao tác cơ bản:

Trạng thái ban đầu:    push(10):    push(20):    pop():       peek():
|      |               |      |      | [20] |     |      |    | [10] |
|      |               | [10] |      | [10] |     | [10] |    | [10] |
|______|               |______|      |______|     |______|    |______|
rỗng                   top=10        top=20        top=10      top=10
                                                  trả về 20   trả về 10
                                                              (không xoá)

3. Pseudocode implement bằng array

Array-backed stack dùng một index top trỏ vào phần tử trên cùng. top = -1 nghĩa là stack rỗng.

-- Stack cài trên array với tự động grow
Stack:
    data[]   -- backing array
    top      -- index của top element, -1 nếu rỗng

push(S, item):
    if S.top + 1 = S.data.length:
        grow(S)           -- tăng 1.5x như ArrayList.grow() bài 07 Module 1
    S.top <- S.top + 1
    S.data[S.top] <- item

Time: O(1) amortized Space: O(1)

pop(S):
    if S.top < 0: throw "Stack rỗng"
    item <- S.data[S.top]
    S.data[S.top] <- null   -- giải phóng reference để GC thu hồi object
    S.top <- S.top - 1
    return item

Time: O(1) Space: O(1)

peek(S):
    if S.top < 0: throw "Stack rỗng"
    return S.data[S.top]

isEmpty(S):
    return S.top < 0

size(S):
    return S.top + 1

Time: O(1) cho mọi operation Space: O(n) tổng thể

data[top] <- null trong pop() là quan trọng: xóa reference giúp GC thu hồi object — không làm sẽ gây memory leak vì backing array vẫn giữ tham chiếu đến object đã "xóa". Cơ chế grow() tương tự ArrayList.grow() đã phân tích ở bài 07 Module 1 — tăng 1.5x để amortize cost.

4. Pseudocode implement bằng linked list (alternative)

Dùng singly linked list với head đóng vai trò top. Push và pop đều thao tác ở head — không cần traverse, luôn O(1).

-- Stack cài trên singly linked list
-- head đóng vai trò top stack
Node:
    data
    next

LinkedStack:
    head   -- node top (null nếu rỗng)
    size

push(S, item):
    newNode <- Node(item, next=S.head)   -- node mới trỏ vào old head
    S.head <- newNode
    S.size <- S.size + 1

Time: O(1) Space: O(1) mỗi push (nhưng alloc Node object)

pop(S):
    if S.head = null: throw "Stack rỗng"
    item <- S.head.data
    S.head <- S.head.next   -- advance head, old node sẽ được GC
    S.size <- S.size - 1
    return item

Time: O(1) Space: O(1)

Cross-link: cấu trúc Node và trade-off singly linked list đã phân tích ở bài 02 Module 2.

So sánh hai cách implement:

Với workload thông thường, array-backed thắng nhờ cache locality. Linked list thắng khi cần bounded memory nghiêm ngặt — không bao giờ alloc quá N phần tử — hoặc khi merge/split stack là thao tác thường xuyên.

5. Bài kinh điển — Balanced bracket check

Kiểm tra xâu ký tự có đóng mở ngoặc hợp lệ không là bài đặc trưng nhất cho stack: mỗi khi gặp mở ngoặc thì push, gặp đóng ngoặc thì pop và kiểm tra khớp.

isBalanced(s):
    S <- Stack rỗng
    for each ký tự c trong s:
        if c là '(', '[', hoặc '{':
            S.push(c)                   -- push mở ngoặc
        else if c là ')', ']', hoặc '}':
            if S.isEmpty(): return false
            open <- S.pop()
            if không khớp(open, c): return false
    return S.isEmpty()                  -- hợp lệ nếu stack rỗng sau khi duyệt hết

khớp(open, close):
    return (open='(' và close=')') hoặc
           (open='[' và close=']') hoặc
           (open='{' và close='}')

Time: O(n) Space: O(n) worst case (toàn mở ngoặc)

Trace ví dụ ({[]}) từng bước:

Ba edge case quan trọng:

• Input rỗng "" → vòng lặp không chạy, isEmpty() = true → trả về true. Đúng theo định nghĩa.
• Thiếu đóng ngoặc (() → cuối vòng lặp stack còn [(], isEmpty() = false → trả về false.
• Thừa đóng ngoặc )abc → gặp ) đầu tiên, stack rỗng → trả về false ngay.

6. Pitfall tổng hợp

Pitfall 1 — Đừng dùng java.util.Stack

java.util.Stack có trong JDK từ Java 1.0 (1996) và là lựa chọn sai cho mọi code mới. Ba lý do cụ thể:

1. Synchronized methods: Mọi method kế thừa từ Vector đều synchronized — lock overhead không cần thiết trong single-threaded context. ArrayDeque không synchronized, nhanh hơn đáng kể trong hot path.
2. Kế thừa Vector API: Stack extends Vector, lộ ra addElement(), set(i, x), get(i) — cho phép random access phá vỡ invariant LIFO. Code nhìn như stack nhưng thực ra dùng như list.
3. Recommendation chính thức: Javadoc của java.util.Stack ghi rõ: "A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class."

-- SAI: java.util.Stack -- synchronized, kế thừa Vector
bad <- new Stack()
bad.push(1)
bad.push(2)
bad.addElement(3)   -- Vector method -- phá invariant LIFO
bad.set(0, 99)      -- random access qua Vector -- phá invariant stack

-- ĐÚNG: Deque với ArrayDeque backing
stack <- new ArrayDeque()   -- khai báo qua Deque interface
stack.push(1)
stack.push(2)
stack.pop()         -- O(1), không synchronized overhead

Pitfall 2 — Deque.peek() trả về đầu nào?

Deque là double-ended queue — có hai đầu. Khi dùng ArrayDeque làm stack, convention là push/pop/peek thao tác ở head (đầu trái). Nhưng Deque kế thừa từ Queue, và peek() của Queue trả về head — nhìn đúng, nhưng dễ nhầm:

stack <- new ArrayDeque()
stack.push(1)       -- addFirst(1) -- head = 1
stack.push(2)       -- addFirst(2) -- head = 2
stack.push(3)       -- addFirst(3) -- head = 3

-- Dùng làm stack: 3 là top
stack.peek()        -- 3 -- đúng, Queue.peek() = head = top
stack.peekFirst()   -- 3 -- explicit, rõ ràng hơn
stack.peekLast()    -- 1 -- đây là BOTTOM của stack, KHÔNG phải top!

Rule: khi dùng Deque làm stack, dùng push/pop/peek hoặc tương đương explicit addFirst/removeFirst/peekFirst. Tuyệt đối không dùng peekLast/pollLast vì sẽ thao tác từ phía bottom.

Pitfall 3 — Stack overflow JVM call stack khác data stack

StackOverflowError trong JVM xảy ra trên call stack của thread, không phải ArrayDeque data structure. Hai thứ hoàn toàn khác nhau:

-- JVM call stack: giới hạn bởi -Xss (512KB-1MB mỗi thread)
-- Đệ quy sâu 10k-20k frame là StackOverflowError
recursive(n):
    recursive(n - 1)   -- mỗi call push 1 frame lên thread stack

-- Data stack trên heap: giới hạn bởi heap size (thường vài GB)
-- Xử lý 1 triệu phần tử không vấn đề
dataStack <- new ArrayDeque()
for i <- 0 đến 999999:
    dataStack.push(i)   -- alloc trên heap, không tiêu thụ thread stack

Khi thuật toán DFS đệ quy gặp cây sâu, giải pháp đúng là chuyển sang explicit Deque trên heap — heap lớn hơn thread stack hàng nghìn lần. Bài 02 Module 1 đã phân tích chi tiết cơ chế call stack và lý do JVM không có TCO. Cross-link: Thuật toán Cốt lõi — Module 3 (Đồ thị) sẽ dùng pattern explicit stack cho DFS tránh StackOverflowError trên graph sâu.

7. Applied to tech

JVM call stack: Mỗi method call push một stack frame lên thread stack, mỗi return pop frame đó. Frame chứa local variables, parameters, return address. StackOverflowError xảy ra khi recursion quá sâu và frame vượt giới hạn -Xss. Bài 02 Module 1 phân tích đầy đủ cơ chế này.

Browser back và forward: Browser dùng hai stack: back stack và forward stack. Click link mới → push URL hiện tại lên back stack. Bấm Back → pop từ back stack, push URL vừa rời lên forward stack. Bấm Forward → pop từ forward stack. Nếu click link mới từ giữa lịch sử → forward stack bị xóa sạch.

Text editor undo/redo: Mỗi thao tác edit push một command object lên undo stack. Ctrl+Z pop từ undo stack và revert, đồng thời push lên redo stack. Ctrl+Y pop từ redo stack. Thao tác mới bất kỳ xóa redo stack. Vim dùng một stack với branching tree — phức tạp hơn nhưng cùng nguyên lý cơ bản.

Compiler expression evaluation: Thuật toán Shunting-yard của Dijkstra dùng hai stack (operator stack và operand stack) để chuyển infix expression thành Reverse Polish Notation (RPN). Ví dụ (2 + 3) * 4 → 2 3 + 4 *. Sau khi có RPN, evaluate bằng một stack: gặp số thì push, gặp operator thì pop hai operand, tính và push kết quả. Thuật toán Cốt lõi — Module 2 (Sắp xếp) sẽ phân tích đầy đủ.

DFS implementation: DFS đệ quy dùng JVM call stack — nguy hiểm với graph sâu tùy ý. DFS lặp dùng explicit Deque trên heap — an toàn hơn vì heap thường lớn hơn thread stack hàng nghìn lần. Thuật toán Cốt lõi — Module 3 (Đồ thị) sẽ implement DFS cả hai cách và so sánh.

8. ArrayDeque source — Cơ chế grow

java.util.ArrayDeque là implementation được khuyến nghị cho cả stack lẫn queue trong production Java. Backing là một circular array — không phải array thông thường mà là array với head và tail index có thể wrap around.

-- push(x) = addFirst(x), pop() = removeFirst()
-- Dùng vì Deque là 2-end, nhưng convention stack dùng head là top
stack <- ArrayDeque rỗng
stack.push("a")    -- addFirst("a")
stack.push("b")    -- addFirst("b")
stack.push("c")    -- addFirst("c")
stack.pop()        -- "c" -- removeFirst()
stack.pop()        -- "b"

Capacity luôn là power-of-2 (8, 16, 32...). Khi backing array đầy, grow() trong OpenJDK 21 tăng gấp đôi với capacity nhỏ hơn 64, tăng 50% khi lớn hơn — cùng triết lý amortization với ArrayList.grow() ở bài 07 Module 1.

9. Deep Dive

10. Tóm tắt

• Stack là LIFO: Last In, First Out — chỉ thao tác ở một đầu. push/pop/peek đều O(1).
• Dùng Deque<T> stack = new ArrayDeque<>() trong production — không dùng java.util.Stack (synchronized, kế thừa Vector, API không sạch).
• ArrayDeque dùng circular array — cache-friendly, không có pointer chasing. push = addFirst, pop = removeFirst.
• peek() của Deque trả về head — đúng khi dùng làm stack. Tránh nhầm với peekLast() là bottom của stack.
• JVM call stack khác data stack: StackOverflowError xảy ra trên thread stack (giới hạn Xss), không liên quan đến ArrayDeque trên heap.
• Balanced bracket check là bài kinh điển: push khi gặp mở ngoặc, pop và kiểm tra khớp khi gặp đóng ngoặc, trả về isEmpty() cuối vòng lặp.
• DFS đệ quy dùng JVM call stack; DFS lặp dùng explicit Deque trên heap — an toàn hơn với input sâu tùy ý.
• Two-stack pattern (browser back/forward, undo/redo) là ứng dụng thực tế quan trọng — một stack lưu lịch sử, một stack lưu trạng thái tương lai.

11. Tự kiểm tra

reverse(s):
  S <- Stack rỗng
  for each ký tự c trong s:
      S.push(c)
  result <- ""
  while not S.isEmpty():
      result <- result + S.pop()
  return result

Bài tiếp theo: Queue & Deque