Если "ДЕК" для тебя что-то знакомое, но до конца не уверен...

- Ты не знаешь чем он отличается от двусвязного списка
- Без понятия какие там реализации

То ты 👉: среднестатистический разработчик

И сейчас я тебя прокачаю!

В общем, дек — абстрактный тип данных, который поддерживает вставку и удаление из начала и конца за O(1)

Абстрактный — значит реализация может быть любая и главное, чтобы выполнялись правила выше

Например, двусвязный список — это одна из реализаций дека

Или можно реализовать его на двух стеках

В общем — как угодно

НО! C++ ТУТ УДЕЛАЛ ВСЕХ!

Он сделал реализацию на chunked array, за счет чего появилась операция доступа по индексу за O(1)...

Т е натуральная имба, которая мало того что удаление и вставка в начало и конец, так еще и O(1) получить элемент по индексу

И вся магия в реализации...

А если соберем 100 🌭 до пятницы — расскажу как это работает под капотом

UPD: разбору быть)