stack堆栈容器

stack 堆栈是一个后进先出的线性表，插入和删除元素都只能在表的一端进行。

堆栈只提供入栈push()、出栈pop()、栈顶元素访问top() 和判断是否为空empty() 等几种方法，用 size()方法返回当前堆栈中有几个元素。

#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;

int main()
{
    stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);
    s.push(9);
    //读取栈顶元素
    cout<<s.top()<<endl;
    //返回堆栈元素数量
    cout<<s.size()<<endl;
    //判断堆栈是否为空
    cout<<s.empty()<<endl;
    //所有元素出栈(删除所有元素)
    while(s.empty()!=true)//堆栈非空
    {
        cout<<s.top()<<" ";//读取栈顶元素
        s.pop();//出栈(即删除栈顶元素)
    }
    cout<<endl;

    return 0;
}
=>
9
4
0
9 3 2 1 

queue 队列容器

queue 队列容器是一个先进先出的线性存储表，元素的插入只能在队尾，删除只能在队首。

queue 队列具有入队 push()、出队 pop()(即删除元素)、读取队首元素 front()、读取队尾元素 back()、判断队列是否为空 empty()和队列当前元素的数目 size()这几种方法。

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int main()
{
    queue<int> q;
    //入队,即插入元素
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(9);
    //返回队列元素数量
    cout<<q.size()<<endl;
    //队列是否为空,是空,则返回逻辑真,否则返回逻辑假
    cout<<q.empty()<<endl;
    //读取队首元素
    cout<<q.front()<<endl;
    //读取队尾元素
    cout<<q.back()<<endl;
    //所有的元素出列(删除所有元素)
    while(q.empty()!=true)
    {
        cout<<q.front()<<" ";
        //队首元素出队(删除队首元素)
        q.pop();
    }
    cout<<endl;

    return 0;
}
=>
4
0
1
9
1 2 3 9 

priority_queue 优先队列容器

与queue不同的是队列中最大的元素总是位于队首，所以出队时并非按先进先出的原则进行，而是将当前队列中最大的元素出队。优先队列同样包含入队 push()(插入元素)、出队 pop()(删除元素)、读取队首元素 top()、判断队列是否为空 empty()和读取队列元素数量 size()等方法。使用方法也与queue同，声明为priority_queue<int> pq。

优先队列默认是最大的元素优先级最高。

1. 对于结构体元素类型，可通过重载“<”操作符来定义优先级。

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

struct Info
{
    string name;
    float score;
    //重载“<”操作符,指定优先规则(排序规则)
    bool operator < (const Info &a) const
    {
        //按 score 由小到大排列。如果要由大到小排列,使用“>”号即可
        return a.score < score;
    }
};
int main()
{
    //定义优先队列,元素类型为 Info 结构体
    priority_queue<Info> pq;
    //定义结构体变量
    Info info;
    //入队
    info.name="Jack";
    info.score=68.5;
    pq.push(info);
    info.name="Bomi";
    info.score=18.5;
    pq.push(info);
    info.name="Peti";
    info.score=90;
    pq.push(info);
    //元素全部出队
    while(pq.empty()!=true)
    {
        //返回队首元素
        cout<<pq.top().name<<" : "<<pq.top().score<<endl;
        //出队,删除队首元素
        pq.pop();
    }
    return 0;
}
=>
Bomi : 18.5
Jack : 68.5
Peti : 90

2. 对于元素非结构体类型的，只能通过重载“()”操作符来定义优先级。但元素是结构体类型的也可用此种方式。

#include <algorithm>
#include <queue>
using namespace std;

//重载“()”操作符
struct cmp
{
    bool operator()(const int &a, const int &b)
    {
        //由小到大排列采用“>”号;如果要由大到小排列,则采用“<”号
        return a > b;
    }
};
int main()
{
    priority_queue<int,vector<int>, cmp> pq;
    //入队
    pq.push(1);
    pq.push(9);
    pq.push(2);
    pq.push(30);
    //元素全部出队
    while(pq.empty()!=true)
    {
        //返回队首元素
        cout<<pq.top()<<" ";
        //出队,删除队首元素
        pq.pop();
    }
    cout<<endl;
    return 0;
}
=>
1 2 9 30