algorithm - 队列平均 O(1) 入队和出队

Question

我被困在 Problem Solving with Algorithms and Data Structures 中的一个练习中.练习说可以实现一个队列，其中入队和出队的平均时间都是 O(1)，并且出队是 O(n) 的一种情况。

我唯一能想到的就是使用一个列表，其中队列的前端(出队端)由列表的索引跟踪。在此队列中，入队在末尾(即 O(1) 的追加)，出队通过复制当前“前面”元素然后向前移动前面索引跟踪器来操作。但这是巨大的空间成本并且不是目标答案，因为两者总是 O(1)。

对此有什么想法吗？

Answer 1

有很多方法可以实现队列并且仅使用 O(n) 空间。

How to implement a queue using two stacks?

C Program to Implement Queue Data Structure using Linked List

Circular buffer

...而且我认为您不需要知道需要 O(n) 时间才能出队的实现。