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

Типові операціїРедагувати

  • Додавання елемента в кінець черги
  • Додавання елемента в початок черги
  • Вибірка останнього елемента
  • Вибірка першого елемента
  • Перевірка першого елемента (без видалення з деку)
  • Перевірка останнього елемента (без видалення з деку)

РеалізаціїРедагувати

Існує принаймні два поширених способи ефективної реалізації двосторонньої черги: за допомогою динамічного масиву або двозв'язного списку.

Обчислювальна складністьРедагувати

Реалізація Типові операції деку Вставка в середину Видалення з середини Довільний доступ (по індексу)
Двозв'язний список О(1) О(1) О(1) O(n)
Динамічний масив О(1) O(n) O(n) О(1)

Див. такожРедагувати

ЛітератураРедагувати