STL之queue队列 stack栈 priority_queue优先队列 deque双向队列-蒲公英云

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

た入场券 2021-06-24 15:57 532阅读 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;
}