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
Collection protocol in order to retain some common functionalities and properties.
count and the
isEmpty properties are an example of properties which could be mutated from the
Collection conformance, or easily implemented from a finite
Queue conformance to a type, it must match these requirements:
Conforming types are expected to provide the
peek() properties and method as O(1) operations.
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
reserveCapacity(_:) are expected to be at worst O(n) operations.