STL之queue队列 stack栈 priority_queue优先队列 deque双向队列

た入场券 2021-06-24 15:57 410阅读 0赞

## **一、queue** ##

先进先出  
empty() 是否为空  
size() 返回大小  
front() 返回队头数据  
back() 返回队尾数据  
push() 队尾压入一个数据  
pop() 抛弃队头数据

## **stack** ##

后进先出  
empty() 是否为空  
size() 返回大小  
top 返回栈顶数据  
push() 栈顶压入一个数据  
pop() 抛弃栈顶数据

## **二、priority\_queue** ##

一般方法：  
empty() 是否为空  
size() 返回大小  
push() 队尾压入一个数据  
pop() 抛弃队头数据  
top() 返回队头数据(并不会抛弃，需手动pop)

优先队列可以实现自动排序。其模板声明如下：  
priority\_queue

int a[3] = {
       1，2，3};
    priority_queue<int> pq;
    for(i = 0; i < 3; i++)
        pq.push(a[i]);
    for(i = 0; i < 3; i++)
    {
        cout<<pq.top()<<" ";   // 输出:3 2 1。默认大顶堆，元素大的优先级高
        pq.pop();
    }

实现小顶堆：

priority_queue<int, vector<int>, greater<int> > pq;

struct Node{
        int x, y;
        Node(int a, int b): x(a), y(b) {}
        friend bool operator<(Node left, Node right){
            if( left.x == right.x ) return left.y> right.y;
            return left.x> right.x;
        }
    };
    priority_queue<Node> pq;  // 只需定义一个struct就行了。

struct Node{
        int x, y;
        Node(int a, int b): x(a), y(b) {}
        friend bool operator<(Node left, Node right){
            if( left.x == right.x ) return left.y> right.y;
            return left.x> right.x;
        }
    };
    struct Cmp{
        bool operator() (Node left, Node right){
            if( left.x == right.x ) return left.y> right.y;
            return left.x> right.x;
        }
    };
    priority_queue<Node, vector<Node>, Cmp> pq;  // 第三个参数自定义时需分开。

## **三、deque** ##

deque second (4,100)  
at \[\]  
front()  
back()  
push\_back()  
pop\_back()  
push\_front()  
pop\_front()  
insert()  
erase()  
empty()  
size()

## **其他** ##

函数特化同时使用front和top：

#include <iostream>
    #include <queue>
    
    template <typename Q> struct get_top;
    
    template <typename T> struct get_top <std::queue<T>>
    {
     static void apply (std::queue<T> const& q)
     {
      std::cout << "std::queue" << std::endl;
      q.front();
     }
    };
    
    template <typename T> struct get_top <std::priority_queue<T>>
    {
     static void apply (std::priority_queue<T> const& q)
     {
      std::cout << "std::priority_queue" << std::endl;
      q.top();
     }
    };
    
    template <typename Q>
    void t (Q const& q)
    {
     get_top<Q>::apply(q);
    }
    
    int main ()
    {
     std::queue<int> q0; t(q0);
     std::priority_queue<int> q1; t(q1);
    
     return 0;
    }