QUEUE LÀ GÌ

1. Hàng đợi (queue) là gì?

Hàng đợi (queue) là một cấu trúc dữ liệu hoạt động theo cơ chế FIFO (First In First Out), tạm dịch là “vào trước ra trước”. Có nghĩa là phần tử nào được thêm hàng đợi trước thì sẽ được lấy ra trước.

Bạn đang xem: Queue là gì

Có thể hình dung hàng đợi như một đoàn người xếp hàng mua vé. Người nào xếp hàng trước sẽ được mua vé trước và ra khỏi hàng để nhường vị trí cho người xếp hàng ngay phía sau.Có thể xem hàng đợi (queue) là một kiểu danh sách có 2 phép toán đặc trưng là:Bổ sung một phần tử vào cuối danh sách (rear)Loại bỏ một phần tử ở đầu danh sách (front)Một số thao tác thông dụng trên queue như:enqueue(): thêm một phần tử vào queue.dequeue(): loại bỏ một phần tử ra khỏi queue.isFull(): kiểm tra queue có đầy chưa. Số lượng phần tử trong queue do người dùng quy định. Tùy trường hợp chúng ta mới cần sử dụng hàm isFull().

Xem thêm: Game Chàng Trai Lửa Và Cô Gái Nước 5 Trong 2021, Download Game Chú Bé Lửa Và Cô Gái Nước

isEmpty(): kiểm tra queue có rỗng hay không.Trong lập trình, có 2 cách thường dùng để xây dựng queue là sử dụng mảng (array) và danh sách liên kết (linked list).

2. Xây dựng hàng đợi bằng mảng

Khi xây dựng queue bằng mảng thì chúng ta lưu ý một số vấn đề sau:Cần có hai chỉ số front và rear để lưu chỉ số phần tử đầu và chỉ số phần tử cuối trong queue. Khởi tạo queue rỗng thì front = 0 và rear = -1.Để thêm một phần tử vào queue, ta tăng rear lên 1 và đưa giá trị đó vào phần tử thứ rear trong mảng.Để loại bỏ một phần tử khỏi queue, ta tăng front lên 1.Chỉ những phần tử của mảng từ vị trí front tới rear mới được xem là các phần tử trong queue.Khi front > rear thì queue đang rỗng.Khi rear tăng lên hết khoảng chỉ số của mảng thì mảng đã đầy, không thể thêm phần tử vào nữa.#include using namespace std;#define max 10000int Queue;int front, rear;void QueueInit(){front = 0;rear = -1;}void enqueue(int V){if(rear >= max-1){cout rear){cout rear){coutKết quảElements in Queue:5 21 10 99 101Dequeue fromt Queue:5 21Print Queue after dequeueElements in Queue:10 99 101Nhận xét:Khi sử dụng mảng để cài đặt queue, chỉ số rear và front chỉ tăng lên chứ không giảm đi, kể cả khi lấy các phần tử ra khỏi hàng đợi. Chỉ có các phần tử từ vị trí front tới rear là thuộc queue. Các phần tử từ vị trí 0 tới front-1 bị lãng phí.Hơn nữa, nếu chỉ số rear tăng lên vượt quá số lượng phần tử cho phép trong mảng thì queue cũng bị tràn, không thể thêm phần tử vào queue nữa.Chúng ta có thể sử dụng danh sách liên kết để cài đặt queue nhằm khắc phục các khuyết điểm trên.

Xem thêm: Game Tín Đồ Shopping Lấy Chồng, Tín Đồ Shopping Lấy Chồng

3. Xây dựng hàng đợi bằng danh sách liên kết

Khi sử dụng danh sách liên kết đơn để xây dựng queue, nếu muốn thêm một phần tử vào queue thì ta thêm vào cuối danh sách. Nếu muốn lấy một phần tử ra khỏi queue thì ta hủy phần tử đầu danh sách.
#include using namespace std;struct node{int data;node *next;};node * front;node *rear;void QueueInit(){front = NULL;rear = NULL;}void enqueue(int V){node *p;p = new node;p->data = V;p->next = NULL;if (front!=NULL){rear->next = p;}else{front = p;}rear = p;}int dequeue(){if (front == NULL){coutdata;node *p = front->next;delete front;front = p;if(front == NULL){rear = NULL;}return res;}}//print Queuevoid printQueue(){node *p;p = front;coutdatanext;}}int main(){//init QueueQueueInit();//enqueue to Queueenqueue(5);enqueue(21);enqueue(10);enqueue(99);enqueue(101);//print QueueprintQueue();//dequeue from QueuecoutKết quảElements in Queue:5 21 10 99 101Dequeue fromt Queue:5 21Print Queue after dequeueElements in Queue:10 99 101
Bài trước và bài sau trong môn học>" data-wpel-link="internal">Cấu trúc dữ liệu dạng cây là gì? Đặc điểm của cây nhị phân (Binary Tree) >>