Array Based Deques: Почему AddFront/RemoveFront O (1)?

Question

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

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

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

Answer 1

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

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

От cppreference и cplusplus, кажется, что двусторонние очереди сохраняются без смежно.

Here - еще один вопрос StackOverflow, который предоставляет полезный образ и некоторую обогащающую информацию.

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

EDIT: Я предполагаю, что из-за того, что в начале и конце есть порции unusued, относительно легко добавить к передней или задней части, пока, как сказал Джон в своем собственном ответе, вы исчерпали комнату/«ударить границу».