【CV炼丹师勇闯力扣训练营 Day10】

使用栈实现队列的下列操作：
push(x) – 将一个元素放入队列的尾部。
pop() – 从队列首部移除元素。
peek() – 返回队列首部的元素。
empty() – 返回队列是否为空。

【示例】
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.push(3);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false

【思路】用一个输入栈，一个输出栈模拟队列
【注意】在push数据的时候，只要数据放进输入栈就好，但在pop的时候，操作就复杂一些，输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据，如果输出栈不为空，则直接从出栈弹出数据就可以了。最后如何判断队列为空呢？如果进栈和出栈都为空的话，说明模拟的队列为空了。

代码如下（Python）：

class MyQueue:def __init__(self):self.stack_in = []  # 进栈self.stack_out = []  # 出栈def push(self, x: int) -> None:self.stack_in.append(x)def pop(self) -> int:if self.empty():  # 先判断进栈和出栈是否都为空return Noneif self.stack_out:  # 判断出栈是否不为空，若不为空，直接popreturn self.stack_out.pop()else:for i in range(len(self.stack_in)):  # 若进栈不空，出栈为空，则先进栈pop填充出栈，再出栈popself.stack_out.append(self.stack_in.pop())  # stack_out: [3,2,1]return self.stack_out.pop()  # 弹出1 stack_out: [3,2]def peek(self) -> int:# 返回队列前端的元素(即下一次要弹出的元素)，而不对队列进行任何修改ans = self.pop()self.stack_out.append(ans)  # 将弹出的1补回去, stack_out: [3,2,1]return ans  # 1def empty(self) -> bool:# 判断队列是否为空return not (self.stack_in or self.stack_out)MQ = MyQueue()
MQ.push(1)
MQ.push(2)
MQ.push(3)
print(MQ.stack_in)  # [1,2,3]
print(MQ.peek())  # 1
print(MQ.stack_out)  # [3,2,1]

使用队列实现栈的下列操作：

push(x) – 元素 x 入栈
pop() – 移除栈顶元素
top() – 获取栈顶元素
empty() – 返回栈是否为空

【思路1】用两个队列模拟栈，只不过这两个栈不是分别用于进出，第二个栈只用于备份
【思路2】用一个队列模拟栈

代码如下（Python）：

from collections import dequeclass 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 Nonefor i in range(len(self.que)-1):  # [3,2,1] -> [2,1,3]self.que.append(self.que.popleft())print(self.que)  # deque([3, 1, 2])return self.que.popleft()  # 弹出3def top(self) -> int:# 写法一：# if self.empty():#     return None# return self.que[-1]# 写法二：if self.empty():return Nonefor i in range(len(self.que)-1):self.que.append(self.que.popleft())temp = self.que.popleft()self.que.append(temp)return tempdef empty(self) -> bool:return not self.que# Your MyStack object will be instantiated and called as such:
obj = MyStack()
obj.push(1)
obj.push(2)
obj.push(3)
print(obj.que)  # deque([1, 2, 3])
param_2 = obj.pop()
print(obj.que)  # deque([1, 2])
param_3 = obj.top()  # 2
param_4 = obj.empty()

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：
输入：s = “()”
输出：true

示例 2：
输入：s = “()[]{}”
输出：true

示例 3：
输入：s = “(]”
输出：false

由于栈结构的特殊性，非常适合做对称匹配类的题目。
【不匹配的情况】
①字符串里左方向的括号多余了，所以不匹配
②括号没有多余，但是括号的类型没有匹配上
③字符串里右方向的括号多余了，所以不匹配
【思路】字符串遍历完之后，栈是空的，就说明全都匹配了

代码如下(Python)：

class Solution:def isValid(self, s: str) -> 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 False  # ①item没空，stack空了：右边多了 ②不匹配else:stack.pop()  # 匹配return True if not stack else False  # ③item空了，stack没空：左边多了

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：
输入：“abbaca”
输出：“ca”

解释：
例如，在 “abbaca” 中，我们可以删除 “bb” 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”，其中又只有 “aa” 可以执行重复项删除操作，所以最后的字符串为 “ca”。

【思路】匹配相邻元素，本质也是消消乐，用栈来解决。栈中存放遍历过的元素，当遍历当前的这个元素的时候，去栈里看一下我们是不是遍历过相同数值的相邻元素，然后再去做对应的消除操作

从栈中弹出剩余元素，此时是字符串ac，因为从栈里弹出的元素是倒序的，所以再对字符串进行反转一下，就得到了最终的结果。

代码如下(Python)：

# 方法一，使用栈
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)  # 否则入栈# ['c', 'a'] -> careturn "".join(res)  # 字符串列表拼接# 方法二，使用双指针模拟栈，如果不让用栈可以作为备选方法。
class Solution1:def removeDuplicates(self, s: str) -> str:res = list(s)slow = fast = 0length = len(res)while fast < length:# 如果一样直接换，不一样会把后面的填在slow的位置res[slow] = res[fast]# 如果发现和前一个一样，就退一格指针if slow > 0 and res[slow] == res[slow - 1]:slow -= 1else:slow += 1fast += 1return ''.join(res[0: slow])S = Solution()
print(S.removeDuplicates("abbaca"))