Двобічна черга, жарг. дек (англ. 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 .
![]() | Це незавершена стаття про структури даних. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет