栈（Stack）和队列（Queue）是两种基本的数据结构，它们的思想在日常生活中的许多场景中都有体现。

栈（Stack）的思想应用：

1. 书堆：书桌上的书堆是栈的一个直观例子。你总是放下（push）一本新书在最上面，当需要一本书时，你会从顶部取走（pop）书，这是一个后进先出（LIFO）的过程。
2. 浏览器的后退按钮：浏览过的网页地址被存储在一个栈中。每当你访问一个新网页，它就被“压入”这个栈。点击后退按钮时，最近访问的网页被“弹出”，显示前一个网页。
3. 撤销（Undo）功能：在文本编辑器中，每次编辑操作（如输入、删除）都被存储在一个栈中。当你执行撤销操作时，最近的编辑动作被撤销，这也是一个后进先出的过程。

队列（Queue）的思想应用：

1. 排队购票：在电影院或音乐会购票处排队时，第一个排队的人将是第一个买到票并离开的。这是一个先进先出（FIFO）的过程。
2. 打印任务队列：在办公室，多个人可能同时向同一台打印机发送打印任务。这些任务按照它们到达打印机的顺序被处理，形成了一个队列。
3. 呼叫中心：在客服中心，来电被放入队列中，客服人员按照来电的顺序接听电话。这确保了第一个呼叫的客户将是第一个被服务的。

232.用栈实现队列

得用两个栈，一个入队列一个出队列

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

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

初始状态

• stack_in = []
• stack_out = []

执行push(x)

• stack_in = [x]（将x压入stack_in）
• stack_out = []

执行push(y)

• stack_in = [x, y]（y入栈到stack_in，放在x之上）
• stack_out = []

执行peek()

1. 首先检查stack_out是否为空，是的话，将stack_in的元素逆序转移到stack_out中。转移后，stack_in为空，而stack_out按照stack_in的逆序存放之前的元素。转移前：stack_in = []stack_out = [y, x]（x是队列前端元素）
2. 然后从stack_out中pop出栈顶元素（此时为x），这是peek操作想要查看的队列前端元素。
3. 由于是peek操作，需要将弹出的元素（x）再次放回stack_out，以保持队列状态不变。操作后：stack_in = []stack_out = [x, y]（x再次被放回）

执行pop()

1. 如果stack_out非空（此时是[x, y]），直接从stack_out中pop出栈顶元素（此时为x），即为执行pop操作移除的队列前端元素。操作后：stack_in = []stack_out = [y]（x被移除）

执行empty()

1. 检查stack_in和stack_out是否都为空。在此步骤中，stack_in确实为空，但stack_out包含元素[y]，因此队列不为空。最终状态：stack_in = []stack_out = [y]

总结

通过这系列操作，我们可以看到stack_in主要用于处理新元素的入队操作，而stack_out主要用于出队操作。通过在pop和peek操作中适当地将元素从一个栈转移到另一个栈，这种设计成功地用两个栈模拟了队列的先进先出（FIFO）特性。

225. 用队列实现栈

from collections import deque

class MyStack:

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

    def push(self, x: int) -> None:
        # 使用append方法向deque的末尾添加元素，模拟栈的push操作
        self.stack.append(x)

    def pop(self) -> int:
        # 如果栈不为空，则使用pop方法移除并返回deque的最后一个元素，模拟栈的pop操作
        if not self.empty():
            return self.stack.pop()
        return None

    def top(self) -> int:
        # 如果栈不为空，返回deque的最后一个元素，但不移除它，模拟栈的top操作
        if not self.empty():
            return self.stack[-1]
        return None

    def empty(self) -> bool:
        # 如果deque为空，则返回True，表示栈为空；否则返回False
        return not self.stack

deque（双端队列）是Python中collections模块提供的一种数据结构。它支持从两端快速添加（push）和移除（pop）元素，因此非常适合用作栈（Stack）和队列（Queue）。下面详细介绍deque的一些常用操作和用法。

deque用法

创建deque

首先，需要从collections模块中导入deque：

from collections import deque

然后，可以创建一个空的deque，或者使用一个可迭代对象（如列表）初始化deque：

d = deque()  # 创建一个空的deque
d = deque([1, 2, 3])  # 使用列表初始化deque

向deque添加元素

• append: 在deque的右端添加一个元素。
• appendleft: 在deque的左端添加一个元素。

从deque中移除元素

• pop: 移除并返回deque的右端元素。
• popleft: 移除并返回deque的左端元素。

访问元素

直接使用索引访问deque中的元素：

first_element = d[0]  # 访问第一个元素
last_element = d[-1]  # 访问最后一个元素

deque的其他常用操作

• extend: 在deque的右端一次性添加多个元素。
• extendleft: 在deque的左端一次性添加多个元素。注意，添加的序列元素将会反序出现在deque的左端。
• rotate: 向右旋转deque中的元素。如果参数为负数，则向左旋转。
• clear: 清空deque中的所有元素。
• maxlen: 创建deque时可以指定一个最大长度。一旦达到这个长度，新添加的元素会导致相反端的元素被移除。

总结

deque是一个非常灵活的数据结构，适用于需要从两端操作数据的场景。由于deque支持O(1)时间复杂度的元素添加和移除操作，它比使用Python列表实现栈或队列更加高效。