Двобічна черга, жарг. дек (англ. deque, скорочення від double ended queue — «черга з двома хвостами») — абстрактна структура даних, елементи якої можуть додаватись як на початок, так і в кінець.
Типові операції
- Додавання елемента в кінець черги
- Додавання елемента в початок черги
- Вибірка останнього елемента
- Вибірка першого елемента
- Перевірка першого елемента (без видалення з деку)
- Перевірка останнього елемента (без видалення з деку)
Реалізації
Існує принаймні два поширених способи ефективної реалізації двосторонньої черги: за допомогою динамічного масиву або двозв'язного списку.
Реалізація |
Типові операції деку |
Вставка в середину |
Видалення з середини |
Довільний доступ (по індексу)
|
Двозв'язний список |
О(1) |
О(1) |
О(1) |
O(n)
|
Динамічний масив |
О(1) |
O(n) |
O(n) |
О(1)
|
Література