基于数组的双端队列：为什么 AddFront/RemoveFront O(1)？

Question

对于基于数组的双端队列，为什么从前面添加和删除会摊销 O(1)？对我来说，它总是 O(n) 是有意义的，因为任何一个操作都意味着数组的当前值需要 "moved" 到 0 索引的右侧才能添加和到左边要删除...

我的教授说你不需要换班，只需更新 hi 和 lo 即可。我不太确定他的意思。

这本身不是 C++ 问题，但我试图用这种语言来理解它。

Answer 1

你有 2 个指针（hi 和 lo）指向双端队列的每一端 :

"aaaaa" <- hi
"bbbbb"
"ccccc"
"ddddd"<- lo

然后当你从一端或另一端弹出时，你只需 return 指针指向的内容并将指针更改为指向 next/prev:

 //"aaaa" is still in the array but not considered part of the deque
 "bbbbb" <- hi
 "ccccc"
 "ddddd" <- lo

更简单的例子：

class Deque {
int deque[10];
int hi, lo;   // Initialize in constructor to -1 to flag deque is empty

public:
void push_front(int x) {
    // First time, add to middle of array
    if (-1 == lo) {
        hi = lo = 5; // Since array size is 10;
        deque[5] = x;
    }
    // Shift required?
    else if (lo == 0) {
        // Check if deque is full
        if (9 == hi) {
             // return error or get more space
        }
        else {
             // Shift by one
             // More optimally you would shift enough to move data to center of array
             for (int i = hi; i >= lo; --i) {
                 deque[i + 1] = deque[i];
             }
             // Update hi
             hi += 1;
             // Store in lo - lo remains at 0
             deque[0] = x;
         }
     }
     // No shift required
     else {
         deque[--lo] = x;
     }
 }
 // TODO: push_back, pop_front, pop_back

Answer 2

我不明白双端队列的确切 C++ 实现，但这是我最好的尝试来合理化你的教授关于时间复杂度的说法：

从cppreference and cplusplus开始，双端队列似乎是非连续存储的。

Here 是另一个 Whosebug 问题，它提供了有用的图像和一些丰富的信息。

请注意 start 是如何简单地指向前面的，但是如何也可能有 unused 部分单独的块。因此，如果我们可以简单地将旧的正面标记为 'unused'，并且背面也类似地标记为

，那么在弹出正面时，也许没有必要移动所有内容。

编辑：我的猜测是，因为在开头和结尾有 unusued 部分，所以添加到前面或后面相对容易，直到，正如约翰在他自己的回答中所说，你运行房间外/'hit a boundary'.

基于数组的双端队列：为什么 AddFront/RemoveFront O(1)？

Array Based Deques: Why is AddFront/RemoveFront O(1)?

c++

queue

dynamic-arrays

deque