今日任务：

1. 栈与队列理论基础
2. LeetCode232 用栈实现队列
3. LeetCode225 用队列实现栈

今日心情：开始女娲补天（）

资料来源：

1. Python deque用法介绍
2. 代码随想录 | 栈与队列理论基础
3. 代码随想录 | LeetCode232 用栈实现队列
4. 代码随想录 | LeetCode225 用队列实现栈

1 栈与队列理论基础

python中常用的类似栈与队列的数据结构为deque（from collections import deque）双端队列。

• 如果要作为栈使用，那么可用的api有入栈（append）、出栈（pop）。
• 如果要作为队列使用，那么可用的api有入队（append）、出队（popleft）。
• 作为双端队列来说，appendleft也是有的。
• 它还支持使用可迭代对象（字符串、列表灯）一次添加多个元素（extend，extendleft）。
• 它可以在初始化时通过指定maxlen属性来指定双端队列的长度（deque(maxlen=5)）。
• 它还支持指定索引查询（index）、计数元素个数（count）、指定元素删除（remove）、清空（clear）、复制（copy）、反转（reverse）和指定次数进行轮转（rotate）。

2 LeetCode232 用栈实现队列

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

如果是硬模拟的话，那一个栈主要存元素，另一个栈用于在取出头元素时，从存元素的栈中倒腾出元素。这样的话push和empty就简单了，直接看那一个栈就行；pop和peek需要倒两次元素。

python
# 我的代码
from collections import deque

class MyQueue:

    def __init__(self):
        self.stack1 = deque()
        self.stack2 = deque()
        # 可用操作：压栈append 出栈pop 求长度len 判断是否全部为空

    # 进入队尾
    def push(self, x: int) -> None:
        self.stack1.append(x)


    # 出队
    def pop(self) -> int:
        while len(self.stack1) != 1:
            self.stack2.append(self.stack1.pop())
        result = self.stack1.pop()
        while len(self.stack2) != 0:
            self.stack1.append(self.stack2.pop())
        return result


    # 查看队列首个元素
    def peek(self) -> int:
        while len(self.stack1) != 1:
            self.stack2.append(self.stack1.pop())
        result = self.stack1.pop()
        self.stack1.append(result)
        while len(self.stack2) != 0:
            self.stack1.append(self.stack2.pop())
        return result


    # 队列是否为空
    def empty(self) -> bool:
        if len(self.stack1) == 0:
            return True
        return False

正常模拟方法可以看成将两个栈底对底拼起来来模拟一个队列的所有行为。

python
from collections import deque

class MyQueue:

    def __init__(self):
        self.stack_in = deque()
        self.stack_out = deque()
        # 可用操作：压栈append 出栈pop 求长度len 判断是否全部为空

    # 进入队尾
    def push(self, x: int) -> None:
        self.stack_in.append(x)

    # 出队
    def pop(self, out: bool = True) -> int:
        if len(self.stack_out) == 0:
            while len(self.stack_in) != 0:
                self.stack_out.append(self.stack_in.pop())
        if out:
            return self.stack_out.pop()
        else:
            num = self.stack_out.pop()
            self.stack_out.append(num)
            return num

    # 查看队列首个元素
    def peek(self) -> int:
        # 这里提醒我了 可以对pop进行抽象 用默认值来设置函数参数
        return self.pop(False)

    # 队列是否为空
    def empty(self) -> bool:
        if len(self.stack_in) == 0 and len(self.stack_out) == 0:
            return True
        return False

3 LeetCode225 用队列实现栈

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

任务文档提醒我了，队列可以只用一个，没这一句的话我还真的会用两个队列去写。入栈和判空不说了，主要是出栈。出栈的原理就是队列的轮转，出队的元素可以再入队回到队尾，将队列中的除了最后一个元素的其他元素进行轮转，下一个要出队的元素就是要出栈的元素了。

python
from collections import deque


class MyStack:

    def __init__(self):
        self.queue = deque()
        # 队列允许的操作：入队append 出队popleft 求队列长度

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

    def pop(self, out: bool = True) -> int:
        for _ in range(len(self.queue) - 1):
            self.queue.append(self.queue.popleft())
        if out is True:
            return self.queue.popleft()
        num = self.queue.popleft()
        self.queue.append(num)
        return num

    def top(self) -> int:
        return self.pop(False)

    def empty(self) -> bool:
        if len(self.queue) == 0:
            return True
        return False