C++ Primer 学习笔记_11_标准模板库_stack、queue队列容器与priority_queue优先队列容器
1、stack堆栈
stack堆栈是一个后进先出（Last In First Out，LIFO）的线性表，插入和删除元素都只能在表的一端进行。插入元素的一端称为栈顶，而另一端称为栈底。插入元素叫入栈(Push)，删除元素叫出栈(Pop)。下图是堆栈示意图
#include <iostream>#include <stack> using namespace std; int main(int argc, char* argv[]){ stack<int> s; s.push(1); s.push(2); s.push(3); s.push(9);cout << "栈顶元素为：" << s.top() << endl;cout << "堆栈元素数量：" << s.size() << endl;while(s.empty() != true){cout << "栈顶元素为：" << s.top() << endl;s.pop(); //出栈}if(s.empty())cout << "empty" << endl; return 0;}
运行结果：
栈顶元素为：9
堆栈元素数量：4
栈顶元素为：9
栈顶元素为：3
栈顶元素为：2
栈顶元素为：1
empty
2、队列容器queue
队列容器queue是一个先进先出（FirstIn First Out，FIFO）的线性存储表，元素的插入只能在队尾，元素的删除只能在队首。图2-10是queue队列容器数据结构示意图。
queue队列具有入队push()、出队pop()、读取队首元素front()、读取队尾元素back()、判断队列是否为空empty()和队列当前元素的数目size()几种方法。
#include <iostream>#include <queue> using namespace std; int main(int argc, char* argv[]){ queue<int> num; num.push(1); num.push(2); num.push(3); num.push(9);cout << num.size() << endl; cout << num.empty() << endl; cout << num.front() << endl; cout << num.back() << endl; while(!num.empty()){cout << num.front() << " ";num.pop();} cout << endl; return 0;}
运行结果：
4
0
1
9
12 3 9
3、优先队列容器priority_queue
优先队列容器priority_queue与队列一样，只能从队尾插入元素，从队首删除元素。但它有一个特性，就是队列中最大的元素总是位于队首，所以出队时，并非按先进先出的原则进行，而是将当前队列中最大的元素出队。这点类似于给队列里的元素进行了由大到小的顺序排序。元素的比较规则默认按元素的值由大到小排序；当然，可以重载“<”操作符来重新定义比较规则。也可以重载“()”重新定义比较规则。
声明的头文件也为#include<queue>。
3.1 优先队列的使用方法
优先队列包含入队push()、出队pop()、读取队首元素top()、判断队列是否为空empty()和队列当前元素的数目size()几种方法。
#include <iostream>#include <queue> using namespace std; int main(int argc, char* argv[]){ priority_queue<int> num; num.push(1); num.push(2); num.push(3); num.push(9);cout << num.size() << endl; cout << num.empty() << endl; cout << num.top() << endl; while(!num.empty()){cout << num.top() << " ";num.pop();} cout << endl; return 0;}
运行结果：
4
0
9
93 2 1
3.2 重载“<”操作符来定义优先级
如果优先队列的元素类型是结构体，，可以通过在结构体中重载“<”操作符的方法来修改优先队列的优先级。
#include <iostream>#include <queue>#include <string> using namespace std; struct Info{ string name; float score; bool operator < (const Info &a) const{return a.score < score;}}; int main(int argc, char* argv[]){ priority_queue<Info> student; Info info;info.name = "Jack"; info.score = 68.5; student.push(info);info.name = "Bomi"; info.score = 18.5; student.push(info);info.name = "Peti"; info.score = 90; student.push(info);while(!student.empty()){cout << student.top().name << " : " <<student.top().score << endl;student.pop();} return 0;}
运行结果：
Bomi ： 18.5
Jack ： 68.5
Peti ： 90
3.3 重载“()”操作符来定义优先级
如果优先队列的元素不是结构体类型，则可以通过重载“()”操作符的方式来定义优先级。当然，元素是结构体类型，也可以通过重载“()”操作符的方式来定义优先级，而不一定要在结构体内重载“<”操作符才行。
#include <iostream>#include <queue>#include <vector> using namespace std; struct myComp{booloperator () (const int &a, const int &b){return a > b;}}; int main(int argc, char* argv[]){ //定义优先队列，元素类型为myComp，显式说明内部结构式vector priority_queue<int, vector<int>, myComp> num; num.push(1); num.push(9); num.push(2); num.push(30);while(!num.empty()){cout << num.top() << " ";num.pop();} cout << endl; return 0;}
运行结果；
12 9 30
版权声明：本文为博主原创文章，未经博主允许不得转载。
你可以很有个性，但某些时候请收敛。
