Двобічна черга

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Двобічна черга, жарг. дек (англ. 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.