任务
232. 用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）
思路
算是一个模拟类的题目，用py中，用列表加上限制条件表示栈（只能用pop表示对栈顶元素出栈处理)
- push：用stackIn保存入队元素
- pop： 出队时，分三种情况，
- 如果队列为空，则返回None
- 如果stackOut中还有元素，则弹出栈顶元素
- 如果stackOut中没有元素，则将stackIn中的元素依次弹出并加入到stackOut栈中，全部完成后，弹出stackOut栈顶元素
- peek: 弹出stackOut栈顶元素并保存其值，然后重新加入栈顶，返回之前保存的值
- empty: 只有stackOut和stackIn全为空，才为空
class MyQueue:
def __init__(self):
self.stackIn = []
self.stackOut = []
def push(self, x: int) -> None:
self.stackIn.append(x)
def pop(self) -> int:
if self.empty(): return None
if self.stackOut: return self.stackOut.pop()
else:
while self.stackIn:
self.stackOut.append(self.stackIn.pop())
return self.stackOut.pop()
def peek(self) -> int:
res = self.pop()
self.stackOut.append(res)
return res
def empty(self) -> bool:
return (not self.stackIn and not self.stackOut)
# 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()
225. 用队列实现栈
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）
思路
两个队列的思路类似上一题，实际只需要一个队列即可。此外，由于用py实现，如果用List模拟队列，移除时需要pop(1),时间复杂度为O(n)，因此用deque和popleft代替来模拟队列。
思路时出栈时，实际就是将队列的前n-1个元素放到队尾，再弹出队列首元素即可。而top更简单栈顶元素即为队尾元素。
class MyStack:
def __init__(self):
self.queue = deque()
def push(self, x: int) -> None:
self.queue.append(x)
def pop(self) -> int:
if self.empty():return None
for i in range(len(self.queue)-1):
self.queue.append(self.queue.popleft())
return self.queue.popleft()
#这种方法虽然能实现，由于是双端队列，访问末尾时间复杂度上也不会有问题，但是若当作普通队列模拟，则可采用top2的方法
#实际py中没必要，实现是为了其他语言且题意要求用普通队列的情况下
def top(self) -> int:
if self.empty():return None
return self.queue[-1]
def top2(self)->int:
res = self.pop()
self.queue.append(res)
return res
def empty(self) -> bool:
return not self.queue
# 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()
20. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
遍历过程中，用栈存储左括号，右括号依次匹配最近的左括号
遍历过程中无效分三种情况
class Solution:
def isValid(self, s: str) -> bool:
stack = []
for c in s:
if c == '(':
stack.append(')')
elif c == '{':
stack.append('}')
elif c == '[':
stack.append(']')
elif(not stack or stack[-1] != c): #第2，3种情况
return False
else: stack.pop()
# elif c == ')': #冗余的写法
# if stack and stack[-1] == ')':
# stack.pop()
# else:
# return False
# elif c == ']':
# if stack and stack[-1] == ']':
# stack.pop()
# else:
# return False
# elif c == '}':
# if stack and stack[-1] = '}':
# stack.pop()
# else:
# return False
return not stack
1047. 删除字符串中的所有相邻重复项
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
思路
按照上述逻辑用栈模拟即可，符合条件的就加入栈中，否则就移除。最终得到一个字符栈，由栈底到栈顶的顺序的字符组成即为所求字符串，又因为py是中用List模拟的栈，因此很方便地直接将List转为str即可（对于栈已经是逆序的）
如果是其他语言如CPP，需要将栈元素弹出并且拼接到字符串上，还需要反转。
class Solution:
def removeDuplicates(self, s: str) -> str:
stack = []
for c in s:
# if not stack: #栈为空时
# stack.append(c)
# elif stack and stack[-1] != c:#栈不为空且当前元素不等于栈顶元素
# stack.append(c)
# else:
# stack.pop()
if stack and stack[-1] == c:
stack.pop()
else:
stack.append(c)
return ''.join(stack)
心得体会
栈和队列的题目中，主要是想到用栈或队列解决问题后，动手模拟一下遍历过程中，栈或者队列的变化情况。在py中，用列表提供有限的操作模拟栈，比如只能访问栈顶,只能添加移除栈顶元素，均是在列表末尾进行操作（[-1],append,pop），由于列表删除最前面的值时间复杂度为O(N),所以使用deque双端队列，如果模拟的是普通队列，只能从尾进头出（append,popleft），访问首元素等（[0])。
此外，栈常常用于匹配最近元素或者刚刚访问过的元素等，如括号匹配和删除字符串中的重复元素。