Queue là gì

     

1. Hàng chờ (queue) là gì?

Hàng đợi (queue) là một kết cấu dữ liệu chuyển động theo hiệ tượng FIFO (First In First Out), tạm bợ dịch là “vào trước ra trước”. Bao gồm nghĩa là thành phần nào nhận thêm hàng ngóng trước thì vẫn được kéo ra trước.

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


*

Có thể tưởng tượng hàng đợi như một đoàn tín đồ xếp hàng thiết lập vé. Fan nào xếp sản phẩm trước sẽ tiến hành mua vé trước và ra khỏi hàng nhằm nhường vị trí cho những người xếp hàng ngay phía sau.Có thể coi hàng hóng (queue) là 1 trong kiểu danh sách có 2 phép toán đặc thù là:Bổ sung một trong những phần tử vào cuối danh sách (rear)Loại bỏ một trong những phần tử làm việc đầu danh sách (front)Một số thao tác thông dụng trên queue như:enqueue(): thêm một trong những phần tử vào queue.dequeue(): nhiều loại bỏ 1 phần tử ra khỏi queue.isFull(): kiểm soát queue gồm đầy chưa. Số lượng phần tử trong queue do người tiêu dùng quy định. Tùy ngôi trường hợp bọn họ mới cần áp dụng hàm isFull().

Xem thêm: Hiện Tượng Nào Sau Đây Được Gọi Là Ứng Động Sinh Học, Trắc Nghiệm Sinh Học 11 Bài 24: Ứng Động Sinh Học

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

2. Tạo hàng đợi bởi mảng

Khi xây dừng queue bằng mảng thì chúng ta lưu ý một vài vấn đề sau:Cần tất cả hai chỉ số front với rear để lưu chỉ số phần tử đầu còn chỉ số phần tử cuối trong queue. Khởi sản xuất queue rỗng thì front = 0 cùng rear = -1.Để thêm một phần tử vào queue, ta tăng rear lên 1 và gửi giá trị kia vào bộ phận thứ rear vào mảng.Để một số loại bỏ 1 phần tử ngoài queue, ta tăng front lên 1.Chỉ những thành phần của mảng từ địa chỉ front cho tới rear new được xem như là các bộ phận trong queue.Khi front > rear thì queue sẽ rỗng.Khi rear tăng thêm hết khoảng chừng chỉ số của mảng thì mảng sẽ đầy, quan trọng thêm thành phần 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 thực hiện mảng để setup queue, chỉ số rear cùng front chỉ tăng lên chứ không sút đi, kể cả khi mang các thành phần ra khỏi hàng đợi. Chỉ tất cả các phần tử từ địa điểm front tới rear là nằm trong queue. Các thành phần từ địa chỉ 0 cho tới front-1 bị lãng phí.Hơn nữa, nếu như chỉ số rear tạo thêm vượt quá số lượng bộ phận cho phép vào mảng thì queue cũng bị tràn, quan trọng thêm bộ phận vào queue nữa.Chúng ta có thể sử dụng danh sách liên kết để setup queue nhằm mục tiêu khắc phục những khuyết điểm trên.

Xem thêm: Từ Điển Anh Việt " Perinatal Là Gì, Từ Điển Anh

3. Xây dừng hàng đợi bằng list liên kết

Khi áp dụng danh sách links đơn để sản xuất queue, nếu còn muốn thêm 1 phần tử vào queue thì ta thêm vào thời gian cuối danh sách. Nếu muốn lấy một trong những phần tử thoát ra khỏi queue thì ta bỏ phần tử đầu danh sách.
#include using namespace std;struct nodeint 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;elsefront = 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 bác 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) >>