C++ Queues(队列)、Priority Queues(优先队列)

一时失言乱红尘 2022-05-28 11:30 319阅读 0赞

**C++ Queues(队列)**  
  
C++队列是一种容器适配器，它给予程序员一种先进先出(FIFO)的数据结构。  
1.back() 返回一个引用，指向最后一个元素  
2.empty() 如果队列空则返回真  
3.front() 返回第一个元素  
4.pop() 删除第一个元素  
5.push() 在末尾加入一个元素  
6.size() 返回队列中元素的个数  
  
队列可以用线性表(list)或双向队列(deque)来实现(注意vector container 不能用来实现queue，因为vector 没有成员函数pop\_front!)：  
queue<list<int>> q1;  
queue<deque<int>> q2;  
其成员函数有“判空(empty)” 、“尺寸(Size)” 、“首元(front)” 、“尾元(backt)” 、“加入队列(push)” 、“弹出队列(pop)”等操作。

例：

int main()
     {
         queue<int> q;
        q.push(4);
         q.push(5);
         printf("%d\n",q.front());
         q.pop();
     }

C++ Priority Queues(优先队列)  
  
C++优先队列类似队列，但是在这个数据结构中的元素按照一定的断言排列有序。  
1.empty() 如果优先队列为空，则返回真  
2.pop() 删除第一个元素  
3.push() 加入一个元素  
4.size() 返回优先队列中拥有的元素的个数  
5.top() 返回优先队列中有最高优先级的元素  
  
优先级队列可以用向量(vector)或双向队列(deque)来实现(注意list container 不能用来实现queue，因为list 的迭代器不是任意存取iterator，而pop 中用到堆排序时是要求randomaccess iterator 的!)：  
priority\_queue<vector<int>, less<int>> pq1; // 使用递增less<int>函数对象排序  
priority\_queue<deque<int>, greater<int>> pq2; // 使用递减greater<int>函数对象排序  
其成员函数有“判空(empty)” 、“尺寸(Size)” 、“栈顶元素(top)” 、“压栈(push)” 、“弹栈(pop)”等。

例：

#include <iostream>
      #include <queue> 
      using namespace std;
       
      class T {
      public:
          int x, y, z; 
        T(int a, int b, int c):x(a), y(b), z(c)
          { 
         }
     };
     bool operator < (const T &t1, const T &t2) 
     {
         return t1.z < t2.z; // 按照z的顺序来决定t1和t2的顺序
     } 
     main()
     { 
         priority_queue<T> q; 
         q.push(T(4,4,3)); 
         q.push(T(2,2,5)); 
         q.push(T(1,5,4)); 
         q.push(T(3,3,6)); 
         while (!q.empty()) 
         { 
             T t = q.top(); 
             q.pop(); 
             cout << t.x << " " << t.y << " " << t.z << endl; 
         } 
         return 1; 
     }

输出结果为(注意是按照z的顺序从大到小出队的)：   
 3 3 6   
 2 2 5   
 1 5 4   
 4 4 3

再看一个按照z的顺序从小到大出队的例子：

#include <iostream> 
      #include <queue> 
      using namespace std; 
      class T 
      { 
      public: 
          int x, y, z; 
          T(int a, int b, int c):x(a), y(b), z(c) 
          {
         } 
     }; 
     bool operator > (const T &t1, const T &t2) 
     { 
         return t1.z > t2.z; 
     } 
     main() 
     { 
         priority_queue<T, vector<T>, greater<T> > q; 
         q.push(T(4,4,3)); 
         q.push(T(2,2,5)); 
         q.push(T(1,5,4)); 
         q.push(T(3,3,6)); 
         while (!q.empty()) 
         { 
             T t = q.top(); 
             q.pop(); 
             cout << t.x << " " << t.y << " " << t.z <<  endl; 
         } 
         return 1; 
     }

输出结果为：   
 4 4 3   
 1 5 4   
 2 2 5   
 3 3 6

如果我们把第一个例子中的比较运算符重载为： bool operator < (const T &t1, const T &t2) \{ return t1.z > t2.z; // 按照z的顺序来决定t1和t2的顺序\} 则第一个例子的程序会得到和第二个例子的程序相同的输出结果。

自己写的实例：

#include<stdio.h>
    #include<queue>
    using namespace std;
    struct T
    {
        int x,y,z;
    };
     bool operator > (const T &t1, const T &t2)
    {
        return t1.z < t2.z;
    }
    int main()
    {
       priority_queue<T, vector<T>, greater<T> > q;
       struct T t;
       t.z=5;
       q.push(t);
       t.z=2;
       q.push(t);
       t.z=3;
       q.push(t);
       t.z=1;
       q.push(t);
       while(!q.empty())
       {
           struct T tmp=q.top();
           q.pop();
           printf("%d\n",tmp.z);
       }
    }