Двобічна черга
| Цю статтю треба вікіфікувати для відповідності стандартам якості Вікіпедії. (серпень 2016) |
Двобічна черга, жарг. дек (англ. deque, скорочення від double ended queue — «черга з двома хвостами») — абстрактна структура даних, елементи якої можуть додаватись як на початок, так і в кінець.
Типові операції ред.
- Додавання елемента в кінець черги
- Додавання елемента в початок черги
- Вибірка останнього елемента
- Вибірка першого елемента
- Перевірка першого елемента (без видалення з деку)
- Перевірка останнього елемента (без видалення з деку)
Реалізації ред.
Існує принаймні два поширених способи ефективної реалізації двосторонньої черги: за допомогою динамічного масиву або двозв'язного списку.
Обчислювальна складність ред.
| Реалізація | Типові операції деку | Вставка в середину | Видалення з середини | Довільний доступ (по індексу) |
|---|---|---|---|---|
| Двозв'язний список | О(1) | О(1) | О(1) | O(n) |
| Динамічний масив | О(1) | O(n) | O(n) | О(1) |
Див. також ред.
Література ред.
- Кормен, Томас; Лейзерсон, Чарльз; Рівест, Рональд; Стайн, Кліфорд (2019). Вступ до алгоритмів (вид. 3). К.І.С. ISBN 978-617-684-239-2.
{{cite book}}: Cite має пустий невідомий параметр:|1=(довідка)
|
Це незавершена стаття про структури даних. Ви можете допомогти проєкту, виправивши або дописавши її. |