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

У Вікіпедії є статті про інші значення цього терміна: Дек (значення).

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