图书整理 II

难度: Easy

读者来到图书馆排队借还书，图书管理员使用两个书车来完成整理借还书的任务。书车中的书从下往上叠加存放，图书管理员每次只能拿取书车顶部的书。排队的读者会有两种操作：

push(bookID)：把借阅的书籍还到图书馆。
pop()：从图书馆中借出书籍。

为了保持图书的顺序，图书管理员每次取出供读者借阅的书籍是最早归还到图书馆的书籍。你需要返回 每次读者借出书的值 。

如果没有归还的书可以取出，返回 -1 。

示例 1：

输入：
["BookQueue", "push", "push", "pop"]
[[], [1], [2], []]
输出：[null,null,null,1]
解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.pop(); // return 1, queue is [2]

提示：

1 <= bookID <= 10000
最多会对 push、pop 进行 10000 次调用

Submission

运行时间: 2268 ms

内存: 16.6 MB

class CQueue:

    def __init__(self):
        self.stack1 = list()
        self.stack2 = list()

    def appendTail(self, value: int) -> None:
        while self.stack1:
            self.stack2.append(self.stack1.pop())
        self.stack1.append(value)
        while self.stack2:
            self.stack1.append(self.stack2.pop())

    def deleteHead(self) -> int:
        if not self.stack1:
            return -1
        return self.stack1.pop()

# Your CQueue object will be instantiated and called as such:
# obj = CQueue()
# obj.appendTail(value)
# param_2 = obj.deleteHead()

Explain

这个问题的核心是使用两个栈(stack1和stack2)来模拟一个队列的操作。栈是后进先出的数据结构，而队列是先进先出的。为了实现队列的从头部删除元素的操作，我们可以利用两个栈的特性来逆转元素的顺序： 1. 当需要在队列尾部添加一个元素时，将stack1中的所有元素转移到stack2中（这将逆转这些元素的顺序），然后将新元素放入stack1中，最后将stack2中的所有元素再次转移回stack1中，这样新元素就位于stack1的底部，符合队列的顺序。 2. 当需要从队列头部删除元素时，直接从stack1中弹出顶部的元素即可，因为根据上述操作，stack1的顶部元素是最早进入的元素，符合队列的操作。

时间复杂度: 摊销O(1)

空间复杂度: O(n)

# 定义CQueue类

class CQueue:

    # 初始化两个栈
    def __init__(self):
        self.stack1 = list()  # 主栈
        self.stack2 = list()  # 辅助栈

    # 在队列尾部添加元素
    def appendTail(self, value: int) -> None:
        # 将stack1中的所有元素移到stack2中
        while self.stack1:
            self.stack2.append(self.stack1.pop())
        # 将新元素添加到stack1中
        self.stack1.append(value)
        # 将stack2中的所有元素移回stack1中
        while self.stack2:
            self.stack1.append(self.stack2.pop())

    # 从队列头部删除元素
    def deleteHead(self) -> int:
        # 如果stack1为空，则返回-1
        if not self.stack1:
            return -1
        # 否则，弹出并返回stack1的顶部元素
        return self.stack1.pop()

# 使用CQueue对象时，可以这样实例化和调用方法
# obj = CQueue()
# obj.appendTail(value)
# param_2 = obj.deleteHead()

Explore

这样做主要是为了保持队列元素的先进先出(FIFO)顺序。栈是后进先出(LIFO)的数据结构，直接将元素加入栈顶会导致顺序颠倒。通过将stack1的元素移至stack2，我们实际上是将stack1的底部变为顶部，这样新加入的元素放在stack1空栈后，再将stack2的元素（原stack1的元素）按原顺序放回stack1，确保了新元素在队列的末尾，从而模拟了队列的行为。

当stack1为空时，返回-1是一种常用的处理方式，表示队列中没有元素可供删除。这种处理方式通常需要客户端代码检查`deleteHead`方法的返回值，以判断是否成功删除了元素或者队列已经空了。在实际应用中，可以根据具体需求引入异常处理或其他逻辑来更明确地处理这种空队列的情况。

元素的这种重复移动确实会增加操作的时间复杂度，尤其是在元素数量较多时。一个更优化的方法是使用两个栈，但采取不同的策略：在`appendTail`时直接将元素推入stack1；在`deleteHead`时，只有当stack2为空时，才将stack1中的所有元素转移到stack2中，并从stack2中进行删除操作。这种方法可以显著减少元素的移动次数，因为元素仅在必要时才从stack1移动到stack2。

在高频率操作的环境中，两栈模拟队列可能会因为频繁的元素转移导致性能问题。特别是在极端情况下，如连续多次进行插入操作后紧接着进行多次删除操作，这会导致大量的元素移动。此外，这种方法也会占用比单个队列更多的内存空间，因为它需要两个栈来存储数据。设计时需要权衡这种方法的性能与内存使用，并考虑是否适用于特定的应用场景。