Stack & Queue — Cấu trúc dữ liệu cơ bản

Stack — Last In, First Out (LIFO)

Hình dung Stack như chồng đĩa: đĩa đặt lên cuối cùng sẽ được lấy ra đầu tiên.

push(1)  push(2)  push(3)  pop()
                   
  ┌─┐     ┌─┐     ┌─┐     ┌─┐
  │1│     │2│     │3│     │2│    → trả về 3
  └─┘     │1│     │2│     │1│
          └─┘     │1│     └─┘
                  └─┘

Operations

Implement bằng Array

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

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

    public void push(T item) {
        data[++top] = item;
    }

    @SuppressWarnings("unchecked")
    public T pop() {
        T item = (T) data[top];
        data[top--] = null;
        return item;
    }

    @SuppressWarnings("unchecked")
    public T peek() {
        return (T) data[top];
    }

    public boolean isEmpty() {
        return top == -1;
    }
}

Ứng dụng: Kiểm tra ngoặc hợp lệ

Bài kinh điển trong coding interview:

public boolean isValid(String s) {
    Stack<Character> stack = new Stack<>();

    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else {
            if (stack.isEmpty()) return false;
            char open = stack.pop();
            if (c == ')' && open != '(') return false;
            if (c == ']' && open != '[') return false;
            if (c == '}' && open != '{') return false;
        }
    }

    return stack.isEmpty();
}

isValid("({[]})");  // true
isValid("([)]");    // false

Queue — First In, First Out (FIFO)

Hình dung Queue như hàng đợi mua vé: ai đến trước được phục vụ trước.

enqueue(1)  enqueue(2)  enqueue(3)  dequeue()

Front→ ┌─┐     ┌─┬─┐     ┌─┬─┬─┐     ┌─┬─┐ ←Back
       │1│     │1│2│     │1│2│3│     │2│3│    → trả về 1
       └─┘     └─┴─┘     └─┴─┴─┘     └─┴─┘

Operations

Implement bằng LinkedList

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

    private Node<T> front, back;

    public void enqueue(T item) {
        Node<T> node = new Node<>(item);
        if (back != null) back.next = node;
        back = node;
        if (front == null) front = back;
    }

    public T dequeue() {
        T data = front.data;
        front = front.next;
        if (front == null) back = null;
        return data;
    }

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

Ứng dụng: BFS (Breadth-First Search)

public void bfs(Node root) {
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        Node current = queue.poll();
        System.out.println(current.value);

        for (Node child : current.children) {
            queue.add(child);
        }
    }
}

So sánh Stack vs Queue