Дек

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

Дек является симбиозом стека и очереди - это та же структура, но на этот раз с ней можно работать с обоих концов. Таким образом, если мы будем работать с деком только с левого края, то фактически получается стек. Аналогично мы получим стек, если будем работать только с правого края. Пользуясь предписаниями «добавить в конец» и «взять из начала», мы сможем получить очередь.

Логическая структура дека

Структуру дека иллюстрирует, например, специальная схема железнодорожного разъезда (рис. 9).

Логическая структура дека

Рис. 9. Логическая структура дека

Частные случаи дека - дек с ограниченным входом и дек с

ограниченным выходом. Деку с ограниченным входом соответствует схема, на которой закрыт путь А. При закрытии пути В получается схема, имитирующая дек с ограниченным выходом.

Дек обладает большей общностью, чем стек или очередь; он имеет некоторые общие свойства с колодой карт.

Физическая структура дека

Физическая структура дека в статической памяти идентична структуре кольцевой очереди.

Логическая и физическая структуры дека аналогичны логической и физической структурам обычной очереди. Однако в этом случае целесообразнее говорить не о хвосте и голове, а о левом конце и правом конце. Оба указателя абсолютно равноправны.

Операции

Функциональные операции:

  • • сделать пустым;
  • • проверить: пуст, не пуст;
  • • добавить элемент в начало;
  • • добавить элемент в конец;
  • • взять элемент из начала;
  • • взять элемент из конца;
  • • удалить элемент из начала;
  • • удалить элемент из конца;
  • • определить число элементов в деке.

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ   След >