Cấu trúc dữ liệu: Stack & Queue

🎯 Stack vs Queue: Hai thái cực đối lập

Trong lập trình, cách chúng ta "nhét vào" và "lấy ra" dữ liệu sẽ quyết định cấu trúc dữ liệu cần dùng.

1. Stack (Ngăn xếp) - LIFO (Last In First Out)

Nguyên lý: "Vào sau Ra trước". Hãy tưởng tượng chồng đĩa rửa bát. Cái đĩa bạn đặt lên cuối cùng sẽ là cái bạn lấy ra rửa đầu tiên.

• Push: Đẩy một phần tử lên đỉnh Stack.
• Pop: Lấy phần tử ở đỉnh ra.
• Peek/Top: Ngó xem đỉnh là cái gì (không lấy ra).

2. Queue (Hàng đợi) - FIFO (First In First Out)

Nguyên lý: "Vào trước Ra trước". Giống xếp hàng mua vé xem phim. Ai đến trước được phục vụ trước.

• Enqueue: Xếp vào cuối hàng.
• Dequeue: Lấy người đầu hàng ra phục vụ.

3. Message Queue (Kafka/RabbitMQ) - Queue trong hệ thống lớn

Trong các hệ thống như Shopee hay Grab, khi bạn đặt đơn, request không được xử lý ngay lập tức (vì server có thể đang bận). Nó được đẩy vào một cái Queue khổng lồ (Message Queue).

• Producer (Người gửi): App của bạn gửi đơn hàng vào Queue.
• Legacy Queue: Hàng đợi vẫn giữ thứ tự (FIFO) để đảm bảo "Ai đặt trước có hàng trước".
• Consumer (Worker): Server rảnh tay sẽ lấy đơn từ Queue ra xử lý dần.

=> Giúp hệ thống không bị sập khi có quá nhiều người dùng cùng lúc (Anti-Peak).

4. Bài tập thực hành: Reverse Polish Notation (RPN)

Một ứng dụng kinh điển của Stack trong máy tính bỏ túi.

Biểu thức: 3 4 + 2 * (Tức là (3+4)*2).

• Đọc 3: Push [3].
• Đọc 4: Push [3, 4].
• Đọc +: Pop 4, Pop 3. Tính 3+4=7. Push [7].
• Đọc 2: Push [7, 2].
• Đọc *: Pop 2, Pop 7. Tính 7*2=14. Push [14].
• Kết quả: 14.