Структуры данных: очередь.

Довольно часто в практике программирования встречается ситуация, когда необходимо использовать FIFO (first-in first-out) очередь.

Одним из очевидных примеров применения такой структуры данных — это отображение alert’ов. Поскольку заранее неизвестно их количество и время отображения, то может сложиться ситуация, когда одновременно будет выполняться present двух и более alert’ов (что естественно приведет к отображению только одного из них). Либо может сложиться ситуация, когда поверх одного alert’а будет выполняться present другого. Для некоторых проектов эта ситуация просто недопустима.

В качестве примера можно также привести ситуацию, когда необходимо последовательно выполнять present нескольких экранов: рекламный банер, экран о проведении технических работ и, возможно, экран о необходимости обновить приложение.

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

Реализация

Сама идея FIFO очереди не нова и немного поискав в интернете на данную тему, можно достаточно быстро найти реализацию. Например:

Однако мне не удалось найти решение, в котором вместо собственной реализации использовались бы возможности стандартной библиотеки Swift. Естественно, речь идет о протоколах Sequence, ExpressibleByArrayLiteral, Collection и CustomStringConvertible. Тем более, что есть отличный пример использования этих протоколов:

Итак, в качестве внутреннего хранилища данных был выбран массив, поскольку никакой дополнительной информации об объектах, а точнее их экземпляров (instance) и порядка, в котором они расположены, сохранять не требовалось.

Естественно, очередь было бы удобно создавать с помощью квадратных скобок, либо уже передавать в инициализатор массив объектов:

let queue: Queue<Int> = []let queue = Queue([1, 2, 3])

Чтобы воплотить в реальность второй случай, достаточно объявить инициализатор, принимающий массив, а если быть точнее, то достаточно и sequence. Но вот чтобы компилировался и первый вариант, необходимо реализовать протокол ExpressibleByArrayLiteral:

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

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

Теперь при вызове

print(queue)

вы будете наблюдать строку вида

[1, 2, 3]

Однозначно лучше, чем тип класса и адрес в памяти его экземпляра.

Далее, вполне реальна ситуация, когда необходимо перебирать элементы очереди. Скажем, так:

let result = queue.map { $0 * $0 }

Для этого достаточно реализовать Sequence протокол:

Не считаю нужным вдаваться в подробное объяснение, почему в качестве итератора выбран AnyIterator<Element>. В начале повествования была дана ссылка на статью от уважаемого raywenderlich о реализации данных протоколов, там более подробно об этом рассказано. Хотелось бы отметить только одно, что считается правилом хорошего тона (хотя, если быть точным, то совершенно необходимо), скрывать от внешнего мира внутреннюю реализацию (инкапсуляция), в том числе и тип итератора.

Теперь для очереди можно использовать такие методы, как map, filter, reduce, forEach и т.д. В добавок теперь доступны для использования свойства count и isEmpty.

И сразу хотелось бы отметить, что можно предоставить доступ по индексу элемента, либо по диапазону индексов, при этом получив slice, реализуя протокол Collection:

В качестве бонуса можно пользоваться и такими методами, как dropFirst(), dropLast() и т.д.

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