专题一:栈系列


1. 中缀表达式后缀表达式(逆波兰式)


在这里插入图片描述

算法原理
在这里插入图片描述


2. 有效括号


题目链接

算法原理

在这里插入图片描述

代码编写

class Solution 
{
public:
    bool isValid(string s) 
    {
        stack<char> st;
        for(const auto ch : s)
        {
            if(ch == '(' || ch == '[' || ch == '{') st.push(ch);
            else 
            {
                // 1、右括号
                if(st.empty()) return false;

                char top = st.top();
                if(top == '(' && ch == ')' || top == '[' && ch == ']' || top == '{' && ch == '}') 
                    st.pop();
                else 
                    return false; // 2、括号匹配
            }
        }

        return st.empty(); // 3、最后若栈为空说明括号全部正确匹配完成
    }
};

3. 用栈实现队列


题目链接

算法原理
在这里插入图片描述

代码编写

class MyQueue 
{
private:
    stack<int> st1; //负责队列
    stack<int> st2; //负责出队

public:
    // 构造函数什么都不需要
    MyQueue() 
    {}
    
    // 入队
    void push(int x) 
    {
        st1.push(x);
    }
    
    // 出队
    int pop() 
    {
        // 队列为空,则返回-1
        if(st1.empty() &amp;&amp; st2.empty()) return -1;   
        // 若 st2 为空,则需要从 st1 中把元素更新过来
        if(st2.empty()) 
        {
            while(!st1.empty()) 
            {
                st2.push(st1.top());
                st1.pop();
            }
        }
        //  st2 栈顶元素即使队列的对首元素删除即可
        int ans = st2.top();
        st2.pop();
        return ans;
    }
    
    int peek() 
    {
        // 队列为空,则返回-1
        if(st1.empty() &amp;&amp; st2.empty()) return -1;
        // 若 st2 为空,则需要从 st1 中把元素更新过来
        if(st2.empty())
        {
            while(!st1.empty()) 
            {
                st2.push(st1.top());
                st1.pop();
            }
        }
        //  st2 栈顶元素即使队列的对首元素,返回即可
        return st2.top();
    }
    
    // 队列判空
    bool empty() 
    {
        return st1.empty() &amp;&amp; st2.empty();
    }
};

4. 最小


题目链接

算法原理
在这里插入图片描述

代码编写

class MinStack 
{
private:
    stack<int> st;   //存放元素
    stack<int> minSt;//存放st中,最小元素序列

public:
    // 默认构造函数
    MinStack() 
    {}
    
    // 栈中插入元素
    void push(int val) 
    {
        st.push(val);
        // 1、若最小为空说明第一个插入元素),此时 val 直接最小
        // 2、若最小栈不为空,则比较最小栈栈顶元素,再决定是否插入最小栈
        if(minSt.empty()) minSt.push(val);
        else
        {
            if(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();
    }
};

原文地址:https://blog.csdn.net/m0_51064412/article/details/134781905

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任

如若转载,请注明出处:http://www.7code.cn/show_41804.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱suwngjj01@126.com进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注