C++初阶作业 Stack&&queue 作业题一

简介: C++初阶作业 Stack&&queue 作业题一

最小栈问题


它问题的题目描述是这样子的

da174c7130dc4a00b39cd090ca5002c3.png


什么意思呢? 用一句话解释下 就是设计一个栈


这个栈除了能够执行正常的操作之外我们还要可以随时的获取这个栈中的最小元素


那我们想想看我们的思路是什么?


是不是只要设计两个栈就好了?


一个栈正常的存放数据


一个栈比较下当前存放的数据是否比自己最小的数据小


如果小于自己最小的数据那就入这个数据 如果不小于自己最小的数据 那么就再入一次目前来说最小的数据


这道题的主要难点在于思路 思路解决了 后面的问题也就解决了


代码表示如下


class MinStack {
public:
    MinStack() {
    }
    void push(int val) 
    {
        _stk.push(val);
        if (_stkmin.empty())
        {
            _stkmin.push(val);
        }
        else
        {
            if (_stkmin.top() > val)
            {
                _stkmin.push(val);
            }
            else
            {
                _stkmin.push(_stkmin.top());
            }
        }
    }
    void pop() 
    {
        _stk.pop();
        _stkmin.pop();
    }
    int top() 
    {
        return _stk.top();
    }
    int getMin() 
    {
        return _stkmin.top();
    }
private:
    stack<int> _stk;
    stack<int> _stkmin;
};


da2b4c14730a4b87ac537a394f926b12.png


栈的压入弹出序列


题目如下

287cf4468df645079a970040adebcb8e.png


这里的题目要求我们来设计一个算法 检验栈的插入弹出序列是否是有效的


也就是说 最后能否完全弹出所有的数据


那想想看 我们这个时候应该怎么做呢?


要设计一个算法去计算有点太难了是不是


那么我们可不可以直接使用一个栈来模拟这个过程呢?


如果模拟通过是不是就表示肯定能通过了啊


我们一开始可以设计两个指针


一个指针指向插入数据的数组


一个指针指向删除数据的数组


像这样

9bdbd617b23043c691ab0497b4df4cb0.png



当我们的出栈序列不等于入栈序列的时候那就一直入栈


当我们的出栈序列等于入栈序列的时候呢 就开始出栈


原则是:出掉所有符合出栈序列的数

1fb1dc94b7484d7bb9908cac678b4cac.png


像是这种情况 就代表出掉了所有的可以出的序列了


所以我们这个时候就停止出栈


当5也入栈的时候

a20865960b4349bb9a5575366e89e67a.png


这个时候就是按照 5 3 2 1的顺序出栈了


那么我们的代码表示如下


class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) 
    {
        stack<int> st;
        int pushvi = 0;
        int popvi = 0;
        while(pushvi < pushV.size())
        {
            st.push(pushV[pushvi]);
            pushvi++;
            // 判断是否要删除
            while(!st.empty() && st.top() == popV[popvi])
            {
                st.pop();
                popvi++;
            }
        }
        // 最后判断下结束
        return popvi == popV.size(); 
    }
};

运行结果如下


b9e60bca0ecc40d9b18d6003ab85c1b1.png


逆波兰表达式问题


题目如下


6ce1cfd646024cce988fa715869f03a5.png


这里大家首先要理解逆波兰表达式究竟是什么?


大家可以上各类视频网站详细了解下 由于博客篇幅限制 这里


就只谈逆波兰表达式如何使用


它的原则其实很简单就只有两条


1 如果我们遍历到加减乘除四个字符串 那么我们就从栈中取出两个元素来分别作为左操作数和右边操作进行运算 之后还将它入栈


2 如果我们遍历到了数字字符串 那么我们就将它转化成整型数字 然后存放到栈当中去


那么对应的代码表示也就很简单了


long num1 = st.top(); st.pop();
           long num2 = st.top(); st.pop();
           if (x == "+") st.push(num2 + num1);
           if (x == "-") st.push(num2 - num1);
           if (x == "*") st.push(num2 * num1);
           if (x == "/") st.push(num2 / num1);
st.push(stol(x));


最后在栈里面的数字其实就是我们要求的答案了


那么完整的代码表示如下


class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for (auto x : tokens)
        {
            if (x == "+" || x =="-" || x =="*" || x =="/")
            {
                long num1 = st.top(); st.pop();
                long num2 = st.top(); st.pop();
                if (x == "+") st.push(num2 + num1);
                if (x == "-") st.push(num2 - num1);
                if (x == "*") st.push(num2 * num1);
                if (x == "/") st.push(num2 / num1);
            }
            else
            {
                st.push(stol(x));
            }
        }
        return st.top();
    }
};

运行结果如下


906688d18ccf40ef91ad96c5322c7c6b.png


总结


讲解了栈的三道题目 最小栈问题 栈的压入弹出序列 逆波兰表达式问题

相关文章
|
1月前
|
设计模式 C++ 容器
c++中的Stack与Queue
c++中的Stack与Queue
|
2月前
|
C++ 容器
【c++丨STL】stack和queue的使用及模拟实现
本文介绍了STL中的两个重要容器适配器:栈(stack)和队列(queue)。容器适配器是在已有容器基础上添加新特性或功能的结构,如栈基于顺序表或链表限制操作实现。文章详细讲解了stack和queue的主要成员函数(empty、size、top/front/back、push/pop、swap),并提供了使用示例和模拟实现代码。通过这些内容,读者可以更好地理解这两种数据结构的工作原理及其实现方法。最后,作者鼓励读者点赞支持。 总结:本文深入浅出地讲解了STL中stack和queue的使用方法及其模拟实现,帮助读者掌握这两种容器适配器的特性和应用场景。
74 21
|
5月前
|
存储 算法 调度
【C++打怪之路Lv11】-- stack、queue和优先级队列
【C++打怪之路Lv11】-- stack、queue和优先级队列
75 1
|
5月前
|
设计模式 存储 C++
C++之stack 和 queue(下)
C++之stack 和 queue(下)
84 1
|
5月前
|
C++ 容器
C++之stack 和 queue(上)
C++之stack 和 queue(上)
131 0
|
5月前
|
存储 C++ 容器
C++番外篇——stack、queue的实现及deque的介绍
C++番外篇——stack、queue的实现及deque的介绍
47 0
|
5月前
|
存储 算法 C++
C++入门10——stack与queue的使用
C++入门10——stack与queue的使用
71 0
|
1月前
|
编译器 C++ 开发者
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。
|
16天前
|
设计模式 安全 C++
【C++进阶】特殊类设计 && 单例模式
通过对特殊类设计和单例模式的深入探讨,我们可以更好地设计和实现复杂的C++程序。特殊类设计提高了代码的安全性和可维护性,而单例模式则确保类的唯一实例性和全局访问性。理解并掌握这些高级设计技巧,对于提升C++编程水平至关重要。
39 16
|
9天前
|
编译器 C++
类和对象(中 )C++
本文详细讲解了C++中的默认成员函数,包括构造函数、析构函数、拷贝构造函数、赋值运算符重载和取地址运算符重载等内容。重点分析了各函数的特点、使用场景及相互关系,如构造函数的主要任务是初始化对象,而非创建空间;析构函数用于清理资源;拷贝构造与赋值运算符的区别在于前者用于创建新对象,后者用于已存在的对象赋值。同时,文章还探讨了运算符重载的规则及其应用场景,并通过实例加深理解。最后强调,若类中存在资源管理,需显式定义拷贝构造和赋值运算符以避免浅拷贝问题。