首页 > 代码库 > STL 队列 、优先队列、栈 小结

STL 队列 、优先队列、栈 小结

学长说现在基本上可以开始学习STL中一些标准模板了,今天先总结一下 队列、栈、优先队列

1、队列(queue)


      先进先出原则,头文件#include <queue>,定义结构queue<类型>名称;queue<int>q、queue<node>q等;

如:

struct node
{
      int x;
}f;
queue<node>q;//结构体类型队列

q.push(f) //将f压入队列的尾部


node t = q.pop()// 弹出队列的第一个元素(队首元素),此函数无返回值


node t = q.front() //返回第一个元素(队首元素)


q.back() //返回最后被压入的元素(队尾元素)


q.empty() //当队列为空时,返回true


q.size() //返回当前状态返回队列的长度


2.栈

      先进后出原则,头文件#include <stack>,定义结构stack<类型>名称;stack<int>s1;stack<string>s2等


struct node{
     int x;
}f;
stack<node>stk;
stk.push(f) //将f压入栈中

stk.pop() //出栈(删除栈顶元素),无返回值

stk.top() //返回当前状态的栈顶元素

stk.size() //栈中的元素个数

stk.empty() //当栈为空时,返回 true


3、优先队列

                 和队列相同,只是加了一步优先级判断,来确定出队顺序,定义方式priority_queue<int>q;

代码模板

#include <iostream>
#include <queue>
#include <cstring>
#include <cstdio>
using namespace std;
struct node{
    int x,y;
    friend bool operator < (const node &a,const node &b)//操作符重载,不要重载‘>’,会CE
    {
        return a.x>b.x; //x小的优先级高,先出队
    }
}k;
struct cmp //自定义比较函数
{
    bool operator  ()(int x, int y)
    {
        return x > y;// x小的 优先级高
     }
};
int main()
{
    int n;
    cin>>n;
    priority_queue<int, vector<int>, cmp>Q;// vector容器类型,cmp自定义比较函数

    priority_queue<node>q;
    for(int i = 0;i< n;i++)
    {
        cin>>k.x>>k.y;
        q.push(k);
        Q.push(k.x);
    }
    puts("---------------------");

    while(!q.empty())
    {
        node t = q.top();
        cout<<t.x <<' '<< t.y<<endl;
        q.pop();
    }
    puts("-----自定义比较函数--------");
    puts("队列:x从小到大输出");
    cout<<endl;
     while(!Q.empty())
    {
        int t = Q.top();
        cout<<t<<endl;
        Q.pop();
    }
return 0;
}