摘要:stack OJ:最小栈、栈的弹出压入序列;queue OJ:二叉树的层序遍历(仅思路,带图解)、逆波兰表达式求值;deque,模拟实现 stack 和 queue
经过对 string、vector、list 的学习,stack 和 queue 上手起来就很快了,因此不再赘述,在使用上有疑问请查看文档。本文将会通过一些OJ题来进一步熟练 stack 和 queue.
1. stack/queue 与 vector/list
- stack/queue——容器适配器(不自己管理数据)
- vector/list——容器(自己直接管理数据)
- stack/queue 与 vector/list 的成员函数的区别:
stack/queue 没有 iterator,因为 stack 是先进后出,queue 是先进先出,不能随机遍历。
2. stack OJ
1)最小栈
思路
我们很容易可以想到用一个变量来存储栈中最小的数据,然而,当pop掉的数据正好是最小数时,那么这个pop操作之后的栈中的最小数就不得而知了,因此,我们不仅要记录栈中数据的当前最小数,而是要记录历史最小数。这里,我们通过使用双栈来实现这个思路。
上述思路图解示例:
代码示例
class MinStack {
public:
void push(int val) {
st.push(val);
if(min_st.empty() || val <= min_st.top())
min_st.push(val);
}
void pop() {
if(st.top() == min_st.top())
{
st.pop();
min_st.pop();
}
else
st.pop();
}
int top() {
return st.top();
}
int getMin() {
return min_st.top();
}
private:
stack<int> st;
stack<int> min_st;
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(val);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/
2)栈的压入、弹出序列
JZ31 栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com)
思路
按给定的入栈顺序模拟数据入栈,同时按给定的出栈顺序模拟数据出栈,最终栈中数据全部出完即为该出栈顺序合法。
注意:如下图,如果先判断再入栈这个过程会比较复杂,这里建议先入栈再判断。
代码示例
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param pushV int整型vector
* @param popV int整型vector
* @return bool布尔型
*/
bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
// write code here
stack<int> st;
size_t size = pushV.size();
for (size_t pushi = 0, popi = 0; pushi < size; ++pushi)
{
st.push(pushV[pushi]);
while (!st.empty() && st.top() == popV[popi])//要先判断是否为空才可以取top
{
st.pop();
++popi;
}
}
return st.empty();
}
};
3. queue OJ
1)二叉树的层序遍历(仅思路,带图解)
- 思路一:双队列,队列_1 用于遍历二叉树,队列_2 用于记录节点对应的层数。 如图,依次遍历,把遍历结果存储在队列中。当我们开始遍历,遍历到‘3’,记录此时层数为1;接着遍历‘3’的child节点,插入‘9’‘7’到队列中,记录此时的层数,即为上一层+1;如此循环。直到遍历完二叉树。
- 思路二:双队列,队列_1 用于存储 parent 节点,队列_2 用于存储 child 节点。
- 思路三:一个队列+一个变量,队列用于遍历二叉树,变量用于记录当前遍历到多少层。
2)逆波兰表达式求值
逆波兰表达式就是后缀表达式。逆波兰表达式求值就是后缀表达式的计算。
后缀表达式的计算
- 中缀表达式:1 + 2 * 3
- 后缀表达式:1 2 3 * + (ps.后缀表达式是没有括号的,因为括号的作用是提高操作符的优先级,而后缀表达式的操作符顺序已经表现了优先级)
思路:遍历后缀表达式,遇到操作数入栈,遇到操作符就取栈顶两元素运算,运算结果再入栈,如此循环,直到遍历完后缀表达式。图例如下。
中缀表达式转后缀表达式(仅思路)
- 思路:遍历中缀表达式,遇到操作数输出;遇到操作符,如果 stack 为空,那么 push 操作符入栈,如果 stack 不为空,那么比较栈顶元素与该操作符的优先级,如果该操作符优先级更高,那么 push 操作符入栈,如果栈顶元素优先级更高或两者优先级相等,就 pop 栈顶元素。(ps.遇到括号处理成递归子问题)。
代码示例
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> st;
for(auto str:tokens)
{
if(str == "+"
||str == "-"
||str == "*"
||str == "/")
{
int right = st.top();
st.pop();
int left = st.top();
st.pop();
switch(str[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(str));
}
}
return st.top();
}
};
4. 模拟实现 stack
库里的实现 → std::stack
template <class T, class Container = deque<T> > class stack;
1)deque(简单了解)
deque 是一个结合了vector 和 list 功能的容器,但也同时结合了 vector 和 list 的双重优点和缺点。(优点多而优势不高,缺点多而缺陷不深)
deque(双端队列):是一种双开口的"连续"空间的数据结构,双开口的含义是:可以在头尾两端进行插入和删除操作,且时间复杂度为O(1),与 vector 比较,头插效率高,不需要搬移元素;与 list 比较,空间利用率比较高。
deque 和 vector 的效率比较(这个操作类似于 list 和 vector 的效率比较)
1.vector sort 的效率约为 deque 的 2倍;
2.通过把 deque 的数据拷贝到 vector 对其排序,都比直接用 deque 排序要快。(ps.通过这个操作我们可以侧面了解到数据拷贝的代价并不高)
sum.实际中 deque 并不常用,综合性比较强,但是优势又并不突出。
为什么选择deque作为stack和queue的底层默认容器:
stack是一种后进先出的特殊线性数据结构,因此只要具有 push_back() 和 pop_back() 操作的线性结构,都可 以作为stack的底层容器,比如vector 和 list 都可以;queue是 先进先出 的特殊线性数据结构,只要具有 push_back 和 pop_front 操作的线性结构,都可以作为 queue 的底层容器,比如list。但是STL中对stack和 queue 默认选择 deque 作为其底层容器,主要是因为:
- stack 和 queue 不需要遍历(因此 stack 和 queue 没有迭代器),只需要在固定的一端或者两端进行操作。
- 在 stack 中元素增长时,deque 比 vector 的效率高(扩容时不需要搬移大量数据);queue 中的元素增长 时,deque不仅效率高,而且内存使用率高。 结合了 deque 的优点,而完美的避开了其缺陷。
2)模拟实现
思路:本质就是复用别的容器的函数接口。注意后进先出的原则。
代码示例
namespace Btl
{
template<class T, class Con = deque<T>>
class stack
{
public:
void push(const T& x)
{
_c.push_back(x);
}
void pop()
{
_c.pop_back();
}
T& top()
{
return _c.back();
}
const T& top()const
{
return _c.back();
}
size_t size()const
{
return _c.size();
}
bool empty()const
{
return _c.empty();
}
private:
Con _c;
};
};
5. 模拟实现 queue
同 stack,注意是先进先出的原则。
namespace Btl
{
template<class T, class Con = deque<T>>
class queue
{
public:
void push(const T& x)
{
_c.push_back(x);
}
void pop()
{
_c.pop_front();
}
T& back()
{
return _c.back();
}
const T& back()const
{
return _c.back();
}
T& front()
{
return _c.front();
}
const T& front()const
{
return _c.front();
}
size_t size()const
{
return _c.size();
}
bool empty()const
{
return _c.empty();
}
private:
Con _c;
};
};
END