用栈实现队列

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

MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek();  // 返回 1
queue.pop();   // 返回 1
queue.empty(); // 返回 false

说明:
你只能使用标准的栈操作 – 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
假设所有操作都是有效的（例如，一个空的队列不会调用 pop 或者 peek 操作）。

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 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) -> int:
        result = self.pop()
        self.stack_out.append(result)
        return result

    def empty(self) -> bool:
        return not  (self.stack_in or self.stack_out)

由于栈是先进后出，队列是先进先出，所以需要两个栈来实现队列的功能。实现负负得正。
然后查看头节点可以用出队列的代码复用，得到后记得再入栈

用队列实现栈

题目链接

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

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

注意:

你只能使用队列的基本操作– 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
你所使用的语言也许不支持队列。你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

class MyStack:

    def __init__(self):
        self.deq = deque()

    def push(self, x: int) -> None:
        self.deq.append(x)

    def pop(self) -> int:
        if self.empty():
            return None
        else :
            for i in range(len(self.deq)-1):
                self.deq.append(self.deq.popleft())
            return self.deq.popleft()

    def top(self) -> int:
        if self.empty():
            return None
        return self.deq[-1]

    def empty(self) -> bool:
        return not self.deq

使用一个队列来实现栈的功能。入栈直接入队列即可。出栈需要将队列中的元素依次出队列再入队列，直到只剩下最后一个元素，这个元素就是栈顶元素，直接出队列即可。

有效的括号

题目链接

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

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

1 2	输入：s = "()" 输出：true

示例 2：

1 2	输入：s = "()[]{}" 输出：true

示例 3：

1 2	输入：s = "(]" 输出：false

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        if len(s) %2 == 1:
            return False
        for i in s:
            if i == "(":
                stack.append(")")
            elif i == "[":
                stack.append("]")
            elif i == '{':
                stack.append("}")
            elif not stack or i != stack[-1]:
                return False
            else:
                stack.pop()
        return True  if not stack else False

这道题是用栈来实现的，遍历字符串，遇到左括号就入栈，遇到右括号就出栈，判断是否匹配。提前为空、栈顶元素不匹配、字符串遍历完成后栈不为空，这三种情况都是无效的。
我遇到了一个很有意思的错误elif not stack or i != stack.pop():
原先我的代码是这样的，但是报错确实在十六行告诉我空栈不能pop，我原本以为是因为python的判断条件是左右会都判断，哪怕左边已经为真了，但其实问题是我在判断栈顶元素是否匹配时，直接用了pop方法，提前把最后一元素出栈这会导致栈为空后续没法pop。

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

题目链接

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：
输入：”abbaca”
输出：”ca”
解释：例如，在 “abbaca” 中，我们可以删除 “bb” 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。
之后我们得到字符串 “aaca”，其中又只有 “aa” 可以执行重复项删除操作，所以最后的字符串为 “ca”。
提示：
1 <= S.length <= 20000
S 仅由小写英文字母组成。

class Solution:
    def removeDuplicates(self, s: str) -> str:
        stack = []
        for i in s:
            if stack and i == stack[-1]:
                stack.pop()
            else :
                stack.append(i)
        return "".join(stack)