Python中的Deque是如何工作的

Question

我在尝试用Python重新创建队列和栈时，对下面代码片段中deque的工作原理感到困惑。

栈示例-已理解

stack = ["a", "b", "c"]

# push operation
stack.append("e")
print(stack)

# pop operation
stack.pop()
print(stack)

按照预期，当进行推入(push)和弹出(pop)操作时，"e"会先进后出(LIFO)。我的问题是针对下面的示例。

队列示例-不理解

from collections import deque

dq = deque(['a','b','c'])
print(dq)

# push
dq.append('e')
print(dq)

# pop
dq.pop()
print(dq)

在进行推送和弹出操作时，“e”是后进先出（LIFO）的。难道不应该是先进先出（FIFO）吗？

- Victor Rodriguez

---

你应该查看 deque 文档。你可能正在寻找 dq.popleft()（或 .appendleft()）。无论哪种情况，"de" 在 dequeue 中代表 "double-ended"。 - jedwards

为什么应该有所不同呢？ - zondo

Answer 1

双向队列是栈和队列的一种泛化数据结构（它的缩写是“double-ended queue”）。

因此，pop() 操作仍然使其像堆栈一样工作，就像在列表中使用时一样。 要使其像队列一样工作，使用 popleft() 命令。 双向队列被设计支持这两种行为，这样 pop() 函数在数据结构之间具有一致性。 为了使双向队列像队列一样工作，必须使用与队列相对应的函数。 因此，在第二个示例中将 pop() 替换为 popleft() ，您应该可以看到您预期的FIFO行为。

双向队列还支持最大长度，这意味着当您向双向队列添加大于 maxlength 的对象时，它将“删除”相反末尾的若干对象以维护其大小。

- James