day06:棧&隊(duì)列&優(yōu)先隊(duì)列

棧

棧：限定只在表尾進(jìn)行刪除插入操作的線性表。

也就是后進(jìn)先出（LIFO-last in first out）：最后插入的元素最先出來。

把允許刪除的一端稱為棧頂（Top）,另一端稱為棧底（Bottom）.不含任何數(shù)據(jù)元素的棧稱為空棧。

棧的插入操作，叫作進(jìn)棧，棧的刪除操叫做出棧。

#include<iostream>
#include<stack>
using namespace std;
stack <int> stk;//定義
/* stack <int> stk;     //定義
stk.push(i);            //入棧
int num = stk.size();   //返回棧內(nèi)元素的大小
bool flag = stk.empty();//如果棧為空返回true，否則返回false
int x = stk.top();      //返回棧頂，但不刪除成員
stk.pop();              //從棧頂彈出一個(gè)成員 */
int main(){
    for(int i=0; i<10; i++) stk.push(i); //入棧
    cout<<"棧的大小"<<stk.size()<<endl;   //返回棧內(nèi)元素的大小
    cout<<"棧內(nèi)元素：";
    while(!stk.empty()){      //如果棧為空返回true，否則返回false
        cout<<stk.top()<<" "; //返回棧頂，但不刪除成員
        stk.pop();            //從棧頂彈出一個(gè)成員
    }cout<<endl;
    cout<<"棧的大?。?<<stk.size()<<endl;
    return 0;
}
//運(yùn)行結(jié)果
棧的大?。?0
棧內(nèi)元素：9 8 7 6 5 4 3 2 1 0 
棧的大小：0

隊(duì)列

隊(duì)列（Queue）：是只允許在一端進(jìn)行插入操作，在另一端進(jìn)行刪除操作的線性表。

（在隊(duì)尾插入數(shù)據(jù)，隊(duì)頭刪除數(shù)據(jù)）

也就是先進(jìn)先出（FIFO-first in first out）：最先插入的元素最先出來。

循環(huán)隊(duì)列：隊(duì)列的頭尾相接的順序存儲(chǔ)結(jié)構(gòu)稱為循環(huán)隊(duì)列。

#include<iostream>
#include<queue>
using namespace std;
queue<int> que; //定義
/* queue<int> que;      //定義
que.push(i);            //入隊(duì)列
int num = que.size();   //返回隊(duì)列內(nèi)元素的個(gè)數(shù)
bool flag = que.empty();//如果隊(duì)列為空返回true，否則返回false
int x = que.front();    //返回隊(duì)首元素
int y = que.back();     //返回隊(duì)尾元素
que.pop();              //從隊(duì)首彈出一個(gè)成員*/
int main() {
    for(int i=0; i<10; i++)  que.push(i); //入隊(duì)
    cout<<"隊(duì)列的大?。?<<que.size()<<endl;//返回隊(duì)列內(nèi)元素的個(gè)數(shù)
    cout<<"隊(duì)首元素："<<que.front()<<endl;//隊(duì)首元素 
    cout<<"隊(duì)尾元素："<<que.back()<<endl; //隊(duì)尾元素
    cout<<"隊(duì)列元素：";
    while(!que.empty()){
        cout<<que.front()<<" ";
        que.pop(); //從隊(duì)首彈出一個(gè)成員
    } cout<<endl;
    cout<<"隊(duì)列的大?。?<<que.size()<<endl;//返回隊(duì)列內(nèi)元素的個(gè)數(shù)
    return 0;
}
//運(yùn)行結(jié)果
隊(duì)列的大小：10
隊(duì)首元素：0
隊(duì)尾元素：9
隊(duì)列元素：0 1 2 3 4 5 6 7 8 9 
隊(duì)列的大小：0

這里由于時(shí)間問題只是簡(jiǎn)單介紹了一下，更多的看這里

棧與隊(duì)列：http://www.rzrgm.cn/hellohebin/p/15677386.html

STL：http://www.rzrgm.cn/hellohebin/p/15677412.html

優(yōu)先隊(duì)列

優(yōu)先隊(duì)列：隊(duì)列中的元素被賦予優(yōu)先級(jí)，當(dāng)訪問元素時(shí)，具有最高優(yōu)先級(jí)的元素最先刪除。

優(yōu)先隊(duì)列具有最高級(jí)先出 （first in, largest out）的行為特征

優(yōu)先隊(duì)列具有隊(duì)列的所有特性，包括隊(duì)列的基本操作，只是在這基礎(chǔ)上添加了內(nèi)部的一個(gè)排序，它本質(zhì)是一個(gè)堆實(shí)現(xiàn)的。

//升序隊(duì)列，小頂堆
priority_queue <int,vector<int>,greater<int> > q;
//降序隊(duì)列，大頂堆
priority_queue <int,vector<int>,less<int> >q;

/*greater和less是std實(shí)現(xiàn)的兩個(gè)仿函數(shù)
就是使一個(gè)類的使用看上去像一個(gè)函數(shù)。
其實(shí)現(xiàn)就是類中實(shí)現(xiàn)一個(gè)operator()，
這個(gè)類就有了類似函數(shù)的行為，就是一個(gè)仿函數(shù)類了*/

優(yōu)先隊(duì)列的本質(zhì)就是堆，一棵完全二叉樹
二叉樹與堆：http://www.rzrgm.cn/hellohebin/p/15743136.html

對(duì)于優(yōu)先隊(duì)列還有更多的知識(shí)點(diǎn)，這里暫不多述，如有興趣，可以參考下面兩篇文章。

參考資料：
c++優(yōu)先隊(duì)列(priority_queue)用法詳解
C++STL——優(yōu)先隊(duì)列