Stack & Queue là hai cấu trúc dữ liệu cơ bản và phổ biến trong con đường của một lập trình viên, hẳn rằng những lập trình viên có kinh nghiệm đều đã nghe, đã biết đến cấu trúc dữ liệu này, vậy cuối cùng thì, Stack & Queue là gì và nó có tác dụng thế nào?

QUEUE - HÀNG ĐỢI

Để bắt đầu nhẹ nhàng, chúng ta bắt đầu với Queue trước. Trước tiên thì Queue là một cấu trúc dữ liệu có dạng FIFO (First In Frist Out) tức là vào trước thì ra trước. Một ví dụ dễ thấy trong cuộc sống hàng ngày là việc xếp hàng, ví dụ khi bạn đứng xếp hàng để gửi xe trong một trung tâm thương mại, xe đến trước sẽ được nhận vé và vào trước rồi sẽ lần lượt đến sau.

Một ví dụ trong việc lập trình, trong trò chơi Liên Minh Huyền Thoại đình đám thì việc khi bạn tìm trận đấu, lúc này bạn sẽ được thêm vào một Queue (bỏ qua các vấn đề về sự ưu tiên như cấp độ xếp hạng, vị trí trong game,...) lúc này hệ thống sẽ ghép lần lượt 10 người chơi đầu tiên bắt đầu tìm trận sớm nhất đưa ra khỏi Queue và bắt đầu trò chơi, cứ thế liên tục đến khi Queue rỗng.

Có thể bạn sẽ thắc mắc rằng, việc này cũng có thể xử lý với mảng (array) cứ xóa 10 người ở đầu là được. Nhưng giải pháp dùng mảng sẽ đem đến một vấn đề về hiệu suất rất nặng.

Giả sử, trong mảng đang lưu một nghìn người chơi đang đợi để tìm trận, khi đó mỗi khi lấy một người đầu tiên ra khỏi mảng thì mình cần phải đưa lần lượt các người chơi khác lùi xuống một vị trí trong mảng rồi xóa phần tử cuối cùng, để không có phần tử rỗng ở trong mảng, lúc này ta sẽ tốn O(n) độ phức tạp để xử lý việc này còn với Queue độ phức tạp sẽ là O(1), tối ưu hơn rất rất nhiều lần, vì Queue chỉ cần cắt một node đầu tiên ra khỏi nó.

---

STACK - NGĂN XẾP

Stack là một cấu trúc dữ liệu có dạng LIFO (Last In First Out) vào sau thì ra trước. Để dễ hình dung, mình liên tưởng đến ống đựng cầu lông, quả cầu được để vào ống sau cùng sẽ được lấy ra đầu tiên, đây chính là cơ chế của cấu trúc dữ liệu Stack.

Stack là một cấu trúc dữ liệu phổ biến trong ngành lập trình, một trong những ứng dụng đặc trưng của Stack là chức năng Undo - Redo.

Bài toán

• Ta có một chuỗi "abc" thực hiện thêm hoặc xóa kí tự trong chuỗi.

1. Khởi tạo undoStack và redoStack
2. Thêm kí tự "d" vào chuỗi.
   1. Thêm chuỗi hiện tại vào undoStack ("abc").
   2. Thêm kí tự "d" vào chuỗi -> "abcd".
3. Sử dụng chức năng Undo.
   1. Lấy phần tử ra khỏi undoStack (.pop() -> "abc").
   2. Thêm chuỗi hiện tại vào redoStack (abcd).
   3. Gán phần tử đã lấy được từ undoStack ("abc") vào chuỗi hiện tại.
4. Sử dụng chức năng Redo.
   1. Lấy phần tử ra khỏi redoStack (.pop() -> "abcd").
   2. Thêm chuỗi hiện tại vào undoStack (abc).
   3. Gán phần tử đã lấy được từ redoStack ("abcd") vào chuỗi hiện tại.

---

KẾT LUẬN

Stack & Queue là hai cấu trúc dữ liệu phổ biến trong thế giới lập trình, việc biết thêm các cấu trúc dữ liệu sẽ giúp cho bản thân mỗi người thêm những giải pháp khi giải quyết các vấn đề gặp phải, với Stack & Queue mình có thể tối ưu được nhiều hơn những bài toán xử lý với mảng, và mảng là một trong những bài toán phổ biến trong lập trình, bất cứ đâu cũng có thể thấy.

---

✏️ System Design VN: https://fb.com/groups/systemdesign.vn
📚 Đọc thêm tài liệu khác: https://roninhub.com/tai-lieu
🎬 Youtube: https://youtube.com/@ronin-engineer