Queue

A data structure which yelds its stored elements with a predetermined sequential order.

Queues works upon two basilar operations: enqueue and dequeue.

• Enqueue is the operation for storing elements in the queue.
• Dequeue is for retrieving elements stored in the queue, sequentially and by the order defined for the queue.

For example a queue using the FIFO order (first in, first out), will dequeue elements starting from the first enqueued element, proceding sequentially to the last enqueued one. On the contrary a queue using the LIFO order (last in, first out) —a.k.a stack— will dequeue elements starting from the last enqeueued one, proceding sequentially to the first equeued one.

Conforming to the Queue protocol

Despite not being stricktly required, a type conforming to Queue protocol might as well benefit from also conforming to Sequence or Collection protocol in order to retain some common functionalities and properties. The count and the isEmpty properties are an example of properties which could be mutated from the Collection conformance, or easily implemented from a finite Sequence. To add Queue conformance to a type, it must match these requirements:

• The count and isEmpty properties
• The capacity and isFull properties
• The peek() and dequeue() methods
• The clear(keepingCapacity:) method
• The enqueue(_:) and enqueue(contentsOf:) methods
• The reserveCapacity(_:) method

Expected Performance

Conforming types are expected to provide the count, isEmpty, capacity, isFull and peek() properties and method as O(1) operations. The dequeue() and enqueue(_:) methods are expected to be at least O(log n) operations, where n is the count of stored elements, thus enqueue(contentsOf:) is expected to be an O(logn + k) where k is the count of elements stored in the sequence specified as contentsOf parameter. Reasonably the clear(keepingCapacity:) and reserveCapacity(_:) are expected to be at worst O(n) operations.