232.用栈实现队列
题目链接：https://leetcode.cn/problems/implement-queue-using-stacks/description/
解题思路：用两个栈实现队列，一个入栈，把入栈里面的元素全部放入出栈
代码实现：
点击查看代码
def __init__(self):self.stack_in = [] #入栈，主要负责pushself.stack_out = [] #出栈，主要负责peek(查看栈顶元素),pop（推出栈顶元素）def push(self, x):""":type x: int:rtype: None"""self.stack_in.append(x) #有元素进来，就往in里面pushdef pop(self):""":rtype: int"""if self.empty():return None #先检查队列是否为空if 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"""#先用pop移除并返回首个元素，再把元素压回stack_outans = self.pop() #运用前面自定义的pop函数，检查了self是否为空的情况并移除了stack_out里面的首个元素self.stack_out.append(ans)return ansdef empty(self):""":rtype: bool"""#只要任何一个栈里有元素，就不为空return not (self.stack_in or self.stack_out)
- 用队列实现栈
题目链接：https://leetcode.cn/problems/implement-stack-using-queues/description/
解题思路：用一个队列实现栈，要把最后一个元素先推出。做法：把这个元素前面所有元素先推出然后从末端放回
代码实现：
点击查看代码
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 Nonereturn self.que[-1]def empty(self):""":rtype: bool"""return not self.que
- 有效的括号
题目链接：https://leetcode.cn/problems/valid-parentheses/description/
方法:使用栈进行左右括号的匹配
解题思路：遍历，遇到什么类型的左括号就将对应的右括号添加到栈，遇到右括号就看是否与栈里的右括号相同，相同则弹出。最后会出现三种情况：左右括号不匹配，有多余左括号，有多余右括号。
代码实现：
点击查看代码
stack = []for i in s:if i == '(':stack.append(')')elif i == '[':stack.append(']')elif i == '{':stack.append('}')elif not stack or i != stack[-1]: #遍历过程中出现not stack(栈为空)说明右括号多余return Falseelse:stack.pop()return True if not stack else False #如果最后都消除了，为True,如果还有右括号存在，表明多出了左括号，为False
- 删除字符串中的所有相邻重复项
题目链接：https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/description/
法一：使用栈
思路：用一个栈存储遍历的元素，如果栈为空或遍历的元素和栈内不一样就放入栈，如果遍历的元素和栈内一样就把栈内元素弹出，最后剩下的就是结果字符
代码：
点击查看代码
res = list()for i in s:if res and res[-1] == i:res.pop()else:res.append(i)return ''.join(res) #从列表的第一个元素开始连接字符串
法二：用双指针模拟栈
思路：快慢指针指向起点，快指针遍历的值赋给慢指针，如果遇到值和之前一样的情况则慢指针后退一格，快指针之后遍历的元素覆盖掉此时慢指针指向的元素
代码：
点击查看代码
slow, fast =0, 0res = list(s)while fast < len(res):res[slow] = res[fast]if slow > 0 and res[slow] == res[slow-1]: #slow要有前值才能比较，slow>0,从第二项开始slow -= 1else:slow += 1fast += 1return ''.join(res[:slow]) #最终slow指向末尾的下一个位置，所以索引是0：slow,取不到slow各题手绘示意图：
