Л А Б О Р А Т О Р И Я

актуальных

РЕШЕНИЙ

реализация структуры Deque с кольцевым буфером - TEST

решение тестовой задачи, создание класса PHP с кольцевым буфером данных

Редко мне попадаются в тестах задачи, которые вызывают большое мое любопытство и интерес при реализации, но вот от одной компании получил такую задачку в общем пакете тестов.

Описание задачи:

Задание Deque

Прежде всего стоит внести ряд пояснений по структуре данных Дек и кольцевому буферу данных.

Вот какая информация есть в Википедии по структуре Дек:

определение Deque

Как можно увидеть требуется реализовать в тесте первые четыре из основных типивых операций обработки данных в структуре Дек. Оставшиеся две операции достаточно тривиальны, поэтому дописать их не составит особого труда даже начинающему программисту.

Из той же Википедии по кольцевому буферу данных:

определение кольцевого буфера

Получив такое интересное задание я естественно первым делом полез в сеть Интернет, чтобы посмотреть, какие реализации такой структуры уже кем-либо осуществлялись. И мне удалось найти несколько реализаций на языке Python. Правда эти реализации были без использования кольцевого буфера. Сделал конвертацию кода по паре примеров, и стал разбираться. Кое-что пришлось повыбрасывать, немногое переделать, что-то добавить - к примеру, логику для кольцевого буфера. Вобщем пришлось вникнуть, и по правде говоря было интересно. :)

Вот итоговый код класса Deque, который мне удалось создать на PHP:

class deq result

Некоторые пояснения по коду:

  • В роли буфера у нас будет выступать массив, который при создании объекта класса будет заполнен значениями NULL, и длина/размерность этого буфера будет задаваться при создании объекта извне (см. строка 14 кода).
  • контроль за расположением элементов в буфере будем осуществлять с помощью двух указателей head (начало очереди) и tail (конец очереди) (см. строки 9-10), в которых будет хранится индекс в массиве последнего поступившего элемента, в head - указатель на последний поступивший элемент в начало очереди, в tail - указатель на последний поступивший элемент в конец очереди.
  • Закольцовывать буфер (массив элементов) мы будем при выдаче новых индексов для head и tail, если указатель будет выходить за границу массива, то переносим его либо в начало, либо в конец массива, в зависимости от направления перемещения указателя (см. строки 66-68).
  • Текущее количество элементов введенное в буфер будем отслеживать с помощью переменной size (см. строка 11).
  • Удаление и добавление элементов приводит к перемещению (изменению) соответствующих указателей, в зависимости от того в конец очереди или в начало добавляется элемент. Значение соответствующего указателя изменяется на -1 для head или 1 для tail при добавлении, и обратно при удалении элементов. При выходе нового индекса за пределы массива буфера соответственно ему присваивается значение либо конца массива, либо начала, в зависимости от направления движения индекса.
  • Сами элементы из буфера не удаляются при вызове методов удаления popFront и popBack (см. строки 41-50 и 52-61), изменяются значения соответствующих указателей, что позволяет достичь О(1).

Удачи в разработке!




другие материалы: