理论基础

栈是先进后出，队列是先进先出。

如图所示：

理解如下4个问题

1. C++中stack 是容器么？
2. 我们使用的stack是属于哪个版本的STL？
3. 我们使用的STL中stack是如何实现的？
4. stack 提供迭代器来遍历stack空间么？

栈和队列是STL（C++标准库）里面的两个数据结构。

C++标准库是有多个版本的，要知道我们使用的STL是哪个版本，才能知道对应的栈和队列的实现原理。

那么来介绍一下，三个最为普遍的STL版本：

1. HP STL 其他版本的C++ STL，一般是以HP STL为蓝本实现出来的，HP STL是C++ STL的第一个实现版本，而且开放源代码。
2. P.J.Plauger STL 由P.J.Plauger参照HP STL实现出来的，被Visual C++编译器所采用，不是开源的。
3. SGI STL 由Silicon Graphics Computer Systems公司参照HP STL实现，被Linux的C++编译器GCC所采用，SGI STL是开源软件，源码可读性甚高。

栈和队列也是SGI STL里面的数据结构， 知道了使用版本，才知道对应的底层实现。

来说一说栈，栈先进后出，如图所示：

栈提供push 和 pop 等等接口，所有元素必须符合先进后出规则，所以栈不提供走访功能，也不提供迭代器(iterator)。 不像是set 或者map 提供迭代器iterator来遍历所有元素。

栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说我们可以控制使用哪种容器来实现栈的功能）。

所以STL中栈往往不被归类为容器，而被归类为container adapter（容器适配器）。

那么问题来了，STL 中栈是用什么容器实现的？

从下图中可以看出，栈的内部结构，栈的底层实现可以是vector，deque，list 都是可以的， 主要就是数组和链表的底层实现。

我们常用的SGI STL，如果没有指定底层实现的话，默认是以deque为缺省情况下栈的底层结构。

deque是一个双向队列，只要封住一端，只开通另一端就可以实现栈的逻辑了。

SGI STL中 队列底层实现缺省情况下一样使用deque实现的。

我们也可以指定vector为栈的底层实现，初始化语句如下：

std::stack<int, std::vector<int> > third;  // 使用vector为底层容器的栈

刚刚讲过栈的特性，对应的队列的情况是一样的。

队列中先进先出的数据结构，同样不允许有遍历行为，不提供迭代器, SGI STL中队列一样是以deque为缺省情况下的底部结构。

也可以指定list 为起底层实现，初始化queue的语句如下：

std::queue<int, std::list<int>> third; // 定义以list为底层容器的队列

所以STL 队列也不被归类为容器，而被归类为container adapter（ 容器适配器）。

我这里讲的都是C++ 语言中的情况， 使用其他语言的同学也要思考栈与队列的底层实现问题， 不要对数据结构的使用浅尝辄止，而要深挖其内部原理，才能夯实基础。

力扣232：用栈实现队列

题目描述

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

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

说明：

• 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
• 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[ [], [1], [2], [], [], [] ]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

解题思路

• 结合下图来理解：用栈来模拟队列，需要两个栈来实现，不难理解。
  

  完整代码

  //用栈实现队列
  class MyQueue {
  public:
  
      //构建入栈与出栈，因为栈的特殊性，先进后出，所以需要两个栈来实现队列的功能。
      stack<int> stIn;
      stack<int> stOt;
      MyQueue() {
  
      }
  
      //将元素X推入到队列的末尾
      void push(int x) {
          stIn.push(x);
      }
  
      //从队列的开头移除并返回元素
      int pop() {
          //移除并返回stOt的首部元素，但需要注意的是这仅在stOt不为空的情况下成立，若为空，则需要把stIn的元素全部导入到stOt中。
          if(stOt.empty()){
              while(!stIn.empty()){
                  stOt.push(stIn.top());
                  stIn.pop();
              }
          }
          int result = stOt.top();
          stOt.pop();
          return result;
  
      }
      //返回队列开头的元素
      int peek() {
          int res = this->pop();
          stOt.push(res);
          return res;
      }
      //判断队列是否为空
      bool empty() {
          return(stIn.empty() && stOt.empty());
      }
  };
  
  
  /**
  
   * Your MyQueue object will be instantiated and called as such:
  
   * MyQueue* obj = new MyQueue();
  
   * obj->push(x);
  
   * int param_2 = obj->pop();
  
   * int param_3 = obj->peek();
  
   * bool param_4 = obj->empty();
  
   */

  力扣225：用队列实现栈

  题目描述

  请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

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

注意：

• 你只能使用队列的标准操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
• 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

解题思路

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

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

完整代码

//用队列来模拟栈
class MyStack {
public:

    //构建用来干活的两个队列，其中que1是用来实际操作的，que2是操作过程中用来备份前面元素的，毕竟队列是先进先出，想要操作后面的元素，就只能把前面的元素备份一下
    queue<int> que1;
    queue<int> que2;

    MyStack() {
    }
    
    //将元素压入栈顶
    void push(int x) {
        que1.push(x);
    }

    //移除并返回栈顶
    int pop() {
        int num = que1.size();
        num = num - 1;
        while(num){
            que2.push(que1.front());  //将que1的元素导入到que2中，但留下最后一个元素，该元素是需要返回的元素
            que1.pop();
            num = num - 1;
        }

        int result = que1.front();
        que1.pop();  //实现清楚栈顶元素，同时也返回这个元素
        que1 = que2;
        while(!que2.empty()){
            que2.pop();
        }
        return result;
    }

    //返回栈顶元素
    int top() {
        int size = que1.size();
        size--;
        while(size--){
            que2.push(que1.front());
            que1.pop();
        }

        int result = que1.front();
        que2.push(que1.front()); //将剩下的最后一个元素也存入que2
        que1.pop();          
        que1 = que2;      //还原que1
        while(!que2.empty()){
            que2.pop();
        }

        return result;
    }
    
    //判断栈是否为空
    bool empty() {
        return que1.empty();
    }
};

  

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

力扣20：有效的括号

题目描述

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入： s = "()"

输出： true

示例 2：

输入： s = "()[]{}"

输出： true

示例 3：

输入： s = "(]"

输出： false

示例 4：

输入： s = "([])"

输出： true

解题思路

括号匹配是栈应用的经典问题。

有三种不匹配的情况，

1. 第一种情况，字符串里左方向的括号多余了 ，所以不匹配。 
2. 第二种情况，括号没有多余，但是 括号的类型没有匹配上。 
3. 第三种情况，字符串里右方向的括号多余了，所以不匹配。 

代码只要覆盖了这三种不匹配的情况，就不会出问题。

动画如下：

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

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

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

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

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

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

完整代码

不得不说，这种思路真的有点意思

class Solution {
public:
    bool isValid(string s) {
        if (s.size() % 2 != 0) return false; // 如果s的长度为奇数，一定不符合要求
        stack<char> st;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') st.push(')');
            else if (s[i] == '{') st.push('}');
            else if (s[i] == '[') st.push(']');
            // 第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号 return false
            // 第二种情况：遍历字符串匹配的过程中，发现栈里没有我们要匹配的字符。所以return false
            else if (st.empty() || st.top() != s[i]) return false;
            else st.pop(); // st.top() 与 s[i]相等，栈弹出元素
        }
        // 第一种情况：此时我们已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false，否则就return true
        return st.empty();
    }
};

力扣1047：删除字符串中所有相邻重复项

题目描述

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

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

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

示例：

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

解题思路

反复调用，直至没有符合要求的结果。
和上题基本思路一致；是一个匹配问题，使用栈存放遍历过的元素，当遇到相同元素时，就弹出，不断弹出，直至最后遍历结束。

完整代码

class Solution {

public:
    string removeDuplicates(string S) {
        stack<char> st;
        for(char s : S){
            if(st.empty() || s != st.top()){
                st.push(s);
            }else{
                st.pop();
            }
        }

        string result = "";
        while(!st.empty()){
            result += st.top();
            st.pop();
        }
        reverse(result.begin(), result.end());
        return result;
    }
};