Комментарии 6
Недавно обнаружил, что не знаю как устроена deque. Оказывается это специальная структура данных (а я почему то лет 15 из своего опыта в программировании считал что там двусвязный список под капотом). Иногда название этой структуры данных переводят как "дека". Двусторонняя очередь это тоже название этой структуры? Мне кажется что в статье не хватает краткого описания ее устройства.
Двух связанный список там всё таки есть. Просто не на один элемент а на несколько.
https://github.com/python/cpython/blob/main/Modules/_collectionsmodule.c#L31
Да, deque — это двусторонняя очередь.
Структурой данных она не является, это скорее контракт структуры данных. Деку можно делать на двусвязном списке или на массиве. А можно и на двусвязном списке массивов, чтобы собрать преимущества обоих вариантов.
Да, deque == double-ended queue
Подскажите, а где применяяются двусторонние очереди?
Приветствую!
Мне кажется, что в "time_fifo_testing(n)" Python проводить какие-то оптимизации, потому как list должен делать pop n элементов за O(n^2)., Что на 10^5 элементов -> 10^10 операций никак не укладывается в ~ 1 секунду.
Асимптотическое частное 
Должно быть как раз порядка 10^5, а не 100.
Двухсторонние очереди в Python: как альтернатива спискам повышает производительность