stack堆棧容器

堆棧只提供入棧push()、出棧pop()、棧頂元素訪問(wèn)top() 和判斷是否為空empty() 等幾種方法，用 size()方法返回當(dāng)前堆棧中有幾個(gè)元素。

#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;
    //返回堆棧元素?cái)?shù)量
    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 隊(duì)列容器

queue 隊(duì)列具有入隊(duì) push()、出隊(duì) pop()(即刪除元素)、讀取隊(duì)首元素 front()、讀取隊(duì)尾元素 back()、判斷隊(duì)列是否為空 empty()和隊(duì)列當(dāng)前元素的數(shù)目 size()這幾種方法。

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

int main()
{
    queue<int> q;
    //入隊(duì),即插入元素
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(9);
    //返回隊(duì)列元素?cái)?shù)量
    cout<<q.size()<<endl;
    //隊(duì)列是否為空,是空,則返回邏輯真,否則返回邏輯假
    cout<<q.empty()<<endl;
    //讀取隊(duì)首元素
    cout<<q.front()<<endl;
    //讀取隊(duì)尾元素
    cout<<q.back()<<endl;
    //所有的元素出列(刪除所有元素)
    while(q.empty()!=true)
    {
        cout<<q.front()<<" ";
        //隊(duì)首元素出隊(duì)(刪除隊(duì)首元素)
        q.pop();
    }
    cout<<endl;

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

priority_queue 優(yōu)先隊(duì)列容器

與queue不同的是隊(duì)列中最大的元素總是位于隊(duì)首，所以出隊(duì)時(shí)并非按先進(jìn)先出的原則進(jìn)行，而是將當(dāng)前隊(duì)列中最大的元素出隊(duì)。優(yōu)先隊(duì)列同樣包含入隊(duì) push()(插入元素)、出隊(duì) pop()(刪除元素)、讀取隊(duì)首元素 top()、判斷隊(duì)列是否為空 empty()和讀取隊(duì)列元素?cái)?shù)量 size()等方法。使用方法也與queue同，聲明為priority_queue<int> pq。

優(yōu)先隊(duì)列默認(rèn)是最大的元素優(yōu)先級(jí)最高。

1. 對(duì)于結(jié)構(gòu)體元素類(lèi)型，可通過(guò)重載“<”操作符來(lái)定義優(yōu)先級(jí)。

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

struct Info
{
    string name;
    float score;
    //重載“<”操作符,指定優(yōu)先規(guī)則(排序規(guī)則)
    bool operator < (const Info &a) const
    {
        //按 score 由小到大排列。如果要由大到小排列,使用“>”號(hào)即可
        return a.score < score;
    }
};
int main()
{
    //定義優(yōu)先隊(duì)列,元素類(lèi)型為 Info 結(jié)構(gòu)體
    priority_queue<Info> pq;
    //定義結(jié)構(gòu)體變量
    Info info;
    //入隊(duì)
    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);
    //元素全部出隊(duì)
    while(pq.empty()!=true)
    {
        //返回隊(duì)首元素
        cout<<pq.top().name<<" : "<<pq.top().score<<endl;
        //出隊(duì),刪除隊(duì)首元素
        pq.pop();
    }
    return 0;
}
=>
Bomi : 18.5
Jack : 68.5
Peti : 90

2. 對(duì)于元素非結(jié)構(gòu)體類(lèi)型的，只能通過(guò)重載“()”操作符來(lái)定義優(yōu)先級(jí)。但元素是結(jié)構(gòu)體類(lèi)型的也可用此種方式。

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

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