Что такое дек?

Дек, также называемый двусторонней очередью, - это упорядоченная коллекция элементов, подобная очереди. Он имеет два конца (голову и хвост), и его элементы остаются позиционированными. Что отличает дек, так это нестрогая природа добавления и удаления его составляющих. Новые элементы могут быть добавлены как в голову, так и в хвост. Аналогично, существующие компоненты могут удаляться из обоих концов. В каком-то смысле, этот гибрид линейной структуры объединяет все возможности стеков и очередей. Рисунок 1 демонстрирует дек из объектов данных Python.

Важно отметить, что несмотря на обладание деком многих характеристик стеков и очередей, он не поддерживает LIFO или FIFO упорядочение, которые воплощаются в жизнь этими структурами данных. Только от вас зависит, какого типа операции добавления или удаления использовать.

../_images/basicdeque.png

Рисунок 1: Дек из объектов данных Python

Next Section - Абстрактный тип данных “дек”