创业给别人做网站怎么样,网上购物商城首页,WORDPRESS添加前台会员注册,汕头响应式网站教程一、stack的简单介绍和使用
1.1 stack的介绍
1.stack是一种容器适配器#xff0c;专门用在具有先进后出#xff0c;后进先出操作的上下文环境中#xff0c;其删除只能从容器的一端进行元素的插入和弹出操作。
2.stack是作为容器适配器被实现的#xff0c;容器适配器即是…一、stack的简单介绍和使用
1.1 stack的介绍
1.stack是一种容器适配器专门用在具有先进后出后进先出操作的上下文环境中其删除只能从容器的一端进行元素的插入和弹出操作。
2.stack是作为容器适配器被实现的容器适配器即是对特定类封装作为其底层的容器并提供一组特定的成员函数来访问其元素将特定类作为其底层的元素特定容器尾部即栈顶被压入和弹出。
3.stack的底层容器可以是任何标准的容器类模板或者一些其他待定的容器类这些容器类需要支持以下的一些操作
empty 判空操作back获取尾部元素push_back尾部插入元素pop_back:尾部删除元素 4.标准容器vector、deque、list等均符合这些需求默认情况下没有为stack指定特定的底层容器时默认情况下就使用deque。
1.2 stack的使用
下面是stack的接口函数及其功能介绍
函数说明接口说明stack()构造空的栈empty()检测stack是否为空size()返回stack中的元素的个数top()返回栈顶元素的作用push()将元素val压入到stack中pop() 将stack中栈顶元素弹出 下面我们来看下stack在一些问题中的使用
我们先来看几道算法设计题
leetcode155,最小栈 对于这个题目我们可以使用两个stack来实现这个最小栈首先给一个主体栈s和一个辅助栈min_s
里面存储最小值当我们的元素入栈时如果辅助栈是空的或者val的值小于min_s的栈顶元素就将val入栈。出栈时如果我们主体栈的栈顶元素和我们的辅助栈的栈顶元素相等的话辅助栈的栈顶元素也出栈。取栈顶元素top()就直接返回s.top()即可取最小值时就直接返回min_s.top()即可。
下面是参考代码
class MinStack {
public:MinStack() {}void push(int val) {//将val压入主体栈中s.push(val);//如果最小栈为空或者val小于最小栈的栈顶元素就将val也压入进最小栈中if(min_s.empty() || val min_s.top()){min_s.push(val);}}void pop() {//出栈时如果主体栈的栈顶元素和最小栈的栈顶元素相同时最小栈也将栈顶元素弹出if(s.top() min_s.top()){min_s.pop();}s.pop();}//返回主体栈的top即可int top() {return s.top();}//返回最小栈的栈顶元素即可int getMin() {return min_s.top();}
private://定义一个主体栈和一个存放最小值的栈stackint s;stackint min_s;
};/*** 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();*/
牛客网JZ31,栈的压入弹出序列 对于这一题就是一个进栈出栈的一个过程模拟我们先定义出一个栈然后定义一个维护出栈序列的下标最后我们将进栈序列中的元素进栈如果栈不为空并且栈顶元素和出栈元素相同就将栈顶元素出栈然后将指向出栈序列的popi向后走一步。出循环后如果栈为空就是匹配返回true如果栈不为空就返回false。
下面是参考代码
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param pushV int整型vector * param popV int整型vector * return bool布尔型*/bool IsPopOrder(vectorint pushV, vectorint popV) {// write code here//定义一个栈模拟进栈过程stackint s;//定义一个出栈下标维护出栈序列int popi 0;//进栈for(auto e : pushV){s.push(e);//如果栈不为空并且出栈队列对应值等于栈顶元素就将栈顶元素弹出然后将出栈序列向后走一步while(!s.empty() popV[popi] s.top()){s.pop();popi;}}//如果栈为空则匹配否则不匹配return s.empty();}
};
通过这两到例题我们应该也就了解了stack的使用下面我们来看下queue的用法。
二、queue的简单介绍和使用
2.1 queue的介绍
1.queue也就是队列也是一种容器适配器专门用于先进先出的上下文操作中从容器一端进数据另一端出数据。
2.queue作为容器适配器实现容器适配器就是将特定的容器类封装作为其底层容器类queue提供一组特定的成员函数来访问其元素元素从队尾入队列从队头出队列。
3.底层容器可以是标准容器类模版之一也可以是其他专门设计的容器类。queue的底层容器至少需要支持一下操作
empty判断队列是否为空size返回队列中有效元素中的个数front返回队头元素的引用back返回队尾元素的引用push_back在队列尾部入队列pop_back:在队列头部出队列
4. 标准容器类deque和list符合这些要求默认情况下如果没有为queue实例化指定容器类则默认使用deque。
2.2 queue的使用
下面是queue的接口函数以及它的接口功能
接口函数接口说明queue()构造空的队列empty()检测队列是否为空为空就放回true否则返回falsesize()返回队列中的有效元素个数front返回队头元素的引用back()返回队尾元素的引用push()将元素进队列pop()将元素出队列 下面我们通过一个题目来了解一下queue的使用
leetcode102,二叉树的层序遍历 对于这一题我们可以借助队列queue来解决我们先定义一个二维数组来存放返回值然后定义一个queue辅助遍历定义一个level_size来存放没层的节点然后先将头结点入队如果队列不为空就进行外层循环内层循环负责将遍历到的值放进管理这一层节点的数组v中然后再将下一层的节点带入出内层循环后更新level_size和ret数组即将level_size更新为目前队列中的元素个数将该层的节点数组v尾插到ret数组中最后返回ret数组即可。
参考代码如下
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),* right(right) {}* };*/
class Solution {
public:vectorvectorint levelOrder(TreeNode* root) {// 定义一个二维数组作为返回数组vectorvectorint ret;// 如果二叉树是空树就直接返回空数组if (root nullptr) {return ret;}// 定义一个辅助队列queueTreeNode* q;// 将root入栈q.push(root);// 记录每层的节点数int level_size 1;//队列不为空就进行循环while (!q.empty()) {//定义一个数组记录每层的节点vectorint v;//遍历这一层的节点并将下一层的节点带入while (level_size--) {TreeNode* front q.front();v.push_back(front-val);q.pop();if (front-left) {q.push(front-left);}if (front-right) {q.push(front-right);}}//更新层节点个数level_size q.size();//将这一层的节点放到返回数组中去ret.push_back(v);}//出循环后返回最终结果return ret;}
}; 关于stack和queue的使用这篇博客就讲到这里大家可以自行通过一些算法题去练习一下也建议能够对博客里的例题能够理解后去自己实现一下。
