Алгоритмы в PHP: Deque (и круговые буферы + связанные списки)

PHP массивы хорошо подходят для многих задач, но операции добавления элементов в начало массива (array_unshift) являются медленными, поскольку требуют сдвига всего массива. Решение для этого проблемы — использование deque (двусторонней очереди).

Очереди и стеки

В программировании, очереди и стеки играют важную роль:

Очередь (FIFO): первый пришел — первый ушел. Работает как очередь в магазине.
Стек (LIFO): последний пришел — первый ушел. Работает как стопка тарелок.

Двусторонняя очередь (Deque)

Deque позволяет добавлять и удалять элементы с обоих концов с эффективностью O(1). Обычно реализуется на основе связанных списков или кольцевого буфера и идеально подходит для реализации функций отмены (undo).

Реализация кольцевого буфера

Для улучшения производительности можно использовать кольцевой буфер, что минимизирует затраты на операции добавления и удаления элементов. Кольцевой буфер использует два курсора (head и tail), что позволяет добавлять и удалять элементы с обоих концов массива.

Добавление элемента в начало буфера
🔸Проверить, заполнен ли буфер.
🔸Если курсор уже в начальной позиции, переместить его в конец массива.
🔸Иначе, декрементировать курсор.
🔸Добавить элемент в массив.

Добавление элемента в конец буфера
🔸Проверить, заполнен ли буфер.
🔸Если курсор уже в конце массива, переместить его в начало.
🔸Иначе, инкрементировать курсор.
🔸Добавить элемент в массив.