关于栈和队列

STL 中的 stack 容器提供了一众成员函数以供调用，其中较为常用的有：

• 元素访问
  • st.top() 返回栈顶
• 修改
  • st.push() 插入传入的参数到栈顶
  • st.pop() 弹出栈顶
• 容量
  • st.empty() 返回是否为空
  • st.size() 返回元素数量

STL 中的 stack 容器提供了一众成员函数以供调用，其中较为常用的有：

元素访问
st.top() 返回栈顶
修改
st.push() 插入传入的参数到栈顶
st.pop() 弹出栈顶
容量
st.empty() 返回是否为空
st.size() 返回元素数量

232.用栈实现队列

class MyQueue {
public:
    MyQueue() {

    }
    stack<int> stackIn;
    stack<int> stackOut;
    void push(int x) {
        stackIn.push(x);
    }
    
    int pop() {
        if (stackOut.empty()) {
            while (!stackIn.empty()) {
              stackOut.push(stackIn.top());
              stackIn.pop();
            }
        }
        int res = stackOut.top();
        stackOut.pop();
        return res;
    }
    
    int peek() {
      int peek = this->pop();
      stackOut.push(peek);
      return peek;
    }
    
    bool empty() {
        return stackOut.empty()&&stackIn.empty();
    }
};

225.用队列实现栈

class MyStack {
public:
  queue<int> que;
  MyStack() {}

  void push(int x) {
    que.push(x);
  }

  int pop() {
    for (int i = 0; i < que.size() - 1; i++) {
      push(que.front());
      que.pop();
    }
    int res = que.front();
    que.pop();
    return res;
  }

  int top() {
    return que.back();
  }

  bool empty() {
    return que.empty();
  }
};

20.有效的括号

class Solution {
public:
  bool isValid(string 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('}');
      } else if (st.empty() || st.top() != s[i]) {
        return false;
      } else {
        st.pop();
      }
    }
    return st.empty();
  }
};

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

第一次尝试

class Solution {
public:
  string removeDuplicates(string s) {
    stack<char> st;
    for (int i = 0; i < s.size(); i++) {
      if (s[i] == st.top()) {
        st.pop();
      } else {
      st.push(s[i]);
      }
    }
    string res;
    while (!st.empty()) {
      res += st.top();
      st.pop();
    }
    reverse(res.begin(),res.end());
    return res;
  }
};

但是这样会报错

Line 6: Char 22: AddressSanitizer: SEGV on unknown address (pc 0x55c137b54e8a bp 0x7ffcd61a8b30 sp 0x7ffcd61a8a40 T0)
Line 6: Char 22:

我估计是因为空栈获取栈顶元素会报错

class Solution {
public:
  string removeDuplicates(string s) {
    stack<char> st;
    for (int i = 0; i < s.size(); i++) {
      if (st.empty() || st.top() != s[i]) {
        st.push(s[i]);
      } else {
      st.pop();
      }
    }
    string res;
    while (!st.empty()) {
      res += st.top();
      st.pop();
    }
    reverse(res.begin(),res.end());
    return res;
  }
};