Двобічна черга
Двобічна черга, жарг. дек (англ. deque, скорочення від double ended queue — «черга з двома хвостами») — абстрактна структура даних, елементи якої можуть додаватись як на початок, так і в кінець.
Типові операції
- Додавання елемента в кінець черги
- Додавання елемента в початок черги
- Вибірка останнього елемента
- Вибірка першого елемента
- Перевірка першого елемента (без видалення з деку)
- Перевірка останнього елемента (без видалення з деку)
Реалізації
Існує принаймні два поширених способи ефективної реалізації двосторонньої черги: за допомогою динамічного масиву або двозв'язного списку.
Обчислювальна складність
| Реалізація | Типові операції деку | Вставка в середину | Видалення з середини | Довільний доступ (по індексу) |
|---|---|---|---|---|
| Двозв'язний список | О(1) | О(1) | О(1) | O(n) |
| Динамічний масив | О(1) | O(n) | O(n) | О(1) |
Див. також
Література
- Кормен, Томас; Лейзерсон, Чарльз; Рівест, Рональд; Стайн, Кліфорд (2019). Вступ до алгоритмів (вид. 3). К.І.С. ISBN 978-617-684-239-2.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.