[代码随想录Day10打卡] 理论基础 232.用栈实现队列 225. 用队列实现栈 20. 有效的括号 1047. 删除字符串中的所有相邻重复项

理论基础

队列先入先出。
栈先入后出。
具体的实现和用法根据语言的不同而不同。

参考的文章

1. https://programmercarl.com/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

232.用栈实现队列

这个定义入栈和出栈，往队列中加入元素的时候就是栈中push操作一样，出栈的时候首先看出栈是否为空如果不为空那么出栈pop，如果出栈为空那么入栈中所有元素pop然后添加到出栈中。（双栈实现队列）
下面是C++,JAVA和Python的实现。

class MyQueue {
public:stack<int> stIn;stack<int> stOut;MyQueue() {}void push(int x) {stIn.push(x);//队列中加入元素就直接入栈就好    }int pop() {//当出栈为空的时候再将入栈中的元素加入到出栈，不会破坏他们的顺序if (stOut.empty()){//将stIn中的数据导入到stOutwhile(!stIn.empty()){stOut.push(stIn.top());stIn.pop();}}int result = stOut.top();//获得元素值，并且returnstOut.pop();return result;}int peek() {int res = this->pop();//直接使用现有的函数stOut.push(res);//因为pop弹出元素所有push回去return res;}bool empty() {return stIn.empty() && stOut.empty();}
};/*** Your MyQueue object will be instantiated and called as such:* MyQueue* obj = new MyQueue();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->peek();* bool param_4 = obj->empty();*/

class MyQueue {Stack<Integer> stackIn;Stack<Integer> stackOut;public MyQueue() {stackIn = new Stack<>();//负责进栈，JAVA必须new一个空间stackOut = new Stack<>();//负责出栈}//入栈public void push(int x) {stackIn.push(x);//这个就是JAVA的栈}public int pop() {dumpstackIn();//后面自定义的一个函数，这个就是判断出栈是否为空，如果为空就将入栈中的所有元素导入到出栈return stackOut.pop();}public int peek() {dumpstackIn();return stackOut.peek();}public boolean empty() {return stackIn.isEmpty() && stackOut.isEmpty();}public void dumpstackIn(){if (!stackOut.isEmpty()) return;//如果出栈不为空就返回。之后正常pop和peek就可以while(!stackIn.isEmpty()){stackOut.push(stackIn.pop());}}
}/*** Your MyQueue object will be instantiated and called as such:* MyQueue obj = new MyQueue();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.peek();* boolean param_4 = obj.empty();*/

class MyQueue(object):def __init__(self):self.stack_in = []self.stack_out = []def push(self, x):""":type x: int:rtype: None""""""有新元素进来，就往stack_in里面push"""self.stack_in.append(x)def pop(self):""":rtype: int"""if self.empty():return Noneif self.stack_out:return self.stack_out.pop()else:for i in range(len(self.stack_in)):self.stack_out.append(self.stack_in.pop())return self.stack_out.pop()def peek(self):""":rtype: int"""ans = self.pop()self.stack_out.append(ans)return ansdef empty(self):""":rtype: bool"""return not (self.stack_in or self.stack_out)# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

参考的文章

1. https://programmercarl.com/0232.%E7%94%A8%E6%A0%88%E5%AE%9E%E7%8E%B0%E9%98%9F%E5%88%97.html

225. 用队列实现栈

可以和上面方法相同使用两个队列表示栈，也可以使用一个队列表示栈。一个队列就是往栈中加入元素就是队列的push，弹出元素就是找到栈应该弹出的元素移动到队列的最开始然后pop。JAVA中有个实现是在加入元素的时候进行操作，将队列的顺序变成栈的顺序，弹出元素就是pop。
其中JAVA注释掉的没有按照queue来操作而是使用dequeue
下面是C++,JAVA和Python的实现。

class MyStack {
public:queue<int> que;//MyStack() {}void push(int x) {que.push(x);}int pop() {int size = que.size();size--;//弹出其中size-1个元素while(size--){//将队列头部元素（除了最后一个元素外）重新加到队列尾部que.push(que.front());//获得队列中的最前面的元素加入到队列que.pop();//然后弹出}int result = que.front();//弹出的元素正好在队列最前面que.pop();return result;}int top() {return que.back();        }bool empty() {return que.empty();}
};/*** Your MyStack object will be instantiated and called as such:* MyStack* obj = new MyStack();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->top();* bool param_4 = obj->empty();*/

class MyStack {Queue<Integer> queue;public MyStack(){queue = new LinkedList<>();}public void push(int x){//这个思路是在入栈的时候进行操作，每次入栈新元素都调整现有的队列顺序与栈的出栈顺序相同queue.offer(x);//安全与add相比，队列满的话会返回false，不会阻塞等待队列有空间int size = queue.size();//移动除了新加入的元素的其他元素while (size-- > 1)queue.offer(queue.poll());}public int pop(){return queue.poll();}public int top() {return queue.peek();}public boolean empty(){return queue.isEmpty();}// Deque<Integer> deque;//deque是不是双向队列// public MyStack() {//     deque = new ArrayDeque<>();// }// public void push(int x) {//     deque.addLast(x);//在最后加入// }// public int pop() {//     //我感觉这个双向列表完成pop操作可以简化，但是为了练习就是好像当作单向队列，我这里还是当作双向队列//     return deque.removeLast();// }// public int top() {//     return deque.peekLast();// }// public boolean empty() {//     return deque.isEmpty();// }}/*** Your MyStack object will be instantiated and called as such:* MyStack obj = new MyStack();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.top();* boolean param_4 = obj.empty();*/

from collections import deque
class MyStack(object):def __init__(self):self.que = deque()def push(self, x):""":type x: int:rtype: None"""self.que.append(x)def pop(self):""":rtype: int"""if self.empty():return Nonefor i in range(len(self.que)-1):self.que.append(self.que.popleft())return self.que.popleft()def top(self):""":rtype: int"""if self.empty():return Noneans = self.pop()self.que.append(ans)return ansdef empty(self):""":rtype: bool"""return not self.que# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

参考的文章

1. https://programmercarl.com/0225.%E7%94%A8%E9%98%9F%E5%88%97%E5%AE%9E%E7%8E%B0%E6%A0%88.html

20. 有效的括号

栈的应用。
不匹配的情况三种：1. 左括号多了 2. 右括号多了 3. 左右括号不匹配
Tips:就是如果遍历中遇到左括号就往栈中存储相对应的右括号。遇到右括号就进行判断，如果栈为空就说明右括号多了输出false，如果栈的top元素不等于当前的右括号就说明不匹配输出false，其他情况就是说明匹配弹出相应的元素。如果遍历完字符串栈不为空就说明左括号多了输出fa;se，否则就是左右括号匹配输出true。
下面是C++,JAVA和Python的实现。

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

class Solution {public boolean isValid(String s) {Deque<Character> deque = new LinkedList<>();char ch;for(int i = 0; i < s.length(); i++){ch = s.charAt(i);//存储字符进行比较if(ch == '(') deque.push(')');else if(ch == '(') deque.push(')');else if(ch == '{') deque.push('}');else if(ch == '[') deque.push(']');else if(deque.isEmpty() || deque.peek()!=ch){return false;}else deque.pop();}return deque.isEmpty();}
}

class Solution(object):def isValid(self, s):""":type s: str:rtype: bool"""stack = []for item in s:if item == '(':stack.append(')')elif item == '[':stack.append(']')elif item == '{':stack.append('}')elif not stack or stack[-1]!=item:return Falseelse:stack.pop()return True if not stack else False 

参考的文章

1. https://programmercarl.com/0020.%E6%9C%89%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7.html

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

栈的应用。与有效括号类似。
就是使用string类型变量实现栈的操作。定义string类型变量result。
如果result为空或者result的栈顶的元素与当前元素不匹配就将当前元素push到栈中。如果匹配就pop。遍历结束后输出result。
下面是C++,JAVA和Python的实现。

class Solution {
public:string removeDuplicates(string S) {string result;for (char s: S){if(result.empty() || s!=result.back()) result.push_back(s);else result.pop_back();}return result;}
};

class Solution {public String removeDuplicates(String S) {ArrayDeque<Character> deque = new ArrayDeque<>();char ch;for (int i = 0; i < S.length(); i++){ch = S.charAt(i);if(deque.isEmpty() || deque.peek() != ch) deque.push(ch);else deque.pop();}String str = "";while(!deque.isEmpty()){str = deque.pop()+ str;}return str;}}

class Solution(object):def removeDuplicates(self, s):""":type s: str:rtype: str"""res = list()for item in s:if res and res[-1] == item:res.pop()else:res.append(item)return "".join(res)

参考的文章

1. https://programmercarl.com/1047.%E5%88%A0%E9%99%A4%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%AD%E7%9A%84%E6%89%80%E6%9C%89%E7%9B%B8%E9%82%BB%E9%87%8D%E5%A4%8D%E9%A1%B9.html