【C++】开始使用stack 与 queue

这篇具有很好参考价值的文章主要介绍了【C++】开始使用stack 与 queue。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【C++】开始使用stack 与 queue,从零开始的C++生活,c++,java,开发语言,学习,c语言,广度优先

送给大家一句话:
忍受现实给予我们的苦难和幸福,无聊和平庸。 – 余华 《活着》


1 前言

在之前的学习中,我们已经对 STL 模板中的 string list vector 等容器进行了详细的探讨,从而获得了对这些容器操作的清晰理解。基于这些知识,现在转向学习 stack(栈) 和 queue(队列)就显得相对简单了。然而,在有效使用这两种容器之前,我们还需要对它们的工作原理和使用场景有一个系统的了解。这样,我们才能更加准确地应用这些数据结构来解决实际问题。

2 stack与queue

2.1 stack 栈

stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入与提取操作。类似与向箱子里放入取出物品,只能一端进行操作

stack是作为容器适配器( 一种设计模式 )被实现的,容器适配器即是对特定类封装作为其底层的容器,并提供一组特定
的成员函数来访问其元素,将特定类作为其底层的,元素特定容器的尾部(即栈顶)被压入和弹出。

stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类,这些容器类应该支持以下
操作:

  • empty:判空操作
  • back:获取尾部元素操作
  • push_back:尾部插入元素操作
  • pop_back:尾部删除元素操作

标准容器vector、deque、list均符合这些需求,默认情况下,如果没有为stack指定特定的底层容器,默认情况下使用deque

2.2 queue 队列

队列是一种容器适配器,专门用于在FIFO上下文(先进先出)中操作,其中从容器一端插入元素,另一端
提取元素。类似与排队打饭,只能从尾端进入,从头离开。

队列作为容器适配器实现,容器适配器即将特定容器类封装作为其底层容器类,queue提供一组特定的
成员函数来访问其元素。元素从队尾入队列,从队头出队列。

底层容器可以是标准容器类模板之一,也可以是其他专门设计的容器类。该底层容器应至少支持以下操
作:

  • empty:检测队列是否为空
  • size:返回队列中有效元素的个数
  • front:返回队头元素的引用
  • back:返回队尾元素的引用
  • push_back:在队列尾部入队列
  • pop_front:在队列头部出队列

标准容器类deque和list满足了这些要求。默认情况下,如果没有为queue实例化指定容器类,则使用标准容器deque

2.3 使用手册

stack手册 和 queue手册
通过手册我们可以发现基本接口是一样的:

stack栈:

函数说明 接口说明
empty() 检测stack是否为空
size() 返回stack中元素的个数
top() 返回栈顶元素的引用
push() 将元素val压入stack中
pop() 将stack中尾部的元素弹出

queue 队列:

函数声明 接口说明
empty() 检测队列是否为空,是返回true,否则返回false
size() 返回队列中有效元素的个数
front( ) 返回队头元素的引用
back() 返回队尾元素的引用
push() 在队尾将元素val入队列
pop() 将队头元素出队列

3 开始使用

接下来我们在解题中体会stack与queue的使用方法

Leetcode 155.最小栈

链接:最小栈
题目描述
【C++】开始使用stack 与 queue,从零开始的C++生活,c++,java,开发语言,学习,c语言,广度优先
这道题看起来很简单奥,我们需要模拟一个特殊的栈:可以获取到栈中的最小元素。
我们解决的办法也很直接了当,我们建立两个栈_st 和_minst,一个用来记录栈中的所以元素,一个来记录当前最小值。这个记录当前最小值只需要在插入元素时判断插入的元素是否小于当前栈中的最小值(也就是_minst中的top()元素)
也就是我们需要对插入与删除进行特殊处理,其余部分与普通的栈区别不大。
PS: 不敢想象如果使用C语言搓轮子会是多么费劲!!!

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;
};

牛客 JZ31 栈的弹出压入序列

上链接!!!栈的弹出压入序列
题目描述
【C++】开始使用stack 与 queue,从零开始的C++生活,c++,java,开发语言,学习,c语言,广度优先
这个题目比较好理解,我们需要通过一个插入序列,来判断弹出序列可不可以通过插入序列来获取。
思路也比较简单,我们只需模拟弹出过程即可:

  1. 首先创建一个栈
  2. 依照插入序列来插入元素
  3. 检查当前栈顶元素是否等于弹出序列的首元素(一样说明该弹出了)
  4. 重复 3 操作直到不一致为止,然后进行2 - 3 操作
class Solution {
public:
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        // 使用两个下表来进行两个序列的读取
        int pushi = 0, popi = 0;
        stack<int> st ;
		//所有元素全部插完为止
        while(pushi < pushV.size())
        {
        	//插入一个
            st.push(pushV[pushi]);
            //检查是否一致,一致就弹出
            while(!st.empty() && st.top() == popV[popi] )
            {
                popi++;
                st.pop();
            }
            pushi++;
            
        }
        //最后进行判断
        if(st.empty()) return true;
        else return false;
    }
};

Leetcode 150.逆波兰表达式求值

题目描述
【C++】开始使用stack 与 queue,从零开始的C++生活,c++,java,开发语言,学习,c语言,广度优先

我们先来认识一下逆波兰表达式:也被称为后缀表达式,是一种非常巧妙的数学表达式写法。在这种表达式中,运算符位于所有操作数的后面,这种布局使得表达式的计算不再需要括号来指示运算的优先级。逆波兰表达式的一个典型特点是其清晰的运算顺序——从左到右,这使得计算过程变得直观且易于通过计算机算法实现。

但为什么我们需要逆波兰表达式呢?主要是因为它极大地简化了计算机程序对表达式的处理。在传统的中缀表达式中,计算机需要处理复杂的优先级和括号,而逆波兰表达式通过其后缀形式自然地避免了这些复杂性。这不仅提高了计算效率,还减少了程序运行过程中的错误可能性。
因此,在很多需要快速且准确计算的领域,如编译器的设计和科学计算中,逆波兰表达式都发挥了不可替代的作用

而这道题我们需要模拟计算逆波兰表达式,我们就要先知道逆波兰表达式是如何计算的:
举个例子:
输入:tokens = [“2”,“1”,“+”,“3”,“*”]
输出:9
解释:该算式转化为常见的中缀算术表达式为:((2 + 1) * 3) = 9

这是如何做到的:
【C++】开始使用stack 与 queue,从零开始的C++生活,c++,java,开发语言,学习,c语言,广度优先
也就是:

  1. 依次读入数字 (压入栈中)
  2. 读到运算符就进行运算(取出栈前两个数字来进行相应运算)
  3. 然后再储存运算结果(压入栈中)
  4. 依次重复 1 - 3 操作
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<string> st;
        int i = 0;
        while(i != tokens.size())
        {
            string tmp = tokens[i];
            //枚举运算符,反正运算符就那些
            if(tmp.size() == 1 && (tmp[0] == '*' || tmp[0] == '/' || tmp[0] == '-' || tmp[0] == '+'))
            {
                int n1 = stoi(st.top());
                st.pop();
                int n2 = stoi(st.top());
                st.pop();
                //直接枚举运算符
                switch(tmp[0])
                {
                	//注意数字顺序很重要!!!
                    case '*': n2 *= n1;
                        break;
                    case '/': n2 /= n1;
                        break;
                    case '+': n2 += n1;
                        break;
                    case '-': n2 -= n1;
                        break;
                    default : break;
                }
				//压入计算结果
                st.push(to_string(n2));
                i++;
            }
            else
            {
                st.push(tokens[i]);
                i++;
            }
        }
        return stoi(st.top());
    }
};

队列的相关习题大部分是子啊BFS中使用,这里就不在说明了文章来源地址https://www.toymoban.com/news/detail-856159.html

Thanks♪(・ω・)ノ谢谢阅读!!!

下一篇文章见!!!

到了这里,关于【C++】开始使用stack 与 queue的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • STL容器适配器 -- stack和queue(使用+实现)(C++)

    栈和队列数据结构+画图分析如果对栈和队列的结构不了解的,可以先看该链接的内容 使用stack时需要头文件 #includestack stack是一种容器适配器,用于具有 后进先出 (LIFO)的环境中。只能从容器的一端(栈顶),执行删除、插入和提取操作。 stack是作为容器适配器实现的,容器

    2024年02月14日
    浏览(62)
  • 【C++】栈和队列(stack and queue)语法使用及实现原理

         本篇文章会对C++中的容器stack和queue用法进行详解,也包含对优先队列(priority_queue)的讲解。同时会模拟实现stack、queue和priority_queue底层。希望本篇文章会对你有所帮助! 目录 一、stack 栈 1、1 什么是适配器 1、2 stack 语法讲解 1、3 stack 底层实现 1、4 deque 双端队列简单

    2024年02月15日
    浏览(36)
  • C++ 栈和队列(stack and queue)语法使用及底层实现原理

         本篇文章会对C++中的容器stack和queue用法进行详解,也包含对优先队列(priority_queue)的讲解。同时会模拟实现stack、queue和priority_queue底层。希望本篇文章会对你有所帮助! 目录 一、stack 栈 1、1 什么是适配器 1、2 stack 语法讲解 1、3 stack 底层实现 1、4 deque 双端队列简单

    2024年02月13日
    浏览(34)
  • stack 、 queue的语法使用及底层实现以及deque的介绍【C++】

    stack是一种容器适配器,具有后进先出,只能从容器的一端进行元素的插入与提取操作 队列是一种容器适配器,具有先进先出,只能从容器的一端插入元素,另一端提取元素 stack和queue在STL中并没有将其划分在容器的行列,而是称为容器适配器 因为stack和queue对其他容器的接口

    2024年02月12日
    浏览(43)
  • 【C++】STL之容器适配器——使用deque适配stack和queue

    个人主页:🍝在肯德基吃麻辣烫 分享一句喜欢的话:热烈的火焰,冰封在最沉默的火山深处。 本文章主要介绍容器适配器的功能,以及一个适配的场景。 容器适配器,按字面意思理解的话,就是用来对一个容器进行匹配的。在C++STL中,容器有:vector,list,deque,map,set等。

    2024年02月16日
    浏览(54)
  • 使用MASA Stack+.Net 从零开始搭建IoT平台 第五章 使用时序库存储上行数据

    @ 目录 前言 分析 实施步骤 时序库的安装 解决playload没有时间戳问题 代码编写 测试 总结 我们可以将设备上行数据存储到关系型数据库中,我们需要两张带有时间戳的表( 最新数据表 和 历史数据表 ), 历史数据表 存储所有设备上报的数据, 最新数据表 需要存储设备最新

    2024年02月11日
    浏览(41)
  • 【C++】STL中stack,queue容器适配器的模拟实现(使用deque容器)

    🌏博客主页: 主页 🔖系列专栏: C++ ❤️感谢大家点赞👍收藏⭐评论✍️ 😍期待与大家一起进步! 虽然stack和queue中也可以存放元素,但在STL中并没有将其划分在容器的行列,而是将其称为容器适配器,这是因为stack和队列只是对其他容器的接口进行了包装,STL中stack和

    2024年02月15日
    浏览(50)
  • 【C++】stack & queue

    适配器 是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结),该种模式是将一个类的接口转换成我们希望的另外一个接口。 虽然 stack 和 queue 中也可以存放元素,但在 STL 中并没有将其划分在容器的行列,而是将其称为 容器

    2024年02月07日
    浏览(37)
  • C++——Stack&&Queue

    目录 一Stack 1介绍 2接口  3模拟实现 4栈的oj题  二Queue 1介绍 2接口 3模拟实现 三容器适配器 1再谈栈和队列  四优先级队列 1接口 ​编辑 2仿函数 五dequeue的简单介绍  先来看看库中对栈的介绍: 1. stack是一种容器适配器,专门用在具有 后进先出 操作的上下文环境中,其删除

    2024年04月13日
    浏览(75)
  • 【C++ 】stack 和 queue

    stack 的介绍: 1. stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行 元素的插入与提取操作 2. stack是作为容器适配器被实现的,容器适配器即是对特定类封装作为其底层的容器,并提供一组特定的成员函数来访问其元素,将特定

    2024年04月15日
    浏览(28)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包