Trước khi so sánh Stack và Queue, nên hiểu khái niệm kiểu dữ liệu: Kiểu dữ liệu là loại dữ liệu mà biến được tạo ra để lưu trữ. Có hai loại chính: Nguyên thủy (Primitive) - định nghĩa sẵn bởi ngôn ngữ, và Phi nguyên thủy (Non-primitive) - do lập trình viên tạo ra.
Stack và Queue đều là cấu trúc dữ liệu phi nguyên thủy, nhưng dựa trên cài đặt nội bộ có những khác biệt chính sau:
| STT | Tiêu chí | Stack (Ngăn xếp) | Queue (Hàng đợi) |
|---|---|---|---|
| 1 | Cài đặt nội bộ | Phần tử chèn cuối cùng sẽ được lấy ra đầu tiên. Stack tuân theo LIFO (Last In First Out). | Phần tử chèn đầu tiên sẽ được lấy ra đầu tiên. Queue tuân theo FIFO (First In First Out). |
| 2 | Phần tử mục tiêu | Thao tác chỉ diễn ra ở một đầu danh sách gọi là đỉnh (top). | Chèn ở cuối (rear), xóa ở đầu (front) của danh sách. |
| 3 | Nhãn và Cờ | Chỉ duy trì một cờ (con trỏ top) luôn trỏ đến phần tử cuối cùng. | Duy trì hai cờ: front trỏ phần tử đầu tiên còn lại, rear trỏ phần tử chèn cuối cùng. |
| 4 | Thao tác | Push (đẩy) và Pop (lấy). | Enqueue (nhập hàng) và Dequeue (xuất hàng). |
| 5 | Biến thể | Không có biến thể, không mở rộng thêm. | Có biến thể: hàng đợi vòng (circular), hàng đợi ưu tiên (priority queue), hàng đợi hai đầu (deque). |
| 6 | Độ phức tạp | Stack đơn giản hơn Queue. | Queue phức tạp hơn Stack. |