手撕代码之栈和队列

文章目录

• 一、括号匹配（leetcode 20）
• 二、最小栈（leetcode 155）
• 三、两个栈实现一个队列（leetcode 232）

一、括号匹配（leetcode 20）

class Solution {
public:
    bool isValid(string s) {
        if (s.empty())
            return true;
        stack<char> stk;
        stk.push(s[0]);
        // 使用栈保存字符，如果新加入的字符与栈顶元素匹配则弹栈
        for (int i = 1; i < s.size(); ++i){
            if ( !stk.empty() && s[i] == ')' && stk.top() == '(' )
                stk.pop();
            else if ( !stk.empty() && s[i] == ']' && stk.top() == '[' )
                stk.pop();
            else if ( !stk.empty() && s[i] == '}' && stk.top() == '{' )
                stk.pop();
            else
                stk.push(s[i]);
        }
        if (!stk.empty())
            return false;
        else
            return true;
    }
};

二、最小栈（leetcode 155）

思路：使用辅助栈来实现，插入元素的时候先和minstack的栈顶元素比较，弹出元素的时候如果stack和minstack的栈顶元素相同，则弹出stack和minstack的栈顶元素。

class MinStack {
public:
    stack<int> stk, minstk;
    MinStack() { }
    
    void push(int x) {
        stk.push(x);
        if (minstk.empty() || x <= minstk.top())
            minstk.push(x);
    }
    
    void pop() {
        if (stk.top() == minstk.top())
            minstk.pop();
        stk.pop();
    }
    
    int top() {
        return stk.top();
    }
    
    int getMin() {
        return minstk.top();
    }
};

三、两个栈实现一个队列（leetcode 232）

思路：使用两个栈来实现，stack1负责插入元素，弹出元素的时候，首先判断stack2是否为空，如果不空则直接弹出stack2的栈顶元素，否则就把stack1里面的元素全部弹出插入到stack2中。

class MyQueue {
public:
    stack<int> stk1, stk2;
    MyQueue() { }
    
    void push(int x) {
        stk1.push(x);
    }

    int pop() {
        if (!stk2.empty()){
            int pop = stk2.top();
            stk2.pop();
            return pop;
        }
        else{
            while (!stk1.empty()){
                stk2.push(stk1.top());
                stk1.pop();
            }
            int pop = stk2.top();
            stk2.pop();
            return pop;
        }
    }
    
    int peek() {
        if (!stk2.empty()){
            return stk2.top();
        }
        else{
            while (!stk1.empty()){
                stk2.push(stk1.top());
                stk1.pop();
            }
            return stk2.top();
        }
    }
    
    bool empty() {
        if (stk1.empty() && stk2.empty()){
            return true;
        }
        return false;
    }
};