Алгоритмы в PHP: Deque (и круговые буферы + связанные списки)PHP массивы хорошо подходят для многих задач, но операции добавления элементов в начало массива (array_unshift) являются медленными, поскольку требуют сдвига всего массива. Решение для этого проблемы — использование
deque (двусторонней очереди).
Очереди и стекиВ программировании, очереди и стеки играют важную роль:
Очередь (FIFO): первый пришел — первый ушел. Работает как очередь в магазине.
Стек (LIFO): последний пришел — первый ушел. Работает как стопка тарелок.
Двусторонняя очередь (Deque)Deque позволяет добавлять и удалять элементы с обоих концов с эффективностью O(1). Обычно реализуется на основе связанных списков или кольцевого буфера и идеально подходит для реализации функций отмены (undo).
Реализация кольцевого буфераДля улучшения производительности можно использовать кольцевой буфер, что минимизирует затраты на операции добавления и удаления элементов. Кольцевой буфер использует два курсора (head и tail), что позволяет добавлять и удалять элементы с обоих концов массива.
Добавление элемента в начало буфера🔸Проверить, заполнен ли буфер.
🔸Если курсор уже в начальной позиции, переместить его в конец массива.
🔸Иначе, декрементировать курсор.
🔸Добавить элемент в массив.
Добавление элемента в конец буфера🔸Проверить, заполнен ли буфер.
🔸Если курсор уже в конце массива, переместить его в начало.
🔸Иначе, инкрементировать курсор.
🔸Добавить элемент в массив.
