Що таке двостороння черга (deque)?

Двостороння черга (deque) - це структура даних, у якій елементи можна додавати та видаляти з обох сторін - і з початку, і з кінця.

#Основні операції

• addFront(x) - додати елемент на початок,
• addRear(x) - додати елемент в кінець,
• removeFront() - видалити елемент з початку,
• removeRear() - видалити елемент з кінця,
• peekFront() і peekRear() - подивитися елементи без видалення.

#Відмінність від звичайної черги

У звичайній черзі додавання - тільки з кінця, видалення - тільки з початку. У deque обидві сторони рівноправні.

#Застосування

• реалізація стека і черги в одному об'єкті,
• задачі з «вікнами» (наприклад, максимум у ковзному вікні),
• кешування (LRU-алгоритми),
• симетрична обробка даних, де потрібно швидко працювати з обома кінцями.

Усі основні операції deque виконуються за O(1).