Инструменты пользователя

Инструменты сайта


examination:ccc:question5

Вопрос №5. Двусвязные очереди

Определение

Дэк, дек (англ. deque: double ended queue), двусвязная очередь, «очередь с двумя концами» — структура данных, в которой элементы можно добавлять и удалять как в начало, так и в конец.

Возможные типы

  1. удаление элементов производится с обоих концов, добавление с одного
  2. удаление производится с одного конца, добавление с обоих

Операции:

  1. PushBack — добавление в конец очереди.
  2. PushFront — добавление в начало очереди.
  3. PopBack — выборка с конца очереди.
  4. PopFront — выборка с начала очереди.
  5. Проверка наличия элементов.
  6. Очистка.



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

Стандартная библиотека шаблонов в Си++: std::deque и std::list

examination/ccc/question5.txt · Последние изменения: 2014/01/15 12:13 (внешнее изменение)