代码随想录算法训练营 第五章 栈与队列part01
** 232.用栈实现队列 **
leetcode链接：https://leetcode.cn/problems/implement-queue-using-stacks/
题目描述：请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：实现 MyQueue 类：1.void push(int x) 将元素 x 推到队列的末尾。2.int pop() 从队列的开头移除并返回元素。3.int peek() 返回队列开头的元素。4.boolean empty() 如果队列为空，返回 true ；否则，返回 false
核心思路：考察栈和队列的操作。
点击查看代码
class MyQueue {
public:stack<int> stIn;stack<int> stOut;MyQueue() {}void push(int x) {stIn.push(x);//入栈，即入队列}int pop() {if(stOut.empty()){//stOut为空while(!stIn.empty()){//stIn不为空stOut.push(stIn.top());//将stIn的栈顶元素加入stOut中stIn.pop();//弹出stIn的栈顶元素}}int result = stOut.top();stOut.pop();return result;}int peek() {int res = this->pop();//this指向类中定义的pop函数，即现有的popstOut.push(res);return res;}bool empty() {return stIn.empty() && stOut.empty();}
};
点击查看代码
class MyStack {
public:queue<int> que1;queue<int> que2;//临时队列MyStack() {}void push(int x) {que1.push(x);}int pop() {int size = que1.size();size--;//最后一个元素不移除while(size--){que2.push(que1.front());//front函数仅读取修改元素，并不删除元素que1.pop();}int result = que1.front();que1.pop();que1 = que2;//将临时队列返回给que1，此时最后一位目标元素已被移除while(!que2.empty()){que2.pop();//如果que2不为空则将其中的元素清除}return result;}int top() {int size = que1.size();size--;//最后一个元素不移除while(size--){que2.push(que1.front());//front函数仅读取修改元素，并不删除元素que1.pop();}int result = que1.front();//存储目标元素que2.push(que1.front());que1.pop();que1 = que2;//将临时队列返回给que1，此时最后一位目标元素已被移除while(!que2.empty()){que2.pop();//如果que2不为空则将其中的元素清除}return result;}bool empty() {return que1.empty() && que2.empty();}
};
点击查看代码
class MyStack {
public:queue<int> que1;//定义单个列表来循环操作队列MyStack() {}void push(int x) {que1.push(x);}int pop() {int size = que1.size() - 1;while(size--){//循环将队列首的元素加入到队列尾，直到遍历到需要的队尾元素。que1.push(que1.front());que1.pop();}int result = que1.front();//存储目标元素后将该元素移除que1.pop();return result;}int top() {int size = que1.size() - 1;while(size--){que1.push(que1.front());que1.pop();}int result = que1.front();//存储目标元素后将该元素加入到队尾que1.push(que1.front());que1.pop();return result;}bool empty() {return que1.empty();}
};
点击查看代码
class Solution {
public:bool isValid(string s) {stack<char> st;if(s.size() % 2 !=0) return false;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('}');//栈空时无法匹配到所需字符，返回false，当字符与栈顶元素不匹配时也返回falseelse if(st.empty() || s[i] != st.top())return false;//顺序不能反，栈空时调用top会报错（未定义）else{st.pop();}}return st.empty();}
};
点击查看代码
class Solution {
public:string removeDuplicates(string s) {stack<char> st;for(char c:s){if(st.empty() || c != st.top()){//这里c不是索引，而是元素st.push(c);}else st.pop();}string result = "";while(!st.empty()){result += st.top();st.pop();}reverse(result.begin(),result.end());//出栈的元素顺序是反的，因此要反转一下。return result;}
};
.)
