代码随想录算法训练营第十天 |

力扣题目链接

使用栈实现队列的下列操作：

push(x) -- 将一个元素放入队列的尾部。 pop() -- 从队列首部移除元素。 peek() -- 返回队列首部的元素。 empty() -- 返回队列是否为空。

示例:

MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false

说明:

• 你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。

• 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

• 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。

算法公开课

《代码随想录》算法视频公开课：栈的基本操作！ | LeetCode：232.用栈实现队列，相信结合视频再看本篇题解，更有助于大家对本题的理解。

思路

这是一道模拟题，不涉及到具体算法，考察的就是对栈和队列的掌握程度。

使用栈来模式队列的行为，如果仅仅用一个栈，是一定不行的，所以需要两个栈一个输入栈，一个输出栈，这里要注意输入栈和输出栈的关系。

下面动画模拟以下队列的执行过程：

执行语句： queue.push(1); queue.push(2); queue.pop(); 注意此时的输出栈的操作 queue.push(3); queue.push(4); queue.pop(); queue.pop();注意此时的输出栈的操作 queue.pop(); queue.empty();

在push数据的时候，只要数据放进输入栈就好，但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。

最后如何判断队列为空呢？如果进栈和出栈都为空的话，说明模拟的队列为空了。

在代码实现的时候，会发现pop() 和 peek()两个函数功能类似，代码实现上也是类似的，可以思考一下如何把代码抽象一下。

C++代码如下：

class MyQueue {
private:
    stack<int> inStk; //不用构造这两个东西，因为他们是容器适配器
    stack<int> outstk;
​
public:
    MyQueue() {}
​
    void push(int x) { inStk.push(x); }
​
    int pop() {
        if (outstk.empty()) {
            while (!inStk.empty()) {
                int tmp = inStk.top();
                inStk.pop();
                outstk.push(tmp);
            }
        }
​
        int result = outstk.top();
        outstk.pop();
        return result;
    }
​
    int peek() {
        int result = pop();
        outstk.push(result);
        return result;
    }
​
    bool empty() { return inStk.empty() && outstk.empty(); }
};
​

• 时间复杂度: push和empty为O(1), pop和peek为O(n)

• 空间复杂度: O(n)

225. 用队列实现栈

力扣题目链接

使用队列实现栈的下列操作：

• push(x) -- 元素 x 入栈

• pop() -- 移除栈顶元素

• top() -- 获取栈顶元素

• empty() -- 返回栈是否为空

注意:

• 你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。

• 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

• 你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

算法公开课

《代码随想录》算法视频公开课：队列的基本操作！ | LeetCode：225. 用队列实现栈，相信结合视频再看本篇题解，更有助于大家对本题的理解。

思路

（这里要强调是单向队列）

有的同学可能疑惑这种题目有什么实际工程意义，其实很多算法题目主要是对知识点的考察和教学意义远大于其工程实践的意义，所以面试题也是这样！

刚刚做过栈与队列：我用栈来实现队列怎么样？的同学可能依然想着用一个输入队列，一个输出队列，就可以模拟栈的功能，仔细想一下还真不行！

队列模拟栈，其实一个队列就够了，那么我们先说一说两个队列来实现栈的思路。

队列是先进先出的规则，把一个队列中的数据导入另一个队列中，数据的顺序并没有变，并没有变成先进后出的顺序。

所以用栈实现队列， 和用队列实现栈的思路还是不一样的，这取决于这两个数据结构的性质。

但是依然还是要用两个队列来模拟栈，只不过没有输入和输出的关系，而是另一个队列完全用来备份的！

如下面动画所示，用两个队列que1和que2实现队列的功能，que2其实完全就是一个备份的作用，把que1最后面的元素以外的元素都备份到que2，然后弹出最后面的元素，再把其他元素从que2导回que1。

模拟的队列执行语句如下：

queue.push(1);        
queue.push(2);        
queue.pop();   // 注意弹出的操作       
queue.push(3);        
queue.push(4);       
queue.pop();  // 注意弹出的操作    
queue.pop();    
queue.pop();    
queue.empty();    

详细如代码注释所示：

class MyStack {
private:
    queue<int> q1;
    queue<int> q2;
​
public:
    MyStack() {}
​
    void push(int x) { q1.push(x); }
​
    int pop() {
        while (q1.size() > 1) {
            int tmp = q1.front();
            q2.push(tmp);
            q1.pop();
        }
        int result = q1.front();
        q1.pop();
        q1 = q2;
        while (!q2.empty()) {
            q2.pop();
        }
        return result;
    }
​
    int top() {
        int result = this->pop();
        q1.push(result);
        return result;
    }
​
    bool empty() { return q1.empty() && q2.empty(); }
};
​

• 时间复杂度: pop为O(n)，其他为O(1)

• 空间复杂度: O(n)

优化

其实这道题目就是用一个队列就够了。

一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时再去弹出元素就是栈的顺序了。

C++优化代码

class MyStack {
private:
    queue<int> q;
​
public:
    MyStack() {}
​
    void push(int x) { q.push(x); }
​
    int pop() {
        int size = q.size() - 1;
        for (int i = 0; i < size; i++) {
            int front = q.front();
            q.pop();
            q.push(front);
        }
        int result = q.front();
        q.pop();
        return result;
    }
​
    int top() { return q.back(); }
​
    bool empty() { return q.empty(); }
};

• 时间复杂度: pop为O(n)，其他为O(1)

• 空间复杂度: O(n)

数据结构与算法应用往往隐藏在我们看不到的地方

20. 有效的括号

力扣题目链接

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。

• 左括号必须以正确的顺序闭合。

• 注意空字符串可被认为是有效字符串。

示例 1:

• 输入: "()"

• 输出: true

示例 2:

• 输入: "()[]{}"

• 输出: true

示例 3:

• 输入: "(]"

• 输出: false

示例 4:

• 输入: "([)]"

• 输出: false

示例 5:

• 输入: "{[]}"

• 输出: true

算法公开课

《代码随想录》算法视频公开课：栈的拿手好戏！| LeetCode：20. 有效的括号，相信结合视频再看本篇题解，更有助于大家对本题的理解。

思路

题外话

括号匹配是使用栈解决的经典问题。

题意其实就像我们在写代码的过程中，要求括号的顺序是一样的，有左括号，相应的位置必须要有右括号。

如果还记得编译原理的话，编译器在 词法分析的过程中处理括号、花括号等这个符号的逻辑，也是使用了栈这种数据结构。

再举个例子，linux系统中，cd这个进入目录的命令我们应该再熟悉不过了。

cd a/b/c/../../

这个命令最后进入a目录，系统是如何知道进入了a目录呢 ，这就是栈的应用（其实可以出一道相应的面试题了）

所以栈在计算机领域中应用是非常广泛的。

有的同学经常会想学的这些数据结构有什么用，也开发不了什么软件，大多数同学说的软件应该都是可视化的软件例如APP、网站之类的，那都是非常上层的应用了，底层很多功能的实现都是基础的数据结构和算法。

所以数据结构与算法的应用往往隐藏在我们看不到的地方！

这里我就不过多展开了，先来看题。

进入正题

由于栈结构的特殊性，非常适合做对称匹配类的题目。

首先要弄清楚，字符串里的括号不匹配有几种情况。

一些同学，在面试中看到这种题目上来就开始写代码，然后就越写越乱。

建议在写代码之前要分析好有哪几种不匹配的情况，如果不在动手之前分析好，写出的代码也会有很多问题。

先来分析一下 这里有三种不匹配的情况，

1. 第一种情况，字符串里左方向的括号多余了 ，所以不匹配。

   

2. 第二种情况，括号没有多余，但是 括号的类型没有匹配上。

   

3. 第三种情况，字符串里右方向的括号多余了，所以不匹配。

   

我们的代码只要覆盖了这三种不匹配的情况，就不会出问题，可以看出 动手之前分析好题目的重要性。

动画如下：

第一种情况：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false

第二种情况：遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以return false

第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false

那么什么时候说明左括号和右括号全都匹配了呢，就是字符串遍历完之后，栈是空的，就说明全都匹配了。

分析完之后，代码其实就比较好写了，

但还有一些技巧，在匹配左括号的时候，右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了，比左括号先入栈代码实现要简单的多了！

实现C++代码如下：

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

• 时间复杂度: O(n)

• 空间复杂度: O(n)

匹配问题都是栈的强项

1047. 删除字符串中的所有相邻重复项

力扣题目链接

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

• 输入："abbaca"

• 输出："ca"

• 解释：例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

提示：

• 1 <= S.length <= 20000

• S 仅由小写英文字母组成。

算法公开课

《代码随想录》算法视频公开课：栈的好戏还要继续！| LeetCode：1047. 删除字符串中的所有相邻重复项，相信结合视频再看本篇题解，更有助于大家对本题的理解。

思路

正题

本题要删除相邻相同元素，相对于20. 有效的括号来说其实也是匹配问题，20. 有效的括号 是匹配左右括号，本题是匹配相邻元素，最后都是做消除的操作。

本题也是用栈来解决的经典题目。

那么栈里应该放的是什么元素呢？

我们在删除相邻重复项的时候，其实就是要知道当前遍历的这个元素，我们在前一位是不是遍历过一样数值的元素，那么如何记录前面遍历过的元素呢？

所以就是用栈来存放，那么栈的目的，就是存放遍历过的元素，当遍历当前的这个元素的时候，去栈里看一下我们是不是遍历过相同数值的相邻元素。

然后再去做对应的消除操作。 如动画所示：

从栈中弹出剩余元素，此时是字符串ac，因为从栈里弹出的元素是倒序的，所以再对字符串进行反转一下，就得到了最终的结果。

C++代码 :

class Solution {
public:
    string removeDuplicates(string s) {
        
        stack<char> stk;
       for (char c : s) {
            if (!stk.empty() && c == stk.top()) {
                stk.pop();
            } else {
                stk.push(c);
            }
        }
​
        int size = stk.size();
        string result(size,'0');
        while(size>0)
        {
            result[size-1] = stk.top();
            stk.pop();
            size--;
        }
        return result;
​
    }
};

• 时间复杂度: O(n)

• 空间复杂度: O(1)，返回值不计空间复杂度