Двобічна черга
Перейти до навігації
Перейти до пошуку
Двобічна черга, жарг. дек (англ. deque, скорочення від double ended queue — «черга з двома хвостами») — абстрактна структура даних, елементи якої можуть додаватись як на початок, так і в кінець.
- Додавання елемента в кінець черги
- Додавання елемента в початок черги
- Вибірка останнього елемента
- Вибірка першого елемента
- Перевірка першого елемента (без видалення з деку)
- Перевірка останнього елемента (без видалення з деку)
Існує принаймні два поширених способи ефективної реалізації двосторонньої черги: за допомогою динамічного масиву або двозв'язного списку.
| Реалізація | Типові операції деку | Вставка в середину | Видалення з середини | Довільний доступ (по індексу) |
|---|---|---|---|---|
| Двозв'язний список | О(1) | О(1) | О(1) | O(n) |
| Динамічний масив | О(1) | O(n) | O(n) | О(1) |
- Дональд Кнут. Fundamental Algorithms // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1997. — Т. 1. — 650 с. — ISBN 0-201-89683-4.(англ.)
- Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 10.1 Стеки і черги. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.
|
Це незавершена стаття про структури даних. Ви можете допомогти проєкту, виправивши або дописавши її. |