文章目录

• 栈与队列
• • 2. 用栈实现队列
  • 3. 用队列实现栈
  • 4. 有效的括号
  • 5. 删除字符串中的所有相邻重复项

栈与队列

2. 用栈实现队列

232. 用栈实现队列

思路：
开两个栈，一个用来放进入队列的值，如果要取队首：

1. 如果 stOut 为空，则将 stIn 栈中的所有元素弹出依次放入 stOut 栈中，并弹出 stOut 栈顶，为队首元素
2. 如果 stOut 不空，则将 stOut 的栈顶弹出

class MyQueue {
public:stack stIn;stack stOut;MyQueue() {}void push(int x) {stIn.push(x);}int pop() {int ret;if (stOut.size() == 0) {int stInSize = stIn.size();while (stInSize--) {stOut.push(stIn.top());stIn.pop();}}ret = stOut.top();stOut.pop();return ret;}int peek() {int ret;if (stOut.size() == 0) {int stInSize = stIn.size();while (stInSize--) {stOut.push(stIn.top());stIn.pop();}}ret = stOut.top();return ret;}bool empty() {if (stOut.size() == 0 && stIn.size() == 0) return true;else return false;}
};

3. 用队列实现栈

225. 用队列实现栈

思路：
将队尾之前的所有元素依次出队首，入队尾，则之前的队尾，此时到了队首，即栈顶元素。

class MyStack {
public:queue que;MyStack() {}void push(int x) {que.push(x);}int pop() {int size = que.size() - 1;while (size--) {que.push(que.front());que.pop();}int res = que.front();que.pop();return res;}int top() {int size = que.size();int res;while (size--) {que.push(que.front());res = que.front();que.pop();}return res;}bool empty() {return que.empty();}
};

4. 有效的括号

20. 有效的括号

思路：
括号都是成对出现的，先入的括号匹配后入的括回。将左括号压入栈中，如果遇到匹配的右括号，则弹出。最后判断，如果栈为空，则为有效输入，否则返回
false。

class Solution {
public:bool isValid(string s) {stack st;int sLen = s.length();for (int i = 0; i < sLen; i++) {if ( !st.empty() && ( (st.top() == '(' && s[i] == ')') || (st.top() == '[' && s[i] == ']')|| (st.top() == '{' && s[i] == '}') ) ) {st.pop();} else {st.push(s[i]);}}return st.empty();}
};

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

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

思路：
利用字符串模拟栈，更方便，栈顶等于输入字符，则弹出，否则压入。

class Solution {
public:string removeDuplicates(string s) {string ans = "";for (char str : s) {if (!ans.empty() && ans.back() == str) ans.pop_back();else ans += str;}return ans;}
};