C++ stack使用、模拟实现、OJ题

目录

一、介绍

二、常用函数

三、模拟实现 

四、OJ练习题

1、最小栈

2、栈的压入、弹出序列

3、逆波兰表达式(后缀转中缀)

4、中缀转后缀思路

5、用栈实现队列

一、介绍

  1. stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。
  2. stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。
  3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：
    • empty：判空操作
    • back：获取尾部元素操作
    • push_back：尾部插入元素操作
    • pop_back：尾部删除元素操作
  4. 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque。

二、常用函数

  • stack()   构造空的栈
  • empty()  检测stack是否为空
  • size()      返回stack中元素的个数
  • top()       返回栈顶元素的引用
  • push()    将元素val压入stack中
  • pop()      将stack中尾部的元素弹出
int main() {
    stack<int> myStack; // 创建一个存储int类型的栈对象
    
    // 检测栈是否为空
    cout << "Is stack empty? " << (myStack.empty() ? "Yes" : "No") << endl; 

    myStack.push(10); // 压入元素10
    myStack.push(20); // 压入元素20
    myStack.push(30); // 压入元素30

    // 输出栈中元素的个数
    cout << "Stack size: " << myStack.size() << endl; 
    
    // 输出栈顶元素的值
    cout << "Top element: " << myStack.top() << endl;

    // 弹出栈顶元素
    myStack.pop(); 
    
    // 输出弹出后的栈顶元素的值
    cout << "Top element after pop: " << myStack.top() << endl; 

    return 0;
}

 

三、模拟实现 

template<class T, class Container = vector<T>>
class stack
{
public:
	void push(const T& x)
	{
		_con.push_back(x);
	}

	void pop()
	{
		_con.pop_back();
	}

	const T& top()
	{
		return _con.back();
	}

	size_t size()
	{
		return _con.size();
	}

	bool empty()
	{
		return _con.empty();
	}

private:
	Container _con;
};

这段代码实现了一个栈（stack）类模板，使用适配器模式（Adapter Pattern）来适配不同类型的容器（Container）作为底层实现。

适配器模式是一种结构型设计模式，用于将一个类的接口转换成客户端所期望的另一个接口。在这个例子中，stack类的接口被适配成了与Container类型兼容的接口。

  • 模板类stack有两个模板参数：T表示栈中元素的类型，Container表示底层容器的类型，默认为vector。这样，我们可以通过指定不同的容器类型来实现不同的底层实现。
  • stack类提供了一些常见的栈操作函数，包括push、pop、top、size和empty。这些函数在内部通过调用底层容器的相应函数来实现栈的功能。
  • 例如，push函数将元素添加到底层容器的末尾，pop函数从底层容器的末尾移除元素，top函数返回底层容器的末尾元素，size函数返回底层容器中元素的个数，empty函数检查底层容器是否为空。
  • 通过使用适配器模式，我们可以将不同类型的容器（如vector、list、deque等）适配成具有相同接口的栈类，从而实现了代码的复用和灵活性。

四、OJ练习题

1、最小栈

这个问题的关键在于如何在常数时间内检索到最小元素。为了实现这个目标，我们可以使用两个栈：一个栈 _st 用于正常的 push 和 pop 操作，另一个栈 _minst 用于存储当前栈中的最小元素。

class MinStack {
public:
    MinStack() {}

    void push(int val) {
        _st.push(val);
        if (_minst.empty() || val <= _minst.top())
        {
            _minst.push(val);
        }
    }

    void pop() {
        if (_minst.top() == _st.top()) {
            _minst.pop();
        }
        _st.pop();
    }

    int top() {
        return _st.top();
    }

    int getMin() {
        return _minst.top();
    }

private:
    stack<int> _st;
    stack<int> _minst;
};

详细步骤：

  1. 初始化：我们初始化两个空栈 _st 和 _minst。

  2. push 操作：当我们将一个元素 val 推入栈 _st 时，我们也需要检查它是否应该被推入栈 _minst。如果 _minst 为空，或者 val 小于等于 _minst 的栈顶元素，那么我们就将 val 推入 _minst。这样，_minst 的栈顶元素就始终是 _st 中的最小元素。

  3. pop 操作：当我们从 _st 中弹出一个元素时，我们需要检查它是否是 _minst 的栈顶元素。如果是，那么我们也需要从 _minst 中弹出它，因为这个元素已经不再 _st 中了，所以 _minst 的栈顶元素需要更新。

  4. top 操作：这个操作只需要返回 _st 的栈顶元素。

  5. getMin 操作：这个操作只需要返回 _minst 的栈顶元素，因为我们已经确保了 _minst 的栈顶元素始终是 _st 中的最小元素。

这个算法的关键在于，我们使用了一个额外的栈 _minst 来存储当前栈中的最小元素，这样我们就可以在常数时间内检索到最小元素。

2、栈的压入、弹出序列

这个问题的关键在于理解栈的特性，即后进先出（LIFO）。我们可以通过一个辅助栈来模拟压入和弹出的过程，以此来判断给定的弹出序列是否可能。

class Solution {
  public:
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
        stack<int> st;
        int pushi = 0, popi = 0;
        while (pushi < pushV.size()) {
            st.push(pushV[pushi++]);
            while (!st.empty() && st.top() == popV[popi]) {
                st.pop();
                popi++;
            }
        }
        return popi==popV.size();
    }
};

  • 初始化一个空栈，用于模拟压入和弹出的过程。同时，初始化两个指针，pushi 和 popi，分别指向 pushV 和 popV 的开始位置。

  • 当 pushi 小于 pushV 的大小时，执行以下操作：

    • 将 pushV[pushi] 压入栈中，并将 pushi 加一。
    • 检查栈顶元素是否等于 popV[popi]。如果相等，说明当前栈顶元素是下一个要弹出的元素，因此我们将其从栈中弹出，并将 popi 加一。我们需要不断进行这个检查，直到栈为空或者栈顶元素不等于 popV[popi]。

  • 最后，如果 popi 等于 popV 的大小，说明 popV 中的所有元素都正确地被弹出了栈，因此返回 true。否则，返回 false。

这个算法的关键在于，它利用了栈的特性来模拟了压入和弹出的过程。当栈顶元素等于 popV[popi] 时，我们知道这个元素应该被弹出，因为在给定的弹出序列中，它是下一个要弹出的元素。

3、逆波兰表达式(后缀转中缀)

思路：

  1. 遇到操作数入栈。
  2. 遇到操作符，取栈顶的两个操作数进行运算，运算结果重新入栈。
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、中缀转后缀思路

1、操作数输出

2、操作符

        (1)栈为空进栈

        (2)栈不为空，跟栈顶的操作符比较。

                a、比栈顶操作符优先级高，进栈。

                b、比栈顶优先级低或相等，出栈顶操作符输出。

带括号的中缀转后缀 

1 + 2*(4 - 5) + 6 /7  >>  1245-*+67/+ 

  1. ( ) 优先级最低
  2. ( 不比较直接入栈
  3. ) 参与比较，直接遇到 (

5、用栈实现队列

 

 

class MyQueue {
public:
    MyQueue() {}

    void push_to_pop(){
        if(stpop.empty()){
            while (!stpush.empty()) {
                stpop.push(stpush.top());
                stpush.pop();
            }
        }
    }

    void push(int x) { stpush.push(x); }

    int pop() {
        push_to_pop();
        int x=stpop.top();
        stpop.pop();
        return x;
    }

    int peek() {
        push_to_pop();
        return stpop.top();
    }

    bool empty() { return stpush.empty() && stpop.empty(); }

private:
    stack<int> stpush;
    stack<int> stpop;
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */
  1. 首先定义了一个名为MyQueue的类，表示队列。
  2. 类中有两个私有成员变量stpush和stpop，它们分别表示用于入队和出队操作的两个栈。
  3. MyQueue类中定义了一个默认构造函数MyQueue()，用于创建一个空的队列。
  4. push_to_pop()函数用于将stpush栈中的元素转移到stpop栈中。如果stpop栈为空，则将stpush栈中的元素逐个弹出并压入stpop栈中，以实现队列的先进先出顺序。
  5. push(int x)函数用于将元素x入队，即将元素压入stpush栈中。
  6. pop()函数用于出队操作，即从队列中移除并返回队头元素。在执行出队操作之前，首先调用push_to_pop()函数，确保stpop栈中有元素。然后从stpop栈中弹出栈顶元素，并返回该元素。
  7. peek()函数用于获取队头元素，但不对队列进行修改。同样，在执行获取队头元素操作之前，先调用push_to_pop()函数，确保stpop栈中有元素。然后返回stpop栈的栈顶元素。
  8. empty()函数用于判断队列是否为空。当stpush和stpop两个栈都为空时，队列为空，返回true；否则返回false。

这样，通过使用两个栈，我们可以实现队列的基本功能，包括入队、出队、获取队头元素和判断队列是否为空。

在代码的最后，给出了使用MyQueue类的示例代码。首先创建一个MyQueue对象obj，然后可以通过调用obj的成员函数来进行入队、出队、获取队头元素和判断队列是否为空的操作。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/286526.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

二叉树的前序遍历 、二叉树的最大深度、平衡二叉树、二叉树遍历【LeetCode刷题日志】

二叉树的前序遍历 、二叉树的最大深度、平衡二叉树、二叉树遍历【LeetCode刷题日志】

目录 一、二叉树的前序遍历 方法一&#xff1a;全局变量记录节点个数 方法二&#xff1a;传址调用记录节点个数 二、二叉树的最大深度 三、平衡二叉树 四、二叉树遍历 一、二叉树的前序遍历 方法一&#xff1a;全局变量记录节点个数 计算树的节点数: 函数TreeSize用于…
阅读更多...
[情商-5]：用IT直男擅长的流程图阐述高情商聊天过程与直男聊天过程

[情商-5]：用IT直男擅长的流程图阐述高情商聊天过程与直男聊天过程

目录 一、目标与主要思想的差别 二、高情商聊天与直男聊天的流程图 1. 发起谈话主题Topic 2. 分析谈话的主题和内容 3. 确定谈话目的&#xff1a;解决问题还是情绪交流 4. 倾听&#xff1a;站在自己的角度倾听、捕获、理解对方的情绪状态与情绪诉求 5. 同理心&#xff1…
阅读更多...
探索 CodeWave低代码技术的魅力与应用

探索 CodeWave低代码技术的魅力与应用

目录 前言1 低代码平台2 CodeWave简介3 CodeWave 的独特之处3.1 高保真还原交互视觉需求3.2 擅长复杂应用开发3.3 支持应用导出&独立部署3.4 金融级安全要求3.5 可集成性高3.6 可拓展性强 4 平台架构和核心功能4.1 数据模型设计4.2 页面设计4.3 逻辑设计4.4 流程设计4.5 接…
阅读更多...
milvus学习（一）cosin距离和欧式距离

milvus学习（一）cosin距离和欧式距离

参考&#xff1a;https://blog.csdn.net/qq_36560894/article/details/115408613 归一化以后的cosin距离和欧式距离可以相互转化&#xff0c;未归一化的不可以相互转化&#xff08;因为距离带单位&#xff09;。
阅读更多...
IO DAY2

IO DAY2

#include<my_head.h> //定义注册函数*************************************************** int do_register() { //以追加的形式打开文件 FILE *wfp 0; char name[20]; char pwd[20]; printf("请输入注册账号&#xff1a;"); fgets(…
阅读更多...
VMware15安装Linux，CentOS-7x86_64

VMware15安装Linux，CentOS-7x86_64

最近面试遇到很多Linux&#xff0c;咱就是实在糊弄不过去了&#xff0c;学一下吧 下载网站&#xff0c;官网&#xff1a;https://www.centos.org/download/ 第一步&#xff1a;点击x86_64 第二步&#xff1a;随便选个国内源&#xff0c;我选的清华 第三步&#xff1a;等待下…
阅读更多...
【LeetCode每日一题】466. 统计重复个数

【LeetCode每日一题】466. 统计重复个数

2024-1-2 文章目录 [466. 统计重复个数](https://leetcode.cn/problems/count-the-repetitions/)思路&#xff1a; 466. 统计重复个数 思路&#xff1a; ​ s1表示要重复的序列。n1表示要重复s1的次数。 ​ s2表示要判断的子序列。n2表示子序列s2在整个序列中重复的次数。返回…
阅读更多...
基于微信小程序的停车预约系统设计与实现

基于微信小程序的停车预约系统设计与实现

基于微信小程序的停车预约系统设计与实现 项目概述 本项目旨在结合微信小程序、后台Spring Boot和MySQL数据库&#xff0c;打造一套高效便捷的停车预约系统。用户通过微信小程序进行注册、登录、预约停车位等操作&#xff0c;而管理员和超级管理员则可通过后台管理系统对停车…
阅读更多...
2024 年政府和技术预测

2024 年政府和技术预测

新的一年即将来临&#xff0c;这意味着专家、技术专家和专栏作家应该尝试预测 2024 年政府和技术即将出现的一些最大趋势。今年可能使这些预测变得更加困难的是事实上&#xff0c;许多技术正在以惊人的速度向前发展。在某些情况下&#xff0c;过去需要多年才能慢慢发生的变化现…
阅读更多...
Vue3-32-路由-重定向路由

Vue3-32-路由-重定向路由

什么是重定向 路由的重定向 &#xff1a;将匹配到的路由 【替换】 为另一个路由。 redirect : 重定向的关键字。 重定向的特点 1、重定向是路由的直接替换,路由的地址是直接改变的&#xff1b; 2、在没有子路由配置的情况下&#xff0c;重定向的路由可以省略 component 属性的配…
阅读更多...
MySQL四大引擎建库建表账号管理

MySQL四大引擎建库建表账号管理

目录 一. 数据库四大引擎 1.1 引擎查看 1.2 InnoDB引擎 1.3 MyISAM引擎 1.4 MEMORY引擎 1.5 Archive引擎 二. 数据库管理 2.1 元数据库 2.2 数据库的增删改查及使用 2.3 权限相关表 三. 数据表管理 3.1 三大范式 3.2 基本数据类型 优化原则 分类 四. 数据库账号…
阅读更多...
C++Qt6 多种排序算法的比较 数据结构课程设计 | JorbanS

C++Qt6 多种排序算法的比较 数据结构课程设计 | JorbanS

一、 问题描述 在计算机科学与数学中&#xff0c;一个排序算法&#xff08;英语&#xff1a;Sorting algorithm&#xff09;是一种能将一串资料依照特定排序方式排列的算法。最常用到的排序方式是数值顺序以及字典顺序。有效的排序算法在一些算法&#xff08;例如搜索算法与合…
阅读更多...
学习【Mysql基础篇】这一篇就够了

学习【Mysql基础篇】这一篇就够了

Mysql基础篇 1. Mysql概述1-1. 数据库相关概念1-2. Mysql数据库版本下载安装启动停止客户端连接数据模型 2. SQL2-1. SQL通用语法2-2. SQL分类2-3. DDL数据库操作表操作 - 查询创建表操作 - 修改表操作 - 删除数据类型 2-4. 图像化界面工具2-5. DML2-6. DQL2-7. DCL 3. 函数4. …
阅读更多...
深度理解Flutter：有状态Widget与无状态Widget的详细对比

深度理解Flutter：有状态Widget与无状态Widget的详细对比

有状态Widget 什么是有状态Widget (StatefulWidget) 官方解释&#xff1a; 如果用户与 widget 交互&#xff0c;widget 会发生变化&#xff0c;那么它就是 有状态的。 有状态的 widget 自身是可动态改变的&#xff08;基于State&#xff09;。 例如用户交互而改变 Widget 的 s…
阅读更多...
Java中的类和方法（方法重载）

Java中的类和方法（方法重载）

目录 前言&#xff1a; 什么是面向对象&#xff1f; 什么是类&#xff1f; 类和方法的关系&#xff1a; 方法的定义&#xff1a; 方法重载&#xff1a; 类的定义&#xff1a; 修改类的名字&#xff1a; 实例化&#xff1a; 利用方法对其属性赋值&#xff1a; this…
阅读更多...
C++多态性——(2)联编

C++多态性——(2)联编

归纳编程学习的感悟&#xff0c; 记录奋斗路上的点滴&#xff0c; 希望能帮到一样刻苦的你&#xff01; 如有不足欢迎指正&#xff01; 共同学习交流&#xff01; &#x1f30e;欢迎各位→点赞 &#x1f44d; 收藏⭐ 留言​&#x1f4dd; 成功的秘诀就在于多努力一次&#xff…
阅读更多...
JVM篇：JVM内存结构

JVM篇：JVM内存结构

程序计数器 程序计数器英文名叫&#xff1a;Program Counter Register 作用&#xff1a;用来记录下一条jvm指令的地址行号。 先来查看一段jvm指令&#xff0c;这些指令对应的java代码就是输出1-5 操作系统运行该Java程序时具体流程如下 语言解释&#xff1a;源文件通过编译转…
阅读更多...
基于机器视觉的害虫种类及计数检测研究-人工智能项目-附代码

基于机器视觉的害虫种类及计数检测研究-人工智能项目-附代码

概述 农业与民生和经济发展息息相关&#xff0c;对农业发展科学化的关注既是民生需求&#xff0c; 也是经济稳步发展的迫切需求。病虫害是影响农作物生长的重要因素&#xff0c;对农作物的产量和品质都能造成无法估计的损害。 - 针对目前广大农业产区农业植保人员稀缺、病虫害…
阅读更多...
从零开始配置kali2023环境：配置jupyter的多内核环境

从零开始配置kali2023环境：配置jupyter的多内核环境

在kali2023上面尝试用anaconda3&#xff0c;anaconda2安装实现配置jupyter的多内核环境时出现各种问题&#xff0c;现在可以通过镜像方式解决 1. 搜索镜像 ┌──(holyeyes㉿kali2023)-[~] └─$ sudo docker search anaconda ┌──(holyeyes㉿kali2023)-[~] └─$ sudo …
阅读更多...
关于this.router 和this.route的总结

关于this.router 和this.route的总结

this.router 和this.route这2个东西一直在用可是我还是迷迷糊糊的不知道啥啥意思&#xff0c;尤其是idea的提示功能&#xff0c;总是让我一个回车就弄错了。 总结一波&#xff1a; 概述 this.$router(路由实例) : 是VueRouter的实例.包含了很多属性和对象&#xff08;比如 h…
阅读更多...
最新文章

Copyright @ 2022~2023