Сложность в очереди при использовании списка Python в качестве очереди

Question

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

Answer 1

Ты прав.Список в Python неэффективен при снятии очереди, поскольку все элементы, следующие за убираемым элементом, должны быть скопированы на свои предыдущие позиции, как вы говорите.Вместо этого вы можете использовать collections.deque, который реализован с помощью двусвязного списка, так что вы можете использовать метод popLeft для эффективного удаления из очереди в O (1) сложность времени.

Answer 2

Вы правы.Список Python является списком массивов, поэтому не подходит для высовывания из головы.Вместо этого используйте collections.deque для O (1) добавить / удалить в первый элемент.

Answer 3

Ваш учитель, вероятно, подумал, что python list - это связанный список.Это не.Начиная с документа :

Можно также использовать список в качестве очереди, где первый добавленный элемент является первым полученным элементом («первым пришел, первым вышел»).«);однако списки не эффективны для этой цели.Хотя добавления и вставки в конце списка выполняются быстро, вставки и вставки в начале списка выполняются медленно (поскольку все остальные элементы должны быть смещены на единицу).

Действительно,док предложил вам использовать collections.deque для этой цели.