零、前言
本章主要讲解学习C++中的容器stack（栈），queue（队列），priority_queue（优先级队列，相当于数据结构中的heap（堆）），在熟悉使用后进行模拟实现
一、stack的介绍和使用
1、stack的介绍
stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作
stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出
stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：
empty：判空操作
back：获取尾部元素操作
push_back：尾部插入元素操作
pop_back：尾部删除元素操作
标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque(双端队列，也是一种容器)
示图：
2、stack的使用
例题1：用栈实现队列
力扣链接：232. 用栈实现队列 - 力扣（LeetCode） (leetcode-cn.com)
实现思路：
这里需要两个栈，一个栈用来入数据，一个栈用来出数据
push：只往入数据栈入数据
pop：只让出数据栈出数据，如果没有数据，则需将入数据中的数据全部依次出栈并随后入栈到出数据栈中
以此实现队列先进先出的特性
实现代码：
class MyQueue { public: MyQueue() { //不需要写什么，对于自定义类型stack会自动调用其构造函数 } void push(int x) { //入栈栈入数据 st1.push(x); } int pop() { int ret; //出栈栈有无数据 if(!st2.empty()) { ret=st2.top(); st2.pop(); return ret; } else { //将数据入栈出栈 while(!st1.empty()) { st2.push(st1.top()); st1.pop(); } //pop数据 ret=st2.top(); st2.pop(); return ret; } } int peek() { if(!st2.empty()) { return st2.top(); } else { while(!st1.empty()) { st2.push(st1.top()); st1.pop(); } return st2.top(); } } bool empty() { return st1.empty()&&st2.empty(); } private: stack<int> st1; stack<int> st2; };
二、queue的介绍和使用
1、queue的介绍
队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素
队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素；元素从队尾入队列，从队头出队列
底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
empty：检测队列是否为空
size：返回队列中有效元素的个数
front：返回队头元素的引用
back：返回队尾元素的引用
push_back：在队列尾部入队列
pop_front：在队列头部出队列
标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque(双端队列)
示图：
2、queue的使用
例题2：用队列实现栈
力扣链接：225. 用队列实现栈 - 力扣（LeetCode） (leetcode-cn.com)
实现思路：
这里我们也需要两个队列
push：往有数据的队列入队列
pop：将有数据队列的数据（除最后一个数据）给依次出队列并入队列到另一个队列中，最后将最后一个数据给出队列
以此实现栈的先进后出的特性
实现代码：
class MyStack { public: MyStack() { } void push(int x) { //入有数据队列 if(q1.empty()) { q2.push(x); } else { q1.push(x); } } int pop() { //确定哪个队列有数据 queue<int>*q=&q1; queue<int>*nonq=&q2; if(q1.empty()) { q=&q2; nonq=&q1; } //出队列再入队列 while(q->size()>1) { nonq->push(q->front()); q->pop(); } //pop数据 int ret=q->front(); q->pop(); return ret; } int top() { if(!q1.empty()) { return q1.back(); } else { return q2.back(); } } bool empty() { return q1.empty()&&q2.empty(); } private: queue<int> q1; queue<int> q2; };
