Data structures: a queue

Quite often there is a situation in programming practice when it is required to use FIFO (first-in first-out) queue.

One of the obvious example of the use of such a data structure is display alerts. Since their number and display time are not known in advance, a situation may arise when several (two or more) alerts will be presented simultaneously (which naturally leads to displaying only one of them). Or there may be a situation when presentation of another will be preformed over the alert. For some projects, this situation is unacceptable.

As an example, you can also give when you need to sequentially perform a presentation of several screens, such as: ad banner, maintenance screen, required app update screen.

The above cases are not all in which a FIFO queue may be needed. And since literate programmers organises the code in such a way that it is reusable, it becomes clear that such a queue should be created as a separate component.

Implementation

The very idea of a FIFO queue is not new and after a little searching on the internet on this topic, you can quickly find an implementation. For example:

However, I have not been able to find a solution that uses all the features of the Swift library instead of programmer own implementation. Naturally we are talking about Sequence, ExpressibleByArrayLiteral, Collection and CustomStringConvertible protocols. Moreover, there is a great example of their use:

So, the array was chosen as the internal data storage, since there is no additional information about the objects and their order was required.

It would be convenient to create a queue using square brackets, or pass an array to the initialiser:

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

To make the second case come true, it is enough to declare an initialiser that takes an array. To be more precise, the sequence is enough. But in order to compile the first option, it is necessary to implement the ExpressibleByArrayLiteral protocol:

Next you should program API, through which the outside world will interact with the queue, in other words, add items, delete and clear.

t would seem that this is the end of it, because all the necessary functionality has been implemented. But it would be convenient during debugging to display the list of elements of the queue, in the same form as it is done for arrays. In fact, this is a very trivial task and it is easy to solve:

Now when calling:

print(queue)

you will get a string like:

[1, 2, 3]

Definitely better than the class type and the memory address where it stored.

Further, the situation is quite real when it is necessary to iterate over the elements of the queue. So to speak:

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

To do this, it is enough to implement the Sequence protocol:

I don’t think it necessary to explain in detail why I choose AnyIterator<Element>. At the beginning of the article, a link was given to the respected raywenderlich about implementation of these protocols. There is more detail about this. It would like to note only one thing, which is considered a good form (although, to be precise, it is absolutely necessary) to hide the internal implementation (encapsulation) from the external part of the program, including the type of iterator.

Now for the queue you can use methods such as map, filter, reduce, forEach etc. In addition, count and isEmpty properties are now available for use.

And right away I would like to note that you can provide access by the index of the element, or by the range of indices, implementing Collection protocol:

As a bonus, you can use methods such as dropFirst(), dropLast() etc.

In the end, writing not so much code, we got a real FIFO queue, while with quite wide possibilities. Of course, the functionality can be expanded. For example add a method to rearrange first element to the end of queue. Bu these methods are already more specific and are not required.Therefore, they are not included in this article. That’s it, I wish you good mood.