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, chỉ thêm và lấy ở một đầu duy nhất. Push, pop, peek đều O(1). Cùng một cơ chế này làm nút Back/Forward của browser hoạt động, làm Ctrl+Z trong editor, làm bước kiểm tra ngoặc đóng mở trong compiler, và làm JVM call stack. Trong Java, đừng dùng java.util.Stack cũ: nó synchronized (khoá mọi thao tác, tốn chi phí thừa) 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 lệnh return của hàm trong JVM (frame gần nhất được giải phóng trước), và làm bước kiểm tra ngoặc trong compiler (ngoặc đóng phải khớp với ngoặc mở gần nhất). Stack là cấu trúc dữ liệu thêm và xoá ở một đầu với O(1). Bài này chỉ ra khi nào nên chọn stack thay vì queue hoặc list, cách cài đặt đúng, và cái bẫy khi dùng java.util.Stack đời cũ trong code thật.

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ì chỉ đụng vào một đầu cố định, không cần duyệt qua các phần tử, cũng không phải dời phần tử nào.

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

Stack cài trên array 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()
    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ể

Dòng data[top] <- null trong pop() rất quan trọng: xoá tham chiếu để GC thu hồi được object. Bỏ dòng này sẽ rò rỉ bộ nhớ (memory leak), vì mảng nền vẫn giữ tham chiếu đến object đã "xoá". Cơ chế grow() giống ArrayList.grow(): tăng 1.5 lần để chi phí copy được chia đều (amortized) cho nhiều lần push.

Thử ngẫmpop() gán data[top] <- null trước khi giảm top. Bỏ dòng đó, stack vẫn chạy đúng chức năng. Vậy chỗ sai sẽ lộ ra ở đâu?

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

Dùng singly linked list với head đóng vai trò top. Push và pop đều làm ở head, không cần duyệt cả list, nên 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 phải cấp phát một 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)

Cấu trúc Node và những điểm được/mất của singly linked list đã phân tích ở bài 02 của module này.

Cài trên array thì liên tiếp trong bộ nhớ nên thân thiện với cache, đổi lại thỉnh thoảng phải copy khi grow. Cài trên linked list thì mỗi push cấp phát một Node (~24 byte), nhưng không bao giờ copy. Với tải thông thường, bản array thắng nhờ cache locality; linked list chỉ đáng khi cần giới hạn bộ nhớ chặt hoặc hay phải gộp/tách stack.

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 tiêu biểu nhất cho stack: gặp ngoặc mở thì push, gặp ngoặc đóng thì pop và kiểm tra xem có khớp không.

isBalanced(s):
    S <- Stack rỗng
    for each ký tự c trong s:
        if c là '(', '[', hoặc '{':
            S.push(c)                   -- push ngoặc mở
        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 (nếu chưa quen đọc bảng theo dõi từng bước thế này, ôn lại ở Bảng trace):

Ba edge case cần nhớ:

• 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.

Thử ngẫmđổi input mẫu thành ({[}]) — ký tự nào làm khớp() trả false đầu tiên, và stack lúc đó còn lại gì?

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. Có ba lý do:

1. Method nào cũng synchronized: mọi method kế thừa từ Vector đều lấy lock, tốn chi phí thừa khi chương trình chỉ chạy một thread. ArrayDeque không synchronized nên nhanh hơn rõ rệt ở đoạn code chạy dày.
2. Kế thừa API của Vector: Stack extends Vector nên lộ ra addElement(), set(i, x), get(i). Các method này cho phép truy cập tuỳ ý và phá quy tắc LIFO (vốn phải luôn đúng với stack). Code nhìn như stack nhưng thực ra đang dùng như list.
3. Javadoc khuyên dùng cái khá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)   -- method của Vector -- phá quy tắc LIFO
bad.set(0, 99)      -- truy cập tuỳ ý qua Vector -- phá quy tắc stack

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

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

Khi dùng ArrayDeque làm stack, push/pop/peek đều thao tác ở head, nên peek() trả đúng top. Cái bẫy là peekLast(): nó trả phần tử ở đáy stack, không phải top.

stack.push(1); stack.push(2); stack.push(3)
stack.peek()        -- 3: top
stack.peekLast()    -- 1: đáy, không phải top!

Quy tắc: dùng Deque làm stack thì chỉ dùng push/pop/peek (hoặc addFirst/removeFirst/peekFirst).

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 trên cấu trúc dữ liệu ArrayDeque. Hai thứ này 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 theo kích thước heap (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

Mỗi lần gọi hàm là một frame mới chồng lên call stack, nên đệ quy sâu chính là stack này đầy dần (nếu muốn ôn hàm gọi hàm hoạt động ra sao, xem Hàm). Khi DFS đệ quy gặp cây quá sâu, cách xử lý đúng là tự quản lý một Deque trên heap, vì heap lớn hơn thread stack rất nhiều. Cơ chế call stack và lý do JVM không tối ưu đệ quy đuôi nằm ở bài 02 Module 1.

Thử ngẫmpitfall 3 tách bạch call stack (giới hạn theo -Xss) với data stack trên heap. DFS đệ quy trên cây sâu 50.000 tầng nên dùng loại stack nào trong hai loại đó?

7. Applied to tech

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

Text editor undo/redo: Mỗi thao tác sửa push một command object lên undo stack. Ctrl+Z pop từ undo stack để hoàn tác, đồng thời push lên redo stack. Ctrl+Y pop từ redo stack. Bất kỳ thao tác mới nào cũng xoá redo stack. Vim dùng một stack kèm cây rẽ nhánh nên phức tạp hơn, nhưng nguyên lý cơ bản vẫn vậy.

Compiler expression evaluation: Thuật toán Shunting-yard của Dijkstra dùng hai stack (một cho toán tử, một cho toán hạng) để chuyển biểu thức viết kiểu thông thường (infix) sang Reverse Polish Notation (RPN, ký hiệu Ba Lan ngược). Ví dụ (2 + 3) * 4 → 2 3 + 4 *. Có RPN rồi thì tính giá trị bằng một stack: gặp số thì push, gặp toán tử thì pop hai toán hạng, tính rồi push kết quả.

8. ArrayDeque source: Cơ chế grow

java.util.ArrayDeque là bản cài đặt được khuyên dùng cho cả stack lẫn queue trong Java thực tế. Mảng nền của nó là circular array: array có head và tail index quay vòng được (wrap around), chi tiết ở bài tiếp theo.

Quy ước khi dùng làm stack: push(x) là addFirst(x), pop() là removeFirst(), nên head của deque là top.

Ở JDK 21 (bản bài này nhắm tới) mảng nền không còn bị ép là luỹ thừa của 2. Khi mảng đầy, grow() trong OpenJDK 21 thêm capacity + 2 ô nếu capacity nhỏ hơn 64 (gần như gấp đôi), còn lại thêm 50%. Ý tưởng chia đều chi phí copy (amortization) giống ArrayList.grow().

9. Deep Dive

10. Tóm tắt

• Stack là LIFO: chỉ thao tác ở một đầu, nên push/pop/peek đều O(1).
• Dùng Deque<T> stack = new ArrayDeque<>(), đừng dùng java.util.Stack (synchronized, kế thừa Vector nên lộ API phá luật LIFO). push = addFirst, pop = removeFirst, và peekLast() trả về đáy chứ không phải top.
• Kiểm tra ngoặc cân bằng: gặp ngoặc mở thì push, gặp ngoặc đóng thì pop và đối chiếu, cuối cùng stack phải rỗng.
• Call stack khác data stack: StackOverflowError xảy ra trên thread stack (giới hạn -Xss), còn ArrayDeque nằm trên heap. DFS đệ quy sâu thì đổi sang Deque tự quản lý.
• Mẫu hai stack (browser back/forward, undo/redo): một stack lưu quá khứ, một stack lưu những gì có thể quay lại.

11. Tự kiểm tra

Bài tiếp theo: Queue & Deque