【刷题16】有效的括号、用栈实现队列、用队列实现栈

一、有效的括号

题目：

思路：栈

• 是左括号就入栈，是右括号就进行比较，取栈顶的左括号
• 如果比较的过程中（是右括号），栈为空，说明没有左括号了，就返回false
• 如果比较的左右括号不匹配，返回false。注意：每次取栈顶元素，记得pop
• 所有的字符遍历完，如果栈不为空，说明有多余的左括号，返回false
• 没有以上的错误情况，最后返回true

代码：

class Solution {
public:bool isValid(string s) {stack<char> st;for(auto &str : s){// 只要是左括号入栈if(str == '(' || str == '[' || str == '{'){st.push(str);}// 右括号要比较else {if(st.empty()) return false;// 没有左括号进行匹配char ch = st.top();st.pop();// 匹配不对if(ch == '(' && str != ')' || ch == '[' && str != ']'|| ch == '{' && str != '}')return false;}}if(!st.empty()) return false;// 还有多余的左括号return true;}
};

二、用栈实现队列

题目：

思路：两个栈实现队列

• 定义两个栈，一个为in，一个为out，in负责进数据，out负责出数据
• push：往in里面放入数据
• pop：先判断out里面也没有元素，有元素返回该元素并删除；没有的话从in里面获取数据，然后取栈顶元素并删除
• peek：与pop的思路一样，只是不需要删除，返回元素即可，过程是一样的
• empty：两个栈都为空才返回true，否则返回false

代码：

class MyQueue {
public:stack<int> in, out;MyQueue() {}void push(int x) {in.push(x);}int pop() {if(!out.empty()) {int ret = out.top();out.pop();return ret;}while(!in.empty()){int k = in.top();in.pop();out.push(k);}int ret = out.top();out.pop();return ret;}int peek() {if(!out.empty()) return out.top();while(!in.empty()){int k = in.top();in.pop();out.push(k);}return out.top();}bool empty() {if(out.empty() && in.empty()) return true;else return false;}
};

三、用队列实现栈

题目：

思路：一个队列实现栈

• push：往队列放入数据
• pop：队列有size个元素，循环操作size-1次，将队列的队头元素重新入队列尾，删除该队头，这样原来队列的最后一个元素就变成队头了，然后返回该元素并删除
• top：思路与pop一样，但是记得最后不能只返回队头元素，还要和还原回去原来的队列顺序，即原来的第一个元素还在第一个位置，第二个还在第二个位置
• empty：队列为空返回true，否则返回false

代码：

class MyStack {
public:queue<int> que;MyStack() {}void push(int x) {que.push(x);}   int pop() {int t = que.size();while(--t){int k = que.front();que.push(k);que.pop();}int ret = que.front();que.pop();return ret;}int top() {int t = que.size();while(--t){int k = que.front();que.push(k);que.pop();}int ret = que.front();que.push(ret);// 记得还原回去！que.pop();return ret;}bool empty() {if(que.empty()) return true;else return false;}
};