队列平均 O(1) 入队和出队
Queue with O(1) enqueue and dequeue on average
我被困在 Problem Solving with Algorithms and Data Structures 的练习中。练习说可以实现一个队列，其中入队和出队的平均时间都是 O(1)，并且出队是 O(n) 的一种情况。
我唯一能想到的就是使用一个列表，其中队列的前端（出队端）由列表的索引跟踪。在这个队列中，入队在最后（即，O(1) 的追加），出队通过复制当前 "front" 元素然后向前移动前端索引跟踪器来操作。但这是巨大的 space 成本并且不是目标答案，因为两者总是 O(1)。
对此有什么想法吗？
有很多方法可以实现队列并且只使用 O(n) space。
How to implement a queue using two stacks?
C Program to Implement Queue Data Structure using Linked List
...而且我认为您不需要知道需要 O(n) 时间才能出队的实现。
我被困在 Problem Solving with Algorithms and Data Structures 的练习中。练习说可以实现一个队列，其中入队和出队的平均时间都是 O(1)，并且出队是 O(n) 的一种情况。
我唯一能想到的就是使用一个列表，其中队列的前端（出队端）由列表的索引跟踪。在这个队列中，入队在最后（即，O(1) 的追加），出队通过复制当前 "front" 元素然后向前移动前端索引跟踪器来操作。但这是巨大的 space 成本并且不是目标答案，因为两者总是 O(1)。
对此有什么想法吗？
有很多方法可以实现队列并且只使用 O(n) space。
How to implement a queue using two stacks?
C Program to Implement Queue Data Structure using Linked List
...而且我认为您不需要知道需要 O(n) 时间才能出队的实现。