Hàng đợi ưu tiên và hàng đợi trong C ++

Như chúng ta biết rằng cấu trúc dữ liệu hàng đợi là cấu trúc dữ liệu First in First Out. Hàng đợi cũng có một số biến thể. Đây là hàng đợi và hàng đợi ưu tiên.

Dequeue về cơ bản là hàng đợi kết thúc kép. Vì vậy có hai cặp phía trước và hai phía sau. Một cặp con trỏ phía trước và phía sau được sử dụng để mô tả hàng đợi từ phía bên trái và một cặp khác được sử dụng để mô tả hàng đợi từ phía bên phải. Chúng ta có thể chèn hoặc xóa các phần tử từ cả hai bên trong cấu trúc này. Ở đây chúng ta sẽ thấy một số mã C ++ sử dụng dequeue STL để hiểu chức năng của nó.

Ví dụ (Dequeue)

#include <iostream>
#include <deque>
using namespace std;
void dequeElements(deque <int> que) {
   deque <int> :: iterator it;
   for (it = que.begin(); it != que.end(); ++it)
      cout << *it << " ";
   cout <<endl;
}
int main() {
   deque <int> que;
   que.push_back(10);
   que.push_front(20);
   que.push_back(30);
   que.push_front(15);
   cout << "Currently que is holding : ";
   dequeElements(que);
   cout <<"Size of dequeue : " <<que.size() << endl;
   cout << "Element at position 2 : " << que.at(2) << endl;
   cout << "Element at front position : " << que.front() << endl;
   cout << "Element at back position : " << que.back() << endl;
   cout << "Delete from front side : ";
   que.pop_front();
   dequeElements(que);
   cout << "Delete from back side : ";
   que.pop_back();
   dequeElements(que);
}

Đầu ra

Currently que is holding : 15 20 10 30
Size of dequeue : 4
Element at position 2 : 10
Element at front position : 15
Element at back position : 30
Delete from front side : 20 10 30
Delete from back side : 20 10

Một biến thể khác của hàng đợi là hàng đợi ưu tiên. Trong cấu trúc này, mỗi phần tử trong hàng đợi có mức độ ưu tiên riêng. Khi chúng tôi chèn mục vào hàng đợi, chúng tôi phải gán giá trị ưu tiên với nó. Nó sẽ xóa phần tử ưu tiên cao nhất lúc đầu. Để triển khai hàng đợi ưu tiên, một trong những phương pháp đơn giản nhất là sử dụng cấu trúc dữ liệu heap.

Hãy để chúng tôi xem một mã C ++ cho STL hàng đợi ưu tiên. Ở đây mức độ ưu tiên được chỉ định dựa trên giá trị. Vì vậy, giá trị cao hơn sẽ được coi là phần tử có mức độ ưu tiên cao nhất.

Ví dụ (Hàng đợi Ưu tiên)

#include <iostream>
#include <queue>
using namespace std;
void dequeElements(priority_queue <int> que) {
   priority_queue <int> q = que;
   while(!q.empty()){
      cout << q.top() << " ";
      q.pop();
   }
   cout << endl;
}
int main() {
   priority_queue <int> que;
   que.push(10);
   que.push(20);
   que.push(30);
   que.push(5);
   que.push(1);
   cout << "Currently que is holding : ";
   dequeElements(que);
   cout << "Size of queue : " <<que.size() << endl;
   cout << "Element at top position : " << que.top() << endl;
   cout << "Delete from queue : ";
   que.pop();
   dequeElements(que);
   cout << "Delete from queue : ";
   que.pop();
   dequeElements(que);
}

Đầu ra

Currently que is holding : 30 20 10 5 1
Size of queue : 5
Element at top position : 30
Delete from queue : 20 10 5 1
Delete from queue : 10 5 1