Запросы на основе массива: почему AddFront/RemoveFront O(1)?

Question

С deque на основе массива, почему добавляются и удаляются с лицевой стороны амортизированный O(1)? Для меня будет иметь смысл, что это всегда будет O(n), потому что любая операция будет означать, что текущие значения массива нужно будет "переместить" вправо от индекса 0, чтобы добавить и перенести влево удалять...

Мой профессор говорит, что вам не нужно переключаться, просто обновите привет и вот. Я не совсем уверен, что он имеет в виду.

Это не вопрос C++ как таковой, но я пытаюсь понять его на этом языке.

Answer 1

У вас есть 2 указателя (привет и ло), которые указывают на каждый конец deque:

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

Затем, когда вы щелкаете с одного конца или с другого конца, вы просто возвращаете то, на что указывает указатель, и меняете указатель на следующий / предыдущий:

 //"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++ deque, но вот моя лучшая попытка рационализировать утверждения вашего профессора о сложности времени:

Из cppreference и cplusplus кажется, что запросы хранятся несмежно.

Вот еще один вопрос Stackru, который предоставляет полезное изображение и некоторую полезную информацию.

Обратите внимание, как start просто указывает на фронт, но как это также возможно иметь unused части отдельных кусков. Так что, возможно, нет необходимости перемещать все, когда высовываете фронт, если мы можем просто пометить старый фронт как "неиспользованный", и в некоторой степени аналогично для задней части.

РЕДАКТИРОВАТЬ: я думаю, это потому, что есть unusued порции в начале и в конце, относительно легко добавить к передней или задней части, пока, как Джон сказал в своем собственном ответе, вы не исчерпали место / "достигли границы".