Deque (should be pronounced as “deck”) is a collection implementing double-ended queues. Deques are similar to arrays, but they have efficient insertions and removal of elements at the beginning and at the end.

The indexing semantics are integer indices that are the same as arrays. Now let’s see a sample implementation of deque.

var colors: Deque = ["Yellow", "Orange"]
print(colors) // [Yellow, Orange]

The above code implements a deque of colors with the strings yellow and orange.

Deque operations

Now let’s see some operations or methods unique to deques.

1. prepend - Adding an element at the beginning of the deque.

colors.prepend("Blue") // Blue is added to the beginning

2. append - Adding an element to the end of the deque.

colors.append("White") // White is added to the end

3. popFirst - Removal of an element from the beginning of the deque.

let _ = colors.popFirst() // Blue is removed

4. popLast - Removal of an element from the beginning of the deque.

let _ = colors.popLast() // White is removed
print(colors) // [Yellow, Orange]

Other operations

Addition to deque specific methods, there are some common methods like insert, sort, etc.,

colors.insert("Violet", at: 1) 
print(colors) // [Yellow, Violet, Orange]
colors.sort() 
print(colors) // [Orange, Violet, Yellow]

Key highlights of a deque

  • Deque implements value semantics.
  • Deque conforms to RangeReplaceableCollection, MutableCollection, and RandomAccessCollection.
  • Deque stores its elements in a circular buffer. So that insertions and deletions at the beginning and end are efficient.

The Gotchas

Every data structure has its pros and cons. Likewise, there are some gotchas of deque which we have to know.

  • The storage in a deque is discontiguous, whereas, in an array, it is contiguous. Because of this behavior, insertions in the front in a deque are faster, and in arrays, random-access lookups are faster. So it is not recommended to replace all arrays with deques in the code. We need to know when to use arrays and when to use deques.

Closing thoughts

Deque is an excellent addition to Swift. Likewise, Ordered Set and Ordered Dictionary are also included in Swift collections. I will be writing more about them in the upcoming articles. I hope you like this article. Do let me know your thoughts about the deque data structure in the comments below.

References

[1] https://swift.org/blog/swift-collections/ [2] https://github.com/apple/swift-collections/blob/main/Documentation/Deque.md

About the author