Series Cấu trúc dữ liệu | Queue - Hàng đợi

Mục lục

• [QUEUE]
• [Priority_QUEUE]

---

Giới thiệu QUEUE

Chắc hẳn các bạn đã từng xếp hàng rồi chứ nhỉ? Khi mua đồ, khi mua vé xem phim, hay xếp hàng ra về. Mọi lần xếp hàng sẽ bắt đầu từ người đứng đầu tiên rồi tới các bạn phía sau, và tất nhiên người nào đến sớm hơn thì sẽ được ra về sớm hơn. Đó cũng chính là minh họa cho Cấu trúc QUEUE mà mình muốn hướng tới ngày hôm nay.

QUEUE-tạm dịch là hàng đợi, là cấu trúc song hành với STACK nhưng hoạt động theo chuẩn LILO(Last In Last Out) hoặc FIFO(Fist In First Out). Hiểu một cách đơn giản là Vào Trước Ra Trước.
Trong QUEUE, có hai vị trí quan trọng là vị trí đầu danh sách (front), nơi phần tử được lấy ra, và vị trí cuối danh sách (back), nơi phần tử cuối cùng được thêm vào

Code

Việc thêm phần tử vào cuối queue gọi là enqueue.
Việc xóa phần tử đầu gọi là dequeue

Khai báo

#include<queue>
//Ví dụ khai báo queue kiểu int  
queue <int> s;  
s.size() : trả về kích thước hiện tại của queue.  
s.empty() : true nếu queue rỗng, và ngược lại  
s.push(x) : đẩy x vào cuối queue.  
s.pop(): loại bỏ phần tử (ở đầu).  
s.front() : trả về phần tử ở đầu  
s.back(): trả về phần tử ở cuối

Ứng dụng

• khử đệ quy
• tổ chức lưu vết các quá trình tìm kiếm theo chiều rộng (BFS) và quay lui, vét cạn
• tổ chức quản lý và phân phốitiến trình trong các hệ điều hành, tổ chức bộ đệm bàn phím.

Priority_QUEUE(Hàng đợi ưu tiên)

Khái niệm

Nhắc tới khái niệm “Ưu tiên” chắc hẳn chúng ta đã biết tính chất của loại hàng đợi này. Đây chính là ví dụ của sự bất công trong xã hội, khi chỉ vì một yếu tố nào đó mà người tới trước chưa chắc đã nhận được thứ mình muốn đầu tiên, hay nói thẳng ra thì người nào có điều kiện tốt nhất thì sẽ được ưu tiên hơn.

Ví dụ: Các thành phần trong hàng đợi được ưu tiên theo độ lớn giảm dần, thì giữa 1 và 5, dù 1 có vào trước nhưng khi đến 5 vào vẫn phải nhường chỗ cho nó.

Code

#include<queue>
priority_queue<int, vector<int>, chuẩn ưu tiên(nếu bỏ trống mặc định vào theo thứ tự giảm dần)> q;
q.push(1);// độ phức tạp log(n)
q.push(2);
q.push(3);
while(!q.empty()) {
 int x=q.front();
 cout<<x<<' ';
 q.pop();
}
// kq: 3 2 1

Ứng dụng

• Có nhiều ứng dụng nhưng có thể dùng nó để sắp xếp cũng khá tốt.

Để hiểu rõ cách hoạt động của priority_queue các bạn nên tìm hiểu thêm cấu trúc Heap(google, có thể tôi sẽ thêm vào các bài sau)

Luyện tập:
https://www.spoj.com/PTIT/problems/P175SUME/
Luyện tập thêm tại SPOJ/PTIT