Яка часова складність видалення з черги?

Часова складність операції видалення з черги (dequeue) - O(1).

Це тому, що елемент завжди видаляється з початку черги, і для цього не потрібно проходити весь список - достатньо просто зсунути вказівник (або взяти перший елемент, якщо черга реалізована на зв'язному списку чи кільцевому буфері).

Виняток: якщо черга реалізована на звичайному масиві без кільцевої структури і під час видалення елементи фізично зсуваються, тоді складність стає O(n). Тому на практиці використовують кільцеві буфери або зв'язні списки, щоб зберегти O(1).