前言
今天是算法训练营的第十天，到这里大概已经过了六分之一了，希望后面的时间继续保持打卡学习。
今天的题目主要是对栈和队列的一些简单经典应用，总体来说难度还行。
232.用栈实现队列
题目链接：232. 用栈实现队列
题目描述：
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（
push、pop、peek、empty）：实现
MyQueue类：
void push(int x)将元素 x 推到队列的末尾int pop()从队列的开头移除并返回元素int peek()返回队列开头的元素boolean empty()如果队列为空，返回true；否则，返回false
思路
这道题主要是用来巩固对于栈和队列的理论知识掌握，用栈模拟队列行为需要使用到两个栈：一个输入栈、一个输出栈。
由于栈是先进后出，而队列是先进先出，总体模拟思路是输入照旧进入输入栈，如果有输出需求时，就将输入栈目前所有元素填入输出栈。输入栈中元素出栈后立刻进入输出栈，这样就能使得最先进输入栈的元素最后进输出栈，如此操作后输出栈中第一个出栈的元素将会是第一个进入输入栈的元素。这样一来，我们就实现了先进先出的操作。
代码实现
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:
for i in range(len(self.stackin)):
self.stackout.append(self.stackin.pop())
return self.stackout.pop()
def peek(self) -> int:
ans = self.pop()
self.stackout.append(ans)
return ans
def empty(self) -> bool:
return not (self.stackin or self.stackout)225.用队列实现栈
题目链接：225. 用队列实现栈
题目描述：
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（
push、top、pop和empty）。实现
MyStack类：
void push(int x)将元素 x 压入栈顶。int pop()移除并返回栈顶元素。int top()返回栈顶元素。boolean empty()如果栈是空的，返回true；否则，返回false。
思路
这道题依旧是用来巩固对栈和队列的熟悉程度，不过这道题可以使用一个队列就模拟出栈的特点。
由于队列是先进先出，而栈是先进后出，那么我们的主要任务就是让队列弹出元素每次都是弹出队列中最后一个元素。为了实现这个操作，我们可以在每次需要弹出元素时都将除了最后一个元素以外的前面所有元素都原地出队列再进队列，一个循环之后就能将最后一个元素顶到头上，这样一来尽管还是左边弹出，但我们已经实现了先进后出。
实现写法
class MyStack:
def __init__(self):
self.que = deque()
def push(self, x: int) -> None:
self.que.append(x)
def pop(self) -> int:
if self.empty():
return None
for i in range(len(self.que) - 1):
self.que.append(self.que.popleft())
return self.que.popleft()
def top(self) -> int:
if self.empty():
return None
for i in range(len(self.que) - 1):
self.que.append(self.que.popleft())
temp = self.que.popleft()
self.que.append(temp)
return temp
def empty(self) -> bool:
return not self.que
20.有效的括号
题目链接：20. 有效的括号
题目描述：
给定一个只包括
'('，')'，'{'，'}'，'['，']'的字符串s，判断字符串是否有效。有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
思路
这道题很早只前有接触过，是栈的一道经典应用。
总体思路大致是遍历字符串，在遇到左括号时将对应的右括号压入栈中；当遇到右括号时，检查目前的栈顶元素和该右括号是否相同，如果相同就弹出，不相同返回False.
遍历结束后，如果栈为空那么说明匹配成功返回True，否则False。
实现写法
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.pop() != c:
return False
return not stack1047.删除字符串中的所有相邻重复项
题目链接：1047. 删除字符串中的所有相邻重复项
题目描述：
给出由小写字母组成的字符串
s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。在
s上反复执行重复项删除操作，直到无法继续删除。在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
思路
这题给我感觉有点像某种三消游戏，像祖玛吐到三个球然后后续一直接上三个球消除。
总体思想大致遍历字符串，将字符串元素加入进栈中，然后比较后续字符和栈顶字符是否相同，如果相同就栈顶元素出栈，不相同就加入栈顶。
具体实现
class Solution:
def removeDuplicates(self, s: str) -> str:
res = list()
for item in s:
if res and res[-1] == item:
res.pop()
else:
res.append(item)
return "".join(res) 总结
今天主要是让我们熟悉栈和队列的基本概念，利用基本概念解决一些简单操作，不过讲真还是有一定思维量的，今天的题目让我开始意识到栈这一结构实际上在很多实际问题中非常重要。
