目录
stack介绍
我们可以搜一些资料学习栈：栈文档
栈的结构
我们很熟悉了，栈的结构：
栈接口的使用
这些接口比较简单，这里不过多赘述！
栈的基本题目
最小栈
地址：最小栈
思路：
题目的本质是，我们要得到一个栈中的最小元素！
我们可以用两个栈实现一个栈的功能：
定义一个栈_st,里面存储所有插入进来的数据，定义另一个栈_minst,存储小数据，不管在什么时候我们都保证它的栈顶元素是所有数据最小的数。
于是，我们拿栈中的最小元素，只需要返回_minst的栈顶元素即可！
那么关键就在于怎么进行插入和删除的操作而已！
插入时，无论什么数据，_st都要插入，当_minst是空的时候，或者插入的元素小于_minst的栈顶元素时，_minst也插入！
删除时，无论什么数据，_st都要删除，当要删除的元素等于_minst的栈顶元素时，_minst也删除！
代码：
class MinStack {
public:
MinStack() {
}
void push(int val) {
//无论如何_st，_st都要push
_st.push(val);
//当_minst为空，或者栈顶元素小于或等于val，_minst也push
if(_minst.empty()||val<=_minst.top())
_minst.push(val);
}
void pop() {
//当_st栈顶的元素和_minst栈顶元素相等，_minst也pop
if(_st.top()==_minst.top())
_minst.pop();
//无论如何，_st都要pop
_st.pop();
}
int top() {
return _st.top();
}
int getMin() {
return _minst.top();
}
private:
stack<int> _st;//存储所有数据
//存储小数据，无论什么时候，它的栈顶一定是所有数据最小的那个
stack<int> _minst;
};
栈的弹出压入序列
地址：栈的弹出压入序列
思路：
我们需要模拟入栈出栈即可！
遍历压入序列，入栈，用 i 记录出栈序列的下标，当栈顶元素和出栈序列相等时，出栈，同时 i++，往前走，当栈顶元素和出栈序列不相等时，继续遍历入栈！
有一种情况：比如压入序列：2，1，0,弹出序列：1，2，0。
当入栈到1时，一直出栈到空，此时0还没有入栈，然后判断条件栈顶元素和出栈序列相等，判断不了，因为此时栈是空的，没有栈顶元素，所以我们需要加一个判断条件：栈不为空！
代码：
bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
// write code here
stack<int> _st;
size_t i=0;//遍历popV
//遍历插入
for(auto& e:pushV)
{
_st.push(e);
//当栈顶元素和popV的元素相等，栈pop
while(!_st.empty()&&_st.top()==popV[i])
{
_st.pop();
i++;
}
}
return _st.empty();
}二叉树的分层遍历
地址：二叉树的层序遍历
思路：
我们首先让根节点先进入队列，根据对头左右节点有就继续进队列，然后队头出队列，循环往复。
只是我们需要插入进一个二维数组，我们可以将这颗树的每一层有多少个节点记录下来！
代码：
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
queue<TreeNode*> q;
vector<vector<int>> vv;
int lsize;
if(root)
{
q.push(root);
lsize=1;
}
while(!q.empty())
{
vector<int> v;
while(lsize--)
{
if(q.front()->left)
q.push(q.front()->left);
if(q.front()->right)
q.push(q.front()->right);
v.push_back(q.front()->val);
q.pop();
}
lsize=q.size();
vv.push_back(v);
}
return vv;
}
};栈的模拟实现
我们仔细观察栈的结构（先进后出），仔细想一下，发现我们可以用一个动态数组来实现它（也可以用链表），
所以我们可以用vector来包装它！
这样就简单很多！
stack.h文件
#include<iostream>
#include<vector>
namespace ywc
{
template<class T>
class stack
{
public:
bool empty()
{
return _s.empty();
}
size_t size()
{
return _s.size();
}
const T& top()
{
return _s.back();
}
void push(const T& x)
{
_s.push_back(x);
}
void pop()
{
_s.pop_back();
}
private:
std::vector<T> _s;
};
}当然，也能用链表实现！这里不过多赘述！
队列的介绍
文档：队列文档
队列的结构
队列接口的使用
这里也不过多赘述，比较简单！
队列的模拟实现
队列是先进先出，需要头删，用一个动态数组效率太慢，所以我们采用链表！
我们可以用一个list来包装！
代码：
#include<iostream>
#include<list>
namespace ywc
{
template<class T>
class queue
{
public:
bool empty()
{
return _lt.empty();
}
size_t size()
{
return _lt.size();
}
const T& front()
{
return _lt.front();
}
const T& back()
{
return _lt.back();
}
void push(const T& x)
{
_lt.push_back(x);
}
void pop()
{
_lt.pop_front();
}
private:
std::list<T> _lt;
};
}priority_queue的介绍和使用
优先级队列的文档：优先级队列文档
简单介绍一下优先级队列：
不管什么时候，它的第一个元素总是最大的！也能随时插入元素，且只能检索顶部数据，且要删除数据也是删除顶部数据！
所以：
优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用 priority_queue。注意：默认情况下priority_queue是大堆。
简单赘述：
优先级队列是底层是一个动态数组（堆），在数组尾部插入，然后利用向上调整法调整数据的分布从而符合堆的特性（大小堆），删除数据时，删除第一个数据，然后利用向下调整法调整数据的分布从而符合堆的特性！
接口使用
接口比较简单，这里不过多赘述！
我们来看一下它的大小堆特性：
但当我们的类型是自定义类型的话：
如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重 载。
如：
优先级队列的题目应用
数组中第k大的数字
思路：
我们可以将数组中的数全部放进一个大堆中，然后将前k-1个数删掉，然后栈顶就是我们的第k个大的数字！
代码：
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
//将数组中的数全部放在一个大堆中
priority_queue<int> q;
for(auto& e:nums)
q.push(e);
while(--k)//将前k-1个数字pop掉
q.pop();
return q.top();
}
};优先级队列的模拟实现
根据刚才我们所说的它的特点来包装它，并且参照STL库中的方式！
我们的思路：
priority_queue.h文件
#pragma once
#include<iostream>
#include<vector>
#include<algorithm>
namespace ywc
{
template<class T>
struct less
{
bool operator()(const T& a, const T& b)
{
return a < b;
}
};
template<class T>
struct greater
{
bool operator()(const T& a, const T& b)
{
return a > b;
}
};
template<class T,class Container=std::vector<T>,class Compare=less<T>>
class priority_queue
{
public:
void push(const T& x)
{
_c.push_back(x);
//向上调整
AdjustUp(size() - 1);
}
void pop()
{
std::swap(_c[0], _c[size() - 1]);
_c.pop_back();
//向下调整
AdjustDown(0);
}
bool empty()
{
return size() == 0;
}
const T& top()
{
return _c.front();
}
size_t size() const
{
return _c.size();
}
private:
//向上调整
void AdjustUp(int child)
{
int parent = (child - 1) / 2;
while (child > 0)//当孩子等于0时跳出
{
if (Compare()(_c[parent],_c[child]))
{
std::swap(_c[child], _c[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
//向下调整
void AdjustDown(int parent)
{
int child = parent * 2 + 1;
while (child < size())
{
//假设法，假设左右孩子大小
if (child + 1 < size() && Compare()(_c[child ] , _c[child+1]))
{
child++;
}
if (Compare()(_c[parent] , _c[child]))
{
std::swap(_c[child], _c[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
Container _c;
};
}
deque的介绍
先前讲过stack底层是vector,queue底层是list，但其实在STL库中，stack和queue底层默认的容器是deque.
我们现在来介绍一下deque:
deque(双端队列)：是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)，与vector比较，头插效率高，不需要搬移元素；与 list比较，空间利用率比较高。
结构：
注意：deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个 动态的二维数组。
如图：
双端队列底层是一段假象的连续空间，实际是分段连续的，为了维护其“整体连续”以及随机访问 的假象，落在了deque的迭代器身上。
deque的缺陷
与vector比较，deque的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩 容时，也不需要搬移大量的元素，因此其效率是必vector高的。
与list比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。
deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其 是否移动到某段小空间的边界，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实 际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层数据结构。
为什么选择deque作为stack和queue的底层默认容器？
- stack和queue不需要遍历(因此stack和queue没有迭代器)，只需要在固定的一端或者两端进 行操作。
- 在stack中元素增长时，deque比vector的效率高(扩容时不需要搬移大量数据)；queue中的 元素增长时，deque不仅效率高，而且内存使用率高。
我们下期见！！！
标签：deque,队列,C++,queue,vector,child,push,stack From： https://blog.csdn.net/Qiwaw/article/details/145230462