常德微网站开发,代理平台登录,惠州seo计费管理,河南住房与城乡建设厅网站文章目录 一、stack的介绍和使用1.1 stack的介绍1.2 stack的使用1.2.1 最小栈1.2.2 栈的压入、弹出序列1.2.3 逆波兰表达式求值1.2.4 用栈实现队列 二、queue的介绍和使用2.1 queue的介绍2.2 queue的使用2.2.1 二叉树的层序遍历 三、模拟实现3.1 stack模拟实现3.2 queue模拟实现… 文章目录 一、stack的介绍和使用1.1 stack的介绍1.2 stack的使用1.2.1 最小栈1.2.2 栈的压入、弹出序列1.2.3 逆波兰表达式求值1.2.4 用栈实现队列 二、queue的介绍和使用2.1 queue的介绍2.2 queue的使用2.2.1 二叉树的层序遍历 三、模拟实现3.1 stack模拟实现3.2 queue模拟实现 四、容器适配器4.1 什么是适配器4.2 STL标准库中stack和queue的底层结构4.3 deque的简单介绍4.3.1 deque的原理介绍4.3.2 deque的缺陷 4.4 为什么选择deque作为stack和queue的底层默认容器 五、结语 一、stack的介绍和使用
1.1 stack的介绍 stack 是一种容器适配器专门用在具有后进先出的上下文环境中。只能从容器的一端进行元素的插入与提取操作。 stack 是作为容器适配器被实现的容器适配器即是对特定类封装作为其底层的容器并提供一组特定的成员函数来访问其元素使得元素在特定容器的尾部栈顶被压入和弹出。 stack 的底层容器可以使任何标准的容器类模板或者一些其它特定的容器类这些容器类应该支持以下操作 empty判空操作 back获取尾部元素操作 push_back尾部插入元素操作 pop_back尾部删除元素操作 标准容器 vector、deque、list 均符合这些需求默认情况下如果没有为 stack 指定特定的底层容器默认情况下使用 deque。 1.2 stack的使用
函数说明接口说明stack()构造空的栈empty()检测栈 stack 是否为空size()返回 stack 中元素的个数top()返回栈顶元素的引用push()将元素 val 压入 stack 中pop()将 stack 中尾部的元素弹出
1.2.1 最小栈 本题的思路是用两个栈来实现其中一个栈 _st 用来正常存储数据另一个栈 _minst 用来存储最小的数据。具体实现就是在往 _st 中插入数据的时候进行判断如果当前插入的数据 val 小于等于 _minst 栈顶的数据那就将 val 也插入到 _minst 这个栈中。否则直将数据插入 _st 中。在 pop 数据的时候先取 _st 的栈顶元素和 _minst 的栈顶元素进行比较如果二者相等那就同时 pop _st 和 _minst 的栈顶元素否则就值 pop _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()){_minst.pop();}_st.pop();}int top() {return _st.top();}int getMin() {return _minst.top();}
private:stackint _st;stackint _minst;
};1.2.2 栈的压入、弹出序列 本题的解题思路是用一个栈来模拟。即先定义一个栈 st 然后给栈中入一个数据接着取栈顶的数据和出栈序列 popV 当前位置元素进行比较进行比较如果不相等则继续从入栈序列 pushV 中拿数据往栈 st 中入如果相等就出栈。这里需要注意有可能需要连续多次出栈。直到最终将入栈序列 pushV 中的数据全入栈最后判断栈 st 是否为空如果为空就说明该出栈序列正确。如果不空就说明该出栈序列有问题。
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param pushV int整型vector * param popV int整型vector * return bool布尔型*/bool IsPopOrder(vectorint pushV, vectorint popV) {// write code herestackint st;size_t push_pos 0, pop_pos 0;while(push_pos pushV.size()){//先入一个元素st.push(pushV[push_pos]);if(st.top() ! popV[pop_pos]){//不匹配继续入数据continue;}while(!st.empty() st.top() popV[pop_pos]){//匹配出数据st.pop();pop_pos;}}return st.empty();}
};代码优化我们可以发现上面代码中不匹配逻辑里面其实啥也没干因此我们可以把这段代码给删掉上面加上是为了使逻辑更加清晰。
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param pushV int整型vector * param popV int整型vector * return bool布尔型*/bool IsPopOrder(vectorint pushV, vectorint popV) {// write code herestackint st;size_t push_pos 0, pop_pos 0;while(push_pos pushV.size()){//先入一个元素st.push(pushV[push_pos]);while(!st.empty() st.top() popV[pop_pos]){//匹配出数据st.pop();pop_pos;}}return st.empty();}
};1.2.3 逆波兰表达式求值 逆波兰表达式也被叫做后缀表达式。什么是后缀表达式呢先来了解一下中缀表达式中缀表达式就是我们平时最常见的例如 2 3 ∗ 1 23*1 23∗1就是一个典型的中缀表达式。将前面的中缀表达式变成后缀表达式得到2 1 3 * 这就是一个后缀表达式后缀表达式相较于中中缀表达式操作数顺序不变操作符按优先级重排。这道题目就是要求我们对后缀表达式进行求解。求解后缀表达式我们可以借助一个栈遇到操作数入栈遇到操作符从栈中出两个元素进行运算将运算结果继续入栈。最终栈顶的元素就是整个逆波兰表达式的结果。
class Solution {
public:int evalRPN(vectorstring tokens) {stackint st;size_t pos 0;while(pos tokens.size()){if(tokens[pos] ! tokens[pos] ! - tokens[pos] ! * tokens[pos] ! /){//如果是数字就入栈int num stoi(tokens[pos]);st.push(num);}else{//不是数字就从栈中取两个元素出来int val1 st.top();st.pop();int val2 st.top();st.pop();int ret 0;if(tokens[pos] ){ret val2 val1;}else if(tokens[pos] -){ret val2 - val1;}else if(tokens[pos] *){ret val2 * val1;}else if(tokens[pos] /){ret val2 / val1;}//将计算结果继续入栈st.push(ret);}pos;}return st.top();}
};注意在写上面这段代码的时候有下面几点需要特别注意首先这是一个 string 数组会涉及到 string 转 int 。其次需要注意在从栈中取数的时候第一次取出的是右操作数第二次取出的是左操作数因此 val2 应该做左操作数val1 应该做右操作数尤其是减法运算和除法运算这两个操作数的顺序必须得到保证。
补充这里补充一个小知识点如何将中缀表达式转换成后缀表达式。主要过程分为以下几步 遇到操作数就输出这里的输出是将其存储到某种容器里。 遇到操作符根据优先级的顺序分为以下两种情况 栈为空或当前操作符比栈顶的优先级高继续入栈。 栈不为空且当前操作符比栈顶的优先级低或者相等则输出栈顶操作符继续执行第二步。 中缀表达式结束后依次出栈里面的操作符。
小Tips当前操作符能否计算取决于后一个操作符的优先级是否高于自己所以每当我们遇到一个操作符的时候先不着急将它入栈先和栈顶的操作符进行优先级比较如果当前操作符的优先级比栈顶操作符的优先级低或者相等我们就可以取出栈顶这个操作符进行运算。如果遇到括号可以走一个递归。其次就是需要想办法确定符号的优先级。
1.2.4 用栈实现队列 将一个栈当做输入栈用于压入 push 传入的数据另一个栈当做输出栈用于 pop 和 peek 操作。每次 pop 或 peek 时若输出栈为空则将输入栈的全部数据依次弹并压入输出栈这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。
class MyQueue {
public:MyQueue() {}void push(int x) {input_st.push(x);}int pop() {if(output_st.empty()){while(!input_st.empty()){output_st.push(input_st.top());input_st.pop();} }int ret output_st.top();output_st.pop();return ret;}int peek() {if(output_st.empty()){while(!input_st.empty()){output_st.push(input_st.top());input_st.pop();}}return output_st.top();}bool empty() {return input_st.empty() output_st.empty();}
private:stackint input_st;stackint output_st;
};二、queue的介绍和使用
2.1 queue的介绍 队列是一种容器适配器专门用于在FIFO上下文中执行先进先出操作其中从容器的一端插入元素另一端提取元素。 队列作为容器适配器实现容器适配器即将特定的容器类封装最为其底层容器queue 提供一组特定的成员函数来访问其元素。元素从队尾入队列从对头出队列。 底层容器可以是标准容器模板之一也可以是其他专门设计的容器类。该底层容器应至少支持以下操作 empty检查队列是否为空 size返回队列中有效元素的个数 front返回对头元素的引用 back返回队尾元素的引用 push_back在队列尾部入队列 pop_front在队列头部出队列 标准容器类 deque 和 list 满足了这些要求。默认情况下如果没有为 queue 实例化指定容器类则使用标准容器 deque。 2.2 queue的使用
函数声明接口说明queue()构造空队列empty()检测队列是否为空是返回 true否则返回 falsesize()返回队列中有效元素个数front()返回队头元素的引用back()返回队尾元素的引用push()在队尾将元素 val 入队列pop()将队头元素出队列
2.2.1 二叉树的层序遍历 二叉树的层序遍历可以借助队列来实现从根节点开始先让父节点入队列在出队尾节点的同时将该节点的左孩子和右孩子依次入队列。直到队列为空从队列中出出来的结果就是层序遍历的结果。这道题目需要将同一层的所有节点都存入一个一维数组再将这些一维数组组合成一个二维数组返回。我们前面的这种做法会导致队列中出现两层节点混在意的情况因此我们可以定义一个变量 levelSize 来记录每一层的节点数。具体代码如下
class Solution
{
public:vectorvectorint levelOrder(TreeNode* root) {vectorvectorint retV;queueTreeNode* qu;int levelSize 0;qu.push(root);while(!qu.empty()){vectorint tmp;levelSize qu.size();while(levelSize ! 0){TreeNode* top qu.front();if(top ! nullptr){tmp.push_back(top-val);qu.push(top-left);qu.push(top-right);} qu.pop();levelSize--;}if(!tmp.empty()){retV.push_back(tmp);}}return retV;}
};三、模拟实现
3.1 stack模拟实现
templateclass T, class Continer vectorTclass stack{public:stack(){}void push(const T val){_con.push_back(val);}void pop(){_con.pop_back();}T top(){return _con.back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Continer _con;};小Tipsstack 可以使用 vector 或者 list 来实现效率相当。插入数据就相当于尾插删除栈顶元素就相当于尾删。
3.2 queue模拟实现
templateclass T, class Continer std::listT
class queue
{
public:queue(){}void push(const T val){_con.push_back(val);}void pop(){_con.pop_front();//这里不再支持vector}T front(){return _con.front();}T back(){return _con.back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}
private:Continer _con;
};小Tips栈不能借助 vector 来实现因为出队列相当于删除 vector 中的第一个元素而对 vector 头删会涉及挪动数据效率相较于 list 会有所下降。
四、容器适配器
4.1 什么是适配器
适配器是一种设计模式设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结该种模式是将一个类的接口转换成客户希望的另外一个接口。
4.2 STL标准库中stack和queue的底层结构
虽然 stack 和 queue 中也可以存放元素但在 STL 中并没有将其划分在容器行列而是将其称为容器适配器这是因为 stack 和 queue 只是对其他容器的接口进行了包装STL 中 stack 和 queue 默认使用 deque。
4.3 deque的简单介绍
4.3.1 deque的原理介绍
deque双端队列是一种双开口的“连续”空间的数据结构双开口的含义是可以在头尾两端进行插入和删除操作且时间复杂度为O(1)与 vector 比较头插效率高不需要搬移元素与 list 比较空间利用率比较高。 deque并不是真正连续的空间而是由一段段连续的小空间拼接而成的实际 deque 类似于一个动态的二维数组其底层结构如下图所示 双端队列底层是一段假象的连续空间实际是分段连续的为了维护其“整体连续”以及随机访问的假象落在了 deque 的迭代器身上因此 deque 的迭代器设计的就比较复杂如下图所示
4.3.2 deque的缺陷 与 vector 比较deque 的优势是头部插入和删除时不需要搬移元素效率特别高而且在扩容时也不需要搬移大量的元素因此其效率是比 vector 高的。 与 list 比较其底层空间是连续的空间利用率比较高不需要存储额外字段。 但是deque 有一个致命缺陷不适合遍历因为在遍历时deque 的迭代器要频繁的去检测其是否移动到某段小空间的边界导致效率低下而序列式场景中可能需要经常遍历因此在实际中需要线性结构式大多数情况下优先考虑 vector 和 listdeque 的应用并不多而目前能看到的一个应用场景就是STL 用其作为 stack 和 queue 的底层数据结构。
4.4 为什么选择deque作为stack和queue的底层默认容器
stack 是一种后进先出的特殊线性数据结构因此只要是具有 push_back() 和 pop_back() 操作的线性结构都可以作为 stack 的底层容器比如 vector 和 list 都可以queue 是先进先出的特殊线性数据结构只要具有 push_back() 和 pop_front() 操作的线性结构都可以作为 queue de 底层容器比如 list。但是 STL 中对 stack 和 queue 默认选择 deque 作为其底层容器主要是因为 stack 和 queue 不需要遍历因此 stack 和 queue 没有迭代器只需要在固定的一端或者两端进行操作。 在 stack 中元素增长时deque 比 vector 的效率高扩容时不需要搬移大量数据queue 中的元素增长时deque 不仅效率高而且内存利用率高。
五、结语
今天的分享到这里就结束啦如果觉得文章还不错的话可以三连支持一下春人的主页还有很多有趣的文章欢迎小伙伴们前去点评您的支持就是春人前进的动力
