Ôn bài một chút, Stack, Queue, Deque và Priority Queue

Nếu bạn từng thắc mắc tại sao browser có thể "back" lại trang trước, hay làm sao XCOM biết đến lượt ai tấn công, hoặc Netflix xử lý hàng triệu video request như thế nào - thì câu trả lời nằm ở 4 cấu trúc dữ liệu huyền thoại này. Hãy cùng khám phá từ nguồn gốc lịch sử cho đến những ứng dụng điên rồ trong game AAA và hệ thống web khổng lồ!

Chuyện kể từ những năm 1940s - ai đã phát minh ra chúng?

Stack - từ "bury" và "unbury" của Alan Turing

Năm 1946, khi máy tính còn to bằng cả căn phòng, Alan Turing đã mô tả một cơ chế lưu trữ kỳ lạ trong báo cáo về ACE (Automatic Computing Engine). Ông gọi nó là "bury" (chôn) và "unbury" (đào lên) - cách thức để máy tính nhớ được mình đang làm gì khi phải tạm dừng để làm việc khác.

Nhưng phải đến năm 1955, hai nhà khoa học Đức Friedrich Bauer và Klaus Samelson tại Đại học Kỹ thuật Munich mới chính thức phát minh ra Stack. Họ gọi nó là "Operationskeller" - tiếng Đức có nghĩa là "hầm chứa phép toán". Tên gọi này cực kỳ hình tượng - giống như bạn chất đồ xuống hầm, cái nào bỏ xuống sau cùng thì phải lấy lên đầu tiên!

Fun fact: Năm 1988, Bauer nhận giải IEEE Computer Pioneer Award cho phát minh này. Samelson không kịp nhận vì đã qua đời.

Queue - từ bài toán điện thoại Copenhagen

Story này thú vị lắm! Năm 1909, Agner Krarup Erlang - một kỹ sư người Đan Mạch làm việc cho Copenhagen Telephone Exchange - gặp phải vấn đề: làm sao biết cần bao nhiêu đường dây điện thoại để khách hàng không phải chờ quá lâu?

Erlang phát hiện ra rằng các cuộc gọi đến theo phân phối Poisson (một kiểu random nhưng có quy luật), và ông phát triển toàn bộ lý thuyết hàng đợi (queueing theory) từ đó. Đến nay, đơn vị đo cường độ traffic điện thoại vẫn được gọi là "Erlang" để tôn vinh ông!

Deque - tiến hóa tự nhiên

Không giống Stack và Queue có "cha đẻ" rõ ràng, Deque (Double-Ended Queue) xuất hiện một cách tự nhiên trong những năm 1960-70s khi các lập trình viên nhận ra: "Ủa, sao không cho phép thêm/xóa ở cả hai đầu luôn?". Đây là minh chứng cho việc cộng đồng lập trình viên đôi khi tạo ra innovation một cách tập thể!

Priority Queue - và câu chuyện về Heapsort

Năm 1964, J.W.J. Williams - một lập trình viên người Anh làm việc cho Elliot Brothers - phát minh ra binary heap và thuật toán heapsort. Williams sinh năm 1930 tại Chippenham, Anh, và phát minh này của ông đã tạo ra cách triển khai Priority Queue hiệu quả với độ phức tạp O(log n).

Thú vị là Williams phát triển heap không phải vì muốn tạo Priority Queue, mà vì muốn có thuật toán sắp xếp tốt hơn! Ông muốn một thuật toán vừa nhanh (O(n log n)) vừa không tốn thêm bộ nhớ. Kết quả là binary heap - có thể lưu trong array mà không cần pointer!

Nguyên lý hoạt động - dễ hiểu như ăn Pringles

Stack (LIFO - Last In First Out)

Hình dung đơn giản: Hộp Pringles! Chip cuối cùng bạn bỏ vào là chip đầu tiên bạn lấy ra.

Stack<String> browserHistory = new Stack<>();
browserHistory.push("google.com");     // Vào Google
browserHistory.push("facebook.com");   // Vào Facebook  
browserHistory.push("youtube.com");    // Vào YouTube

String lastPage = browserHistory.pop(); // Lấy ra "youtube.com"
// Giống như bấm nút Back trên browser!

Operations cơ bản:

• push(item): Thêm vào đỉnh - O(1)
• pop(): Lấy và xóa từ đỉnh - O(1)
• peek(): Xem đỉnh không xóa - O(1)

Queue (FIFO - First In First Out)

Hình dung: Xếp hàng mua trà sữa - ai đến trước được phục vụ trước!

Queue<String> printQueue = new LinkedList<>();
printQueue.offer("CV_cua_ban.pdf");      // File 1 vào hàng đợi
printQueue.offer("Bai_tap_lon.docx");    // File 2 vào hàng đợi
printQueue.offer("Meme_vui.jpg");        // File 3 vào hàng đợi

String printing = printQueue.poll();      // In "CV_cua_ban.pdf" trước

Operations:

• enqueue(item): Thêm vào cuối - O(1)
• dequeue(): Lấy từ đầu - O(1)
• front(): Xem đầu hàng - O(1)

Deque - con tàu hai đầu

Hình dung: Toa tàu có thể gắn thêm hoặc tháo toa ở cả đầu và cuối!

Deque<String> chatHistory = new ArrayDeque<>();
chatHistory.addFirst("Message mới nhất");    // Thêm đầu
chatHistory.addLast("Message cũ");           // Thêm cuối
chatHistory.removeFirst();                   // Xóa tin mới nhất
chatHistory.removeLast();                    // Xóa tin cũ nhất

Priority Queue - phòng cấp cứu bệnh viện

Hình dung: Ở phòng cấp cứu, bệnh nhân nguy kịch được ưu tiên dù đến sau!

PriorityQueue<Task> aiTasks = new PriorityQueue<>();
aiTasks.add(new Task("Tấn công player", 100));    // Ưu tiên cao
aiTasks.add(new Task("Đi tuần tra", 10));         // Ưu tiên thấp
aiTasks.add(new Task("Nhặt item", 5));            // Ưu tiên rất thấp

Task urgent = aiTasks.poll(); // Lấy "Tấn công player" trước!

Time & Space Complexity - bảng tổng hợp không thể thiếu

*Amortized - trung bình là O(1), nhưng đôi khi phải resize array sẽ tốn O(n)

Game Development - từ Undo/Redo đến A* Pathfinding

Stack trong game - không chỉ là Ctrl+Z

Unity's Undo System dùng Stack kết hợp Command Pattern:

public class UndoManager {
    private Stack<ICommand> undoStack = new Stack<ICommand>();
    
    public void ExecuteCommand(ICommand cmd) {
        cmd.Execute();
        undoStack.Push(cmd);  // Lưu lại để undo
    }
    
    public void Undo() {
        if (undoStack.Count > 0) {
            undoStack.Pop().Undo();
        }
    }
}

Maze Generation - thuật toán recursive backtracking cũng dùng Stack:

1. Đi random đến khi bí đường
2. Pop từ stack để quay lại
3. Thử hướng khác
4. Lặp lại đến khi tạo xong mê cung

Turn-based Combat trong XCOM dùng Stack để quản lý combat state - mỗi action được push vào stack, cho phép rollback khi cần!

Queue - xương sống của game engine

Fighting Game Input Buffer - bí mật của combo mượt mà:

• Street Fighter 6: buffer 5 frames (1/12 giây)
• Tekken 8: buffer 8 frames cho phép combo phức tạp hơn
• Input được queue up và xử lý theo thứ tự

public class InputBuffer {
    private Queue<Input> buffer = new Queue<Input>();
    private const int BUFFER_FRAMES = 5;
    
    public void BufferInput(Input input) {
        buffer.Enqueue(input);
        if (buffer.Count > BUFFER_FRAMES) {
            buffer.Dequeue(); // Xóa input cũ
        }
    }
}

Event System trong Unity/Unreal - mọi thứ từ click chuột đến explosion đều qua event queue!

Deque cho Sliding Window

Procedural World Generation kiểu Minecraft:

public class WorldStreamer {
    private Deque<Chunk> loadedChunks = new Deque<Chunk>();
    
    void UpdateWorld(Vector3 playerPos) {
        // Xóa chunk phía sau player
        while (IsTooFar(loadedChunks.Front(), playerPos)) {
            UnloadChunk(loadedChunks.RemoveFront());
        }
        // Thêm chunk phía trước
        if (NeedNewChunk(playerPos)) {
            loadedChunks.AddBack(GenerateChunk(playerPos));
        }
    }
}

Priority Queue - bộ não của Enemy AI

A Pathfinding* - thuật toán tìm đường kinh điển:

PriorityQueue<Node> openSet;
openSet.push(startNode, 0);

while (!openSet.empty()) {
    Node current = openSet.pop();  // Lấy node có f-score thấp nhất
    
    if (current == goal) return reconstructPath();
    
    for (Node neighbor : current.neighbors) {
        float newCost = costSoFar[current] + distance(current, neighbor);
        float priority = newCost + heuristic(neighbor, goal);
        openSet.push(neighbor, priority);
    }
}

Enemy Task Scheduling:

• Priority 200: Tấn công player
• Priority 100: Đuổi theo player
• Priority 50: Tuần tra
• Priority 10: Idle animation

Web Development - scale lên hàng triệu users

Stack powers của browser và React

Browser History dùng 2 stacks:

class BrowserHistory {
    constructor() {
        this.backStack = [];
        this.forwardStack = [];
    }
    
    visit(url) {
        this.backStack.push(url);
        this.forwardStack = []; // Clear forward history
    }
    
    back() {
        if (this.backStack.length > 1) {
            this.forwardStack.push(this.backStack.pop());
            return this.backStack[this.backStack.length - 1];
        }
    }
}

React Fiber - cách mạng hóa rendering:

• Thay vì dùng call stack (blocking), React 16+ dùng "fiber" - linked list có thể pause/resume
• Cho phép chia nhỏ rendering work, không block main thread
• Kết quả: UI mượt mà hơn, especially với animations

Queue - xương sống của backend

Node.js Event Loop - multiple queues với priority khác nhau:

1. Timer queue: setTimeout, setInterval callbacks
2. I/O queue: File, network operations
3. Check queue: setImmediate callbacks
4. Close queue: Socket close events

Message Queue Systems:

• Netflix dùng Apache Kafka: Xử lý hàng triệu events/giây
• AWS SQS: Queue service của Amazon, handle mọi scale
• RabbitMQ: NASA và Mercedes-Benz tin dùng!

Deque trong caching strategies

Facebook's LRU Cache với deque:

• Photo CDN dùng S4LRU (Segmented LRU)
• Tăng cache hit rate từ 33% lên 46.9%!
• Scale đến 28TB+ memory, 800+ servers

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map();
        this.order = new Deque(); // Track access order
    }
    
    get(key) {
        if (this.cache.has(key)) {
            this.order.remove(key);
            this.order.addFront(key); // Move to front (most recent)
            return this.cache.get(key);
        }
    }
}

Priority Queue tại Netflix scale

Netflix's Timestone System - priority queue khổng lồ:

• Dùng Redis sorted sets + Kafka + Flink
• Xử lý video encoding jobs với priority
• "Exclusive Queues" ngăn parallel processing conflicts
• Support cả Cosmos (media platform) và Conductor (workflow engine)

Implementation Variants - trade-offs quan trọng

Array vs Linked List

Array-based (như ArrayList):

• ✅ Cache locality tốt - CPU prefetch hiệu quả
• ✅ Memory overhead thấp - không cần pointer
• ❌ Resize tốn O(n)
• ❌ Memory waste khi không full

Linked List:

• ✅ Dynamic size - grow/shrink thoải mái
• ✅ Không bao giờ resize
• ❌ Cache miss nhiều - nodes nằm rải rác trong memory
• ❌ Memory overhead cao - mỗi node cần pointer

Circular Buffer - tối ưu cho Queue

class CircularQueue {
    private int[] buffer;
    private int head = 0, tail = 0;
    
    void enqueue(int item) {
        buffer[tail] = item;
        tail = (tail + 1) % buffer.length; // Wrap around!
    }
    
    int dequeue() {
        int item = buffer[head];
        head = (head + 1) % buffer.length;
        return item;
    }
}

Pro tip: Dùng size là lũy thừa của 2 (64, 128, 256...) để thay % bằng &:

tail = (tail + 1) & (size - 1); // Nhanh hơn modulo!

Fun Facts ít ai biết

Etymology thú vị

• Stack ban đầu được gọi là "Keller" (hầm) trong tiếng Đức - hình ảnh chất đồ xuống hầm!
• Queue theory ra đời từ bài toán... xếp hàng điện thoại năm 1909
• "Deque" đọc là "deck" như bộ bài, không phải "dee-queue"!

Cultural differences ảnh hưởng design

• Văn hóa xếp hàng của người Anh vs "free-for-all" của Mỹ
• Nhật Bản có "women-only cars" trên tàu - priority queue in real life!
• Một số nước ưu tiên người già/trẻ em - cần modified queue algorithms

Performance records điên rồ

• Lock-free ring buffers đạt hàng triệu operations/giây
• Facebook's Memcached: 800+ servers, 28TB+ RAM
• Netflix Kafka xử lý triệu messages/giây

Security vulnerabilities

• Stack overflow attacks - hackers lợi dụng predictable stack behavior
• Queue flooding - DDoS attacks làm tràn processing queues
• Morris Worm 1988 - một trong những malware đầu tiên dùng buffer overflow

Decision Matrix - chọn cấu trúc nào?

Quick Decision Guide

Khi nào KHÔNG dùng

Đừng dùng Stack khi:

• Cần xử lý công bằng theo thứ tự (dùng Queue)
• Cần access random elements (dùng Array/List)

Đừng dùng Queue khi:

• Cần ưu tiên (dùng Priority Queue)
• Cần xóa ở giữa (dùng List)

Đừng dùng Priority Queue khi:

• Chỉ cần min/max (dùng simple variable)
• Data ít và đã sorted (dùng Array)

Common Mistakes cần tránh

Memory leak trong Java Stack:

// SAI - reference còn giữ object!
public T pop() {
    return array[--size];
}

// ĐÚNG - clear reference
public T pop() {
    T item = array[--size];
    array[size] = null;  // Prevent leak!
    return item;
}

Race condition với multi-threading:

// SAI - không atomic!
if (!queue.isEmpty()) {
    item = queue.poll(); // Thread khác có thể poll trước!
}

// ĐÚNG - dùng concurrent collections
ConcurrentLinkedQueue<Item> queue = new ConcurrentLinkedQueue<>();
Item item = queue.poll(); // Thread-safe

Optimization Techniques nâng cao

Cache-Friendly Implementation

Modern CPU có cache line ~64 bytes. Array-based structures tận dụng tốt spatial locality:

// Good: Contiguous memory
int stack[1000];  // All elements in sequence

// Bad: Scattered memory  
struct Node {
    int data;
    Node* next;  // Could be anywhere in memory!
};

Benchmark thực tế:

• Small data (<1KB): không khác biệt
• Medium (1KB-1MB): Array nhanh 2-5x
• Large (>1MB): Array nhanh đến 10x!

Lock-Free cho Concurrent Systems

// Lock-free stack với CAS operation
public class LockFreeStack<T> {
    private AtomicReference<Node<T>> head = new AtomicReference<>();
    
    public void push(T item) {
        Node<T> newHead = new Node<>(item);
        while (true) {
            Node<T> oldHead = head.get();
            newHead.next = oldHead;
            if (head.compareAndSet(oldHead, newHead)) {
                break;  // Success!
            }
            // Retry if another thread changed head
        }
    }
}

Kết luận - master của data structures

Bốn cấu trúc dữ liệu này không chỉ là lý thuyết khô khan trong sách vở. Chúng là xương sống của mọi hệ thống software hiện đại:

• Stack cho phép browser của bạn "Back", React render smooth, và compiler hiểu code của bạn
• Queue giúp Node.js xử lý hàng triệu requests, game fighting chơi mượt với input buffer
• Deque power-up Facebook's cache system, Minecraft's infinite worlds
• Priority Queue là bộ não của enemy AI, Netflix's video processing, và emergency room triage

Key Takeaways cho junior developers:

1. Hiểu rõ trade-offs: Array nhanh nhưng fixed size, Linked List flexible nhưng cache miss
2. Pattern recognition: Thấy LIFO → Stack, thấy FIFO → Queue, cần priority → Priority Queue
3. Real-world first: Đừng chỉ học API, hiểu tại sao Instagram dùng Redis Queue, Unity dùng Stack cho undo
4. Performance matters: Cache locality có thể boost performance 10x!
5. Don't reinvent: Dùng built-in implementations trước khi tự viết

Nhớ rằng: Google, Facebook, Netflix - tất cả đều dùng những cấu trúc "cơ bản" này để scale lên hàng tỷ users. Master chúng, và bạn đã nắm được một phần quan trọng của computer science!

Happy coding! 🚀