Ngăn xếp và hàng đợi là hai kiểu cấu trúc dữ liệu động được sử dụng khá phổ biến trong lập trình. Hai kiểu cấu trúc này đều được xây dựng dựa trên danh sách liên kết đơn cho nên khá dễ để cài đặt. Hãy cùng tìm hiểu xem stack và queue là gì và phân biệt hai cấu trúc dữ liêu này trong bài viết dưới đây bạn nhé!
Khái niệm ngăn xếp
Ngăn xếp hay Stack là một dạng danh sách liên kết hoạt động theo cơ chế LIFO (Last In, First Out), nghĩa là các phần tử được thêm vào sau cùng thì sẽ là phần tử được lấy ra đầu tiên.
Một con trỏ đặc biệt gọi là top được sử dụng để theo dõi phần tử được thêm vào gần nhất trong Stack.
Các thao tác cơ bản trên ngăn xếp như sau:
- IsEmpty: kiểm tra xem ngăn xếp có rỗng hay không
- Push: thêm phần tử vào trên cùng ngăn xếp
- Pop: lấy phần tử nằm trên cùng ra khỏi ngăn xếp và trả về giá trị của phần tử đó (nếu ngăn xếp không rỗng)
- Top: trả về giá trị của phần tử nằm trên cùng của ngăn xếp (nếu ngăn xếp không rỗng)
Khái niệm hàng đợi
Hàng đợi hay queue là một cấu trúc dữ liệu động hoạt động theo cơ chế FIFO (First In, First Out), nghĩa là phần tử được thêm vào đầu tiên sẽ là phần tử được lấy ra đầu tiên.
Queue sử dụng hai con trỏ: con trỏ front chỉ đến phần tử đầu tiên được chèn vào, trong khi con trỏ rear chỉ đến phần tử được chèn vào cuối cùng.
Các thao tác cơ bản trên hàng đợi:
- IsEmpty: kiểm tra hàng đợi có rỗng hay không
- EnQueue: thêm một phần tử vào cuối hàng đợi
- DeQueue: lấy phần tử đầu tiên ra khỏi hàng đợi (nếu hàng đợi không rỗng)
- Front: trả về giá trị của phần tử ở đầu hàng đợi (nếu hàng đợi không rỗng)
Điểm chung của Ngăn xếp và Hàng đợi
Stack và Queue có nhiều điểm chung dù chúng hoạt động theo các nguyên tắc khác nhau. Đầu tiên, cả Stack và Queue đều là cấu trúc dữ liệu tuyến tính, nghĩa là các phần tử trong chúng được lưu trữ và truy cập theo một thứ tự xác định. Cả hai đều có thể lưu trữ các phần tử của cùng một kiểu dữ liệu, chẳng hạn như số nguyên, chuỗi, hoặc các đối tượng.
Cả Stack và Queue đều hỗ trợ các thao tác cơ bản như thêm (insert) và xóa (delete) phần tử. Trong Stack, thao tác thêm và xóa diễn ra ở cùng một đầu (đỉnh – top), trong khi Queue sử dụng hai đầu (front và rear) để thực hiện các thao tác này. Tuy nhiên, về cơ bản, cả hai đều dựa vào việc sử dụng con trỏ để theo dõi các phần tử trong cấu trúc dữ liệu.
Cả Stack và Queue đều không cho phép lặp lại phần tử đã được truy cập, vì chúng hoạt động theo thứ tự và yêu cầu phần tử được xử lý theo nguyên tắc FIFO (First In, First Out) trong Queue, hoặc LIFO (Last In, First Out) trong Stack.
Trong C++, cả hai cấu trúc dữ liệu này đều có thể được triển khai dễ dàng thông qua Thư viện Mẫu Chuẩn (STL), với các thao tác tương tự như push(), pop(), và empty(). Cả Stack và Queue đều đóng vai trò quan trọng trong nhiều bài toán về quản lý dữ liệu, thuật toán, và cấu trúc điều khiển, giúp lập trình viên xử lý các vấn đề phức tạp một cách hiệu quả.
Bảng so sánh Stack và Queue
Dưới đây là bảng so sánh sự khác nhau giữa Stack và Queue:
| Tham số | Cấu trúc dữ liệu Stack | Cấu trúc dữ liệu Queue |
|---|---|---|
| Cơ bản | Là cấu trúc dữ liệu tuyến tính. Phần tử được thêm vào và xóa khỏi cùng một đầu. | Là cấu trúc dữ liệu tuyến tính. Phần tử được thêm vào và xóa khỏi hai đầu khác nhau. |
| Nguyên tắc hoạt động | Tuân theo nguyên tắc LIFO (Last In, First Out). Phần tử được chèn cuối cùng sẽ bị xóa trước tiên. | Tuân theo nguyên tắc FIFO (First In, First Out). Phần tử được thêm vào đầu tiên sẽ bị xóa trước tiên. |
| Con trỏ | Có một con trỏ duy nhất – top. Con trỏ này chỉ đến phần tử trên cùng của stack. | Có hai con trỏ – front và rear. rear chỉ đến phần tử được chèn cuối cùng, còn front chỉ đến phần tử được thêm đầu tiên. |
| Các thao tác | Stack sử dụng các thao tác push và pop. pop xóa phần tử, push chèn phần tử. | Queue sử dụng các thao tác enqueue và dequeue. dequeue xóa phần tử, enqueue chèn phần tử. |
| Cấu trúc | Việc thêm và xóa phần tử chỉ diễn ra ở một đầu, gọi là top. | Sử dụng hai đầu – front và rear. rear dùng để chèn phần tử, front dùng để xóa phần tử. |
| Kiểm tra điều kiện đầy | Khi top == max-1, stack đã đầy. | Khi rear == max-1, queue đã đầy. |
| Kiểm tra điều kiện rỗng | Khi top == -1, stack rỗng. | Khi front == rear + 1 hoặc front == -1, queue rỗng. |
| Biến thể | Không có các loại biến thể nào của Stack. | Queue có ba loại biến thể – circular queue, priority queue, và double-ended queue. |
| Trực quan | Stack được hình dung như một tập hợp các phần tử theo chiều dọc. | Queue được hình dung như một tập hợp các phần tử theo chiều ngang. |
| Triển khai | Triển khai đơn giản hơn so với Queue. | Triển khai phức tạp hơn so với Stack. |
Tham khảo bài viết gốc: https://byjus.com/gate/difference-stack-and-queue-data-structures/
Vậy là trong bài này, mình đã giới thiệu cho các bạn thêm hai cấu trúc dữ liệu phổ biến đó chính là ngăn xếp (stack) và hàng đợi (queue) và bảng so sánh tóm tắt sự khác nhau của hai cấu trúc dữ liệu này. Nếu các bạn thấy bài viết này hay, đừng quên chia sẻ cho bạn bè cùng biết, cảm ơn các bạn đã theo dõi bài viết!