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

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

ASCII diagram bốn thao tác cơ bản:

Initial:    push(10):   push(20):   pop():      peek():
|   |       |   |       |20 |       |   |       |10 |
|   |       |10 |       |10 |       |10 |       |10 |
|___|       |___|       |___|       |___|       |___|
empty       top=10      top=20      top=10      top=10
                                   returns 20  returns 10
                                               (no remove)

3. Implement bằng array (Java)

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.

public class MyStack<T> {
    private Object[] data;
    private int top = -1;

    public MyStack(int capacity) {
        data = new Object[capacity];
    }

    public void push(T item) {
        if (top + 1 == data.length) grow();
        data[++top] = item;
    }

    @SuppressWarnings("unchecked")
    public T pop() {
        if (top < 0) throw new IllegalStateException("Stack empty");
        T item = (T) data[top];
        data[top--] = null; // help GC
        return item;
    }

    @SuppressWarnings("unchecked")
    public T peek() {
        if (top < 0) throw new IllegalStateException("Stack empty");
        return (T) data[top];
    }

    public boolean isEmpty() { return top < 0; }

    public int size() { return top + 1; }

    private void grow() {
        // Same 1.5x strategy as ArrayList -- see Module 1 lesson 07
        int newCapacity = data.length + (data.length >> 1);
        data = java.util.Arrays.copyOf(data, newCapacity);
    }
}

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

public class LinkedStack<T> {
    private static class Node<T> {
        T data;
        Node<T> next;
        Node(T data, Node<T> next) {
            this.data = data;
            this.next = next;
        }
    }

    private Node<T> head;
    private int size;

    public void push(T item) {
        head = new Node<>(item, head); // new node points to old head
        size++;
    }

    public T pop() {
        if (head == null) throw new IllegalStateException("Stack empty");
        T item = head.data;
        head = head.next; // advance head, old node GC'd
        size--;
        return item;
    }

    public T peek() {
        if (head == null) throw new IllegalStateException("Stack empty");
        return head.data;
    }

    public boolean isEmpty() { return head == null; }

    public int size() { return size; }
}

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.

public boolean isBalanced(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        switch (c) {
            case '(', '[', '{' -> stack.push(c);
            case ')', ']', '}' -> {
                if (stack.isEmpty()) return false;
                char open = stack.pop();
                if (!matches(open, c)) return false;
            }
        }
    }
    return stack.isEmpty();
}

private boolean matches(char open, char close) {
    return (open == '(' && close == ')')
        || (open == '[' && close == ']')
        || (open == '{' && close == '}');
}

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:

// WRONG: java.util.Stack -- legacy, synchronized, exposes Vector methods
Stack<Integer> bad = new Stack<>();
bad.push(1);
bad.push(2);
bad.addElement(3);   // Vector method -- breaks LIFO invariant conceptually
bad.set(0, 99);      // random access via Vector -- phá invariant stack
bad.pop();           // synchronized overhead du single-thread

// CORRECT: Deque<T> with ArrayDeque backing
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
stack.pop();         // O(1), no synchronization overhead

Ba lý do cụ thể:

1. Synchronized methods: Mọi method của Stack (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."

Cách đúng: Deque<T> stack = new ArrayDeque<>() và dùng push/pop/peek.

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:

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);  // addFirst(1) -- head = 1
stack.push(2);  // addFirst(2) -- head = 2
stack.push(3);  // addFirst(3) -- head = 3

// Dung lam stack: 3 la top
stack.peek();      // 3 -- correct, Queue.peek() = head = top
stack.peekFirst(); // 3 -- explicit, ro rang hon
stack.peekLast();  // 1 -- day la bottom cua stack, KHONG phai 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 — đây là nguồn nhầm lẫn số 1 của intern khi code review.

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 -- gioi han boi -Xss (512KB-1MB theo thread)
// Recursion sau 10k-20k frame la StackOverflowError
void recursive(int n) {
    recursive(n - 1); // moi call push 1 frame len thread stack
}

// Data stack tren heap -- gioi han boi heap size (thong thuong vai GB)
// Xu ly 1 trieu phan tu khong van de
Deque<Integer> dataStack = new ArrayDeque<>();
for (int i = 0; i < 1_000_000; i++) {
    dataStack.push(i); // alloc tren heap, khong tieu thu 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: Module 5 (Graph) 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 (không thể forward về trang chưa ghé thăm).

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ả. Module 4 (sorting/parsing) 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. Module 5 (Graph) sẽ implement DFS cả hai cách và so sánh.

8. Java ArrayDeque source

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.

// ArrayDeque: push(x) = addFirst(x), pop() = removeFirst()
// Dung vì Deque la 2-end, nhung convention stack dung head la top
Deque<String> stack = new ArrayDeque<>();
stack.push("a");   // addFirst("a")
stack.push("b");   // addFirst("b")
stack.push("c");   // addFirst("c")
System.out.println(stack.pop()); // "c" -- removeFirst()
System.out.println(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:

// Trich tu OpenJDK 21 -- java.util.ArrayDeque.grow()
private void grow(int needed) {
    final int oldCapacity = elements.length;
    int newCapacity;
    // Double size if small; else grow by 50%
    int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1);
    if (jump < needed
        || (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0)
        newCapacity = newCapacity(needed);
    elements = Arrays.copyOf(elements, newCapacity);
}

Với capacity nhỏ hơn 64 thì tăng gần gấp đôi, lớn hơn thì tăng 50% — 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 Java — 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

public String reverse(String s) {
  Deque<Character> stack = new ArrayDeque<>();
  for (char c : s.toCharArray()) {
      stack.push(c);
  }
  StringBuilder sb = new StringBuilder();
  while (!stack.isEmpty()) {
      sb.append(stack.pop());
  }
  return sb.toString();
}

Bài tiếp theo: Queue & Deque