标准模板库巧解算法题 栈和队列

232 用栈实现队列

尝试使用栈(stack)来实现队列(queue)。

实现 MyQueue 类:

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空,返回 true ;否则,返回 false

解析:

​ 本题可以使用两个方向相反的栈实现一个队列如下图所示,其中箭头表示元素 pop 方向

标准模板库巧解算法题 栈和队列

​ 使用两个栈的目的是:为了达到先入先出的效果,需要有一个栈用来翻转输入到栈中数组元素的顺序。这个翻转过程既可以在插入时完成,也可以在取值时完成。

​ 在输入时进行反转:当所有元素都压栈进入 in 栈之后,将所有元素先入后出地压入 out 栈翻转数组。

​ 在取值时进行反转:每次取值时,如果out非空则直接取栈顶;如果 out 栈为空,先将 in 栈中的元素全部先入后出压入 out 栈中,再从 out 栈中出栈元素。

class MyQueue {

private:
    // < out | in <
    stack<int> out;
    stack<int> in;

public:
    MyQueue() {}
    
    void push(int x) {
        in.push(x);
    }

    void connectOutIn(){
        if(out.empty()){
            while(!in.empty()){
                int tail = in.top();
                in.pop();
                out.push(tail);
            }
        }
    }
    
    int pop() {
        connectOutIn();
        int tail = out.top();
        out.pop();
        return tail;
    }
    
    int peek() {
        connectOutIn();
        return out.top();
    }
    
    bool empty() {
        return out.empty()&&in.empty(); 
    }
};

225 用队列实现栈

尝试使用队列(queue)来实现栈(stack)。

实现 MyStack 类:

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的,返回 true ;否则,返回 false 。

解析:

​ 本题可以使用两个队列,主队列 q1 和辅助队列 q2,q1 保存当前所有元素,q2 用来在压入新元素时将该元素 q1 中已存在的元素之前。核心思想就是将新元素放到就元素之前形成先入后出。

​ 主要考虑压入新元素的过程:

  • 有新元素要入栈,现将该元素压入辅助队列 q2
  • 将 q1 中的所有元素依次压入已经压入新元素的 q2 中,翻转出队列顺序
  • 将 q2 中的所有元素按次序压入到 q1 中,这一过程也可以直接使用 swap 交换
  • 完成新元素压入操作
class MyStack {

private:
    queue<int> q1;
    queue<int> q2;
public:
    MyStack() {

    }
    
    void push(int x) {
        q2.push(x);
        while(!q1.empty()){
            q2.push(q1.front());
            q1.pop();
        }
        // swap(q1,q2);
        while(!q2.empty()){
            q1.push(q2.front());
            q2.pop();
        }
    }
    
    int pop() {
        int val = q1.front();
        q1.pop();
        return val;
    }
    
    int top() {
        return q1.front();
    }
    
    bool empty() {
        return q1.empty();
    }
};

155 最小栈

设计一个最小栈,除了需要支持常规栈的操作外,还需要支持在 O(1) 时间内查询栈内最小值的功能。

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。

解析:

​ 一种简单的思路是建立一个记录栈内当前最小值的辅助栈:每次插入原栈时,都向辅助栈插入一次原栈里当前所有值的最小值,即为辅助栈栈顶和待插入值中较小的那一个;每次从原栈里取出数字时,同样取出新栈的栈顶。

class MinStack {

private:
    stack<int> s, min_s;

public:
    MinStack() {
        min_s.push(INT_MAX);
    }
    
    void push(int val) {
        min_s.push(min(min_s.top(),val));
        s.push(val);
    }
    
    void pop() {
        min_s.pop();
        s.pop();
    }
    
    int top() {
        return s.top();
    }
    
    int getMin() {
        return min_s.top();
    }
};

​ 采用上述策略简化了判断,但是每次都要插入和取出,提高了时间复杂度。可以增加判断条件,减少辅助栈插入取出的操作:每当在原栈里插入一个数字时,若该数字小于等于辅助栈栈顶,则表示这个数字在原栈里是最小值,我们将其同时插入辅助栈内。每当从原栈里取出一个数字时,若该数字等于辅助栈栈顶,则表示这个数是原栈里的最小值之一,同时取出辅助栈栈顶的值。

20 有效的括号

给定一个只由左右原括号、花括号和方括号组成的字符串,求这个字符串是否合法。合法的定义是每一个类型的左括号都有一个右括号一一对应,且括号内的字符串也满足此要求。

输入是一个字符串,输出是一个布尔值,表示字符串是否合法。

输入:s = “()[]{}”
输出:true

解析:

​ 括号匹配是典型的使用栈来解决的问题。从左往右遍历,每当遇到左括号便放入栈内,遇到右括号则判断其和栈顶的括号是否是统一类型,是则从栈内取出左括号,否则说明字符串不合法。

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for(const auto c: s){
            if(c=='(' || c=='[' || c=='{'){
                st.push(c);
            }else{
                if(st.empty()){
                    return false;
                }
                if(c==')' && st.top()=='('){
                    st.pop();
                }else if(c==']' && st.top()=='['){
                    st.pop();
                }else if(c=='}' && st.top()=='{'){
                    st.pop();
                }else{
                    return false;
                }
            }
        }
        return st.empty();
    }
};

参考资料

LeetCode 101:和你一起轻松刷题(C++) 第 11 章 妙用数据结构

上一篇:JZ9 用两个栈实现队列


下一篇:滑动窗口的中位数