stack和queue
1. stack
1.1 简单了解stack
- stack是一种容器适配器，是通过对特殊类或者容器的封装，获得想要的容器。stack的底层是类或者容器。
- stack支持后进先出，只能在一端进行操作。
- stack的底层容器应该支持stack的基本操作，例如push_back()尾插，pop_back()尾删，empty()判断栈空等操作。
- stack默认使用deque作为底层容器（后面讲），而vector、list也满足条件。
1.2 stack的常见接口
void test()
{
//构造
stack<int> st;
//push尾插
st.push(1);
st.push(2);
st.push(3);
st.push(4);
//empty判断为空
while (!st.empty())
{
//top输出栈顶元素
cout << st.top() << " ";
//pop尾删
st.pop();
}
cout << endl;
}
//结果
//4 3 2 1
1.3 练习
//思路：利用两个栈，_st将元素正常入栈，_minSt比较入栈元素和栈顶元素，
//小于或者等于栈顶元素就入栈;出栈时，如果_st的栈顶元素和_minSt的栈顶元素相同就一同出栈
class MinStack {
public:
MinStack() {}
void push(int val)
{
_st.push(val);
if(_minSt.empty()||val<=_minSt.top())
{
_minSt.push(val);
}
}
void pop()
{
if(_st.top()==_minSt.top())
{
_st.pop();
_minSt.pop();
}
else
{
_st.pop();
}
}
int top() {
return _st.top();
}
int getMin()
{
return _minSt.top();
}
private:
stack<int> _st;//用来存储正常元素
stack<int> _minSt; //用来存储最小元素
};
//根据入栈序列判断出栈序列是否正确
bool IsPopOrder(vector<int>& pushV, vector<int>& popV)
{
// write code here
stack<int> st;//用来入栈和出栈
int ipushV = 0;//用来记录入栈序列的下标
int ipopV = 0;//用来记录出栈序列的下标
//当入栈顶序列的元素都入栈顶后，停止循环
while(ipushV<pushV.size())
{
//直接入栈
st.push(pushV[ipushV++]);
//判断栈顶元素是否和出栈序列相同
//不同就继续入栈，相同就出栈，依次与出栈序列比较
if(st.top()!=popV[ipopV])
{
continue;
}
else
{
while(!st.empty()&&st.top()==popV[ipopV])
{
st.pop();
++ipopV;
}
}
}
//如果为空，说明出栈序列为真
return st.empty();
}
class Solution {
public:
//（1）逆波兰表达式是后缀表达式。
//（2）用后缀表达式计算出表达式的值，需要用到栈。
//（3）首先将操作数入栈，然后遇到操作符就取出栈顶两个元素进行运算，同时将计算结果入栈。
int evalRPN(vector<string>& tokens) {
stack<int> st;
for(size_t i = 0;i<tokens.size();i++)
{
if(tokens[i]=="+"||tokens[i]=="-"||tokens[i]=="*"||tokens[i]=="/")
{
//注意：先取出的是右操作数
int right = st.top();
st.pop();
int left = st.top();
st.pop();
//tokens每个元素都是string类型
switch(tokens[i][0])
{
case '+':
st.push(left+right);
break;
case '-':
st.push(left-right);
break;
case '*':
st.push(left*right);
break;
case '/':
st.push(left/right);
break;
}
}
else
{
st.push(stoi(tokens[i]));
}
}
return st.top();
}
};
1.4 模拟实现stack
namespace zn
{
//stack默认适配的容器是deque，deque后面会讲到
template<class T,class Container = deque<T>>
class stack
{
Container _con;
public:
//不用写构造，_con会自动调用其构造
void push(const T& val)
{
_con.push_back(val);
}
void pop()
{
_con.pop_back();
}
bool empty()
{
return _con.empty();
}
T& top()
{
return _con.back();
}
size_t size()
{
return _con.size();
}
};
void test_stack()
{
stack<int> st;
st.push(1);
st.push(2);
st.push(3);
st.push(4);
cout << st.size() << endl;
while (!st.empty())
{
cout << st.top() << " ";
st.pop();
}
cout << endl;
//底层容器也可以用vector和list
//stack<int, vector<int>> st1;
stack<int, list<int>> st2;
st2.push(1);
st2.push(2);
st2.push(3);
st2.push(4);
cout << st2.size() << endl;
while (!st2.empty())
{
cout << st2.top() << " ";
st2.pop();
}
}
}
2. queue
2.1 简单了解queue
- queue也是一种容器适配器。底层是特殊类或者其他容器。
- queue支持先进先出，只能在一端插入，在另一端删除。
- queue的底层容器应该支持queue的基本操作，例如push_back尾插，pop_front头删，front输出队头元素，back输出队尾元素等操作。
- 如果没有为queue指定容器，则默认使用deque。
2.2 queue的常见接口
void test1()
{
queue<int> q;
q.push(1);
q.push(2);
q.push(3);
q.push(4);
while (!q.empty())
{
cout << q.front() << " ";
q.pop();
}
cout << endl;
}
2.3 练习
class Solution {
public:
//思路：从上到下，将一层节点放到一个队列中，用vector<int>记录一层节点的值，将这层节点出队时同时将下一层节点入队（其中为了区分不同层次，利用levelsize记录每层节点的个数），再将vector<int>放到vector<vector<int>>中
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> vv;
int levelsize = 0;//记录当前这层的节点个数
queue<TreeNode*> q;
if(root!=nullptr)
{
q.push(root);
levelsize = 1;
}
while(!q.empty())
{
vector<int> v;
for(size_t i = 0;i<levelsize;i++)
{
TreeNode* tmp = q.front();
q.pop();
v.push_back(tmp->val);
if(tmp->left)
{
q.push(tmp->left);
}
if(tmp->right)
{
q.push(tmp->right);
}
}
vv.push_back(v);
levelsize = q.size();
}
return vv;
}
};
class Solution {
public:
//只需在上一题的基础上，加上逆置即可。
vector<vector<int>> levelOrderBottom(TreeNode* root) {
queue<TreeNode*> q;
vector<vector<int>> vv;
int levelSize;
if(root)
{
q.push(root);
levelSize = 1;
}
while(!q.empty())
{
vector<int> v;
for(int i = 0;i<levelSize;i++)
{
TreeNode* front = q.front();
q.pop();
v.push_back(front->val);
if(front->left)
{
q.push(front->left);
}
if(front->right)
{
q.push(front->right);
}
}
levelSize = q.size();
vv.push_back(v);
}
reverse(vv.begin(),vv.end());
return vv;
}
};
2.4 模拟实现queue
namespace zn
{
template<class T,class Container = deque<T>>
class queue
{
Container _con;
public:
void push(const T& val)
{
_con.push_back(val);
}
void pop()
{
_con.pop_front();
}
bool empty()
{
return _con.empty();
}
size_t size()
{
return _con.size();
}
T& front()
{
return _con.front();
}
T& back()
{
return _con.back();
}
};
void test_queue()
{
queue<int> qt;
qt.push(1);
qt.push(2);
qt.push(3);
qt.push(4);
cout << qt.front() << " " << qt.back() << endl;
while (!qt.empty())
{
cout << qt.front() << " ";
qt.pop();
}
cout << endl;
//queue的底层容器可以是list，但不适合用vector适配，
//因为vector没有提供头删的接口。如果要强制适配，可以用vector.erase(begin())
queue<int, list<int>> qt1;
qt1.push(1);
qt1.push(2);
qt1.push(3);
qt1.push(4);
cout << qt1.front() << " " << qt1.back() << endl;
while (!qt1.empty())
{
cout << qt1.front() << " ";
qt1.pop();
}
cout << endl;
}
}
3. deque（了解）
deque为什么可以作为stack和queue的底层容器？它到底是什么？它有什么优点和缺点？不急，先了解下deque。
deque是双端队列，是可以两端进行插入和删除的容器，具有一段“连续”的内存空间。
因此deque的头插头删和尾插尾删效率非常高，时间复杂度是O(1)，效率比vector高；因为是“连续”的空间，空间利用率比list高。
此处的“连续”并不是指物理上的连续，deque的内存空间是由一段一段的连续空间组成的，类似于二维数组，只不过这个二位数组可以扩容。
既然deque这么厉害，为什么只在stack和queue的底层才认识到它？deque看来是弥补了vector和list的缺点。但是没有取得其精华。相比于vector，deque极大缓解了扩容问题、头插头删问题，但下标访问不够极致，得计算在哪一段空间，在那段空间的第几个；相比于list，deque能够支持下标访问，因为空间是一段一段的，CPU高速缓存效率不错，头插头删不错，但中间插入和删除效率低。
综上，什么情况下使用deque最好？需要高频的头插头删和尾插尾删，不适合中间插入和删除以及高频的随机访问。用来适配stack和queue刚刚好（取其精华，去其糟粕）。
4. priority_queue
4.1 优先级队列的介绍
- priority_queue是容器适配器，底层是二叉树的堆，默认是大堆。
- priority_queue可以支持随机访问，并支持堆的基本操作，例如push_back尾插入，front输出堆顶元素，empty判断堆空，size输出元素数量。
- priority_queue的底层容器默认是vector，也可以用deque作为底层容器。
4.2 priority_queue的常见接口
void test_priority_queue()
{
priority_queue<int> pq;
//尾插
pq.push(1);
pq.push(3);
pq.push(4);
pq.push(2);
//判断是否为空
while (!pq.empty())
{
//输出堆顶元素
cout << pq.top() << " ";
//尾删（实际上是删除堆顶元素）
pq.pop();
}
cout << endl;
}
4.3 练习
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
//法1：建立大堆，pop（k-1）次，此时堆顶元素就是第k个最大元素
// priority_queue<int> pq(nums.begin(),nums.end());
// while(--k)
// {
// pq.pop();
// }
// return pq.top();
//法2：建立有k个元素的小堆，如果比堆顶元素大就入堆，最终堆顶元素就是第k个最大元素
priority_queue<int,vector<int>,greater<int>> pq;
size_t i = 0;
for(i = 0;i<k;i++)
{
pq.push(nums[i]);
}
for(;i<nums.size();i++)
{
if(nums[i]>pq.top())
{
pq.pop();
pq.push(nums[i]);
}
}
return pq.top();
}
};
4.4 模拟实现priority_queue
namespace zn
{
//仿函数本质上是一个类对象，可以像函数一样使用，所以叫仿函数
//模拟实现仿函数
template<class T>
class less
{
public:
bool operator()(const T& left, const T& right)
{
return left < right;
}
};
template<class T>
class greater
{
public:
bool operator()(const T& left, const T& right)
{
return left > right;
}
};
//有仿函数，只需要传递不同的仿造函数，不用修改代码，可以实现大堆和小堆
template<class T,class Container = vector<T>,class Compare = less<T>>
class priority_queue
{
Container _con;
void AdjustDown(int parent)
{
Compare com;
int child = 2 * parent + 1;
while (child < size())
{
if (child + 1 < size() && com(_con[child], _con[child + 1]))
{
++child;
}
if (com(_con[parent], _con[child]))
{
swap(_con[parent], _con[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void swap(T& left, T& right)
{
T tmp = left;
left = right;
right = tmp;
}
void AdjustUp(int child)
{
Compare com;
int parent = (child - 1) / 2;
while (child > 0)
{
if (com(_con[parent], _con[child]))
{
swap(_con[parent], _con[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
public:
priority_queue()
{}
template<class InputIterator>
priority_queue(InputIterator begin,InputIterator end)
{
while (begin != end)
{
_con.push_back(*begin);
++begin;
}
for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(i);
}
}
void push(const T& val)
{
_con.push_back(val);
AdjustUp(size()-1);
}
void pop()
{
swap(_con[0], _con[size() - 1]);
_con.pop_back();
AdjustDown(0);
}
int size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
T& top()
{
return _con.front();
}
};
void test()
{
//建立大堆
priority_queue<int> pq;
pq.push(1);
pq.push(5);
pq.push(2);
pq.push(4);
pq.push(3);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
//建立小堆
priority_queue<int,vector<int>,greater<int>> p;
p.push(1);
p.push(5);
p.push(2);
p.push(4);
p.push(3);
while (!p.empty())
{
cout << p.top() << " ";
p.pop();
}
cout << endl;
}
}