Дек

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Типові операції[ред.ред. код]

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

Реалізації[ред.ред. код]

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

Обчислювальна складність[ред.ред. код]

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

Дивіться також[ред.ред. код]