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