A data structure which yelds its stored elements with a predetermined sequential order.
Queues works upon two basilar operations: enqueue and dequeue.
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.
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.
|Last commit: 26 weeks ago|