力扣算法刷题 Day 10
232 用栈实现队列
题目链接
232. 用栈实现队列 - 力扣（LeetCode）
思路
用一个出栈和入栈
文章详解
232.用栈实现队列 | 代码随想录
class MyQueue { public: stack<int> stIn; stack<int> stOut; /** Initialize your data structure here. */ MyQueue() { } /** Push element x to the back of queue. */ void push(int x) { stIn.push(x); } /** Removes the element from in front of queue and returns that element. */ int pop() { // 只有当stOut为空的时候，再从stIn里导入数据（导入stIn全部数据） if (stOut.empty()) { // 从stIn导入数据直到stIn为空 while(!stIn.empty()) { stOut.push(stIn.top()); stIn.pop(); } } int result = stOut.top(); stOut.pop(); return result; } /** Get the front element. */ int peek() { int res = this->pop(); // 直接使用已有的pop函数 stOut.push(res); // 因为pop函数弹出了元素res，所以再添加回去 return res; } /** Returns whether the queue is empty. */ bool empty() { return stIn.empty() && stOut.empty(); } };225 用队列实现栈
题目链接
225. 用队列实现栈 - 力扣（LeetCode）
思路
只用一个队列
文章详解
225. 用队列实现栈 | 代码随想录
class MyStack { public: queue<int> que1; queue<int> que2; // 辅助队列，用来备份 /** Initialize your data structure here. */ MyStack() { } /** Push element x onto stack. */ void push(int x) { que1.push(x); } /** Removes the element on top of the stack and returns that element. */ int pop() { int size = que1.size(); size--; while (size--) { // 将que1 导入que2，但要留下最后一个元素 que2.push(que1.front()); que1.pop(); } int result = que1.front(); // 留下的最后一个元素就是要返回的值 que1.pop(); que1 = que2; // 再将que2赋值给que1 while (!que2.empty()) { // 清空que2 que2.pop(); } return result; } /** Get the top element. ** Can not use back() direactly. */ int top(){ int size = que1.size(); size--; while (size--){ // 将que1 导入que2，但要留下最后一个元素 que2.push(que1.front()); que1.pop(); } int result = que1.front(); // 留下的最后一个元素就是要回返的值 que2.push(que1.front()); // 获取值后将最后一个元素也加入que2中，保持原本的结构不变 que1.pop(); que1 = que2; // 再将que2赋值给que1 while (!que2.empty()){ // 清空que2 que2.pop(); } return result; } /** Returns whether the stack is empty. */ bool empty() { return que1.empty(); } };150 逆波兰表达式求值
题目链接
20. 有效的括号 - 力扣（LeetCode）
思路
利用栈来实现
文章详解
20. 有效的括号 | 代码随想录
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(); // s 与 st.top()相等的情况 } } string result = ""; while (!st.empty()) { // 将栈中元素放到result字符串汇总 result += st.top(); st.pop(); } reverse (result.begin(), result.end()); // 此时字符串需要反转一下 return result; } };