# Deque

A collection implementing a double-ended queue. 

## Declaration

```swift
import DequeModule

@frozen struct Deque<Element>
```

## Overview

`Deque` (pronounced "deck") implements an ordered random-access
collection that supports efficient insertions and removals from both
ends.

```swift
var colors: Deque = ["red", "yellow", "blue"]
```

Deques implement the same indexing semantics as arrays: they use integer
indices, and the first element of a nonempty deque is always at index zero.
Like arrays, deques conform to `RangeReplaceableCollection`,
`MutableCollection` and `RandomAccessCollection`, providing a familiar
interface for manipulating their contents:


```swift
print(colors[1]) // "yellow"
print(colors[3]) // Runtime error: Index out of range

colors.insert("green", at: 1)
// ["red", "green", "yellow", "blue"]

colors.remove(at: 2) // "yellow"
// ["red", "green", "blue"]
```

Like all variable-size collections on the standard library, `Deque`
implements value semantics: each deque has an independent value that
includes the values of its elements. Modifying one deque does not affect any
others:

```swift
var copy = deque
copy[1] = "violet"
print(copy)  // ["red", "violet", "blue"]
print(deque) // ["red", "green", "blue"]
```

This is implemented with the copy-on-write optimization. Multiple copies of
a deque share the same underlying storage until you modify one of the
copies. When that happens, the deque being modified replaces its storage
with a uniquely owned copy of itself, which is then modified in place.

`Deque` stores its elements in a circular buffer, which allows efficient
insertions and removals at both ends of the collection; however, this comes
at the cost of potentially discontiguous storage. In contrast, `Array` is
(usually) backed by a contiguous buffer, where new data can be efficiently
appended to the end, but inserting at the front is relatively slow, as
existing elements need to be shifted to make room.

This difference in implementation means that while the interface of a deque
is very similar to an array, the operations have different performance
characteristics. Mutations near the front are expected to be significantly
faster in deques, but arrays may measure slightly faster for general
random-access lookups.

Deques provide a handful of additional operations that make it easier to
insert and remove elements at the front. This includes queue operations such
as `popFirst` and `prepend`, including the ability to directly prepend a
sequence of elements:

```swift
colors.append("green")
colors.prepend("orange")
// colors: ["orange", "red", "blue", "yellow", "green"]

colors.popLast() // "green"
colors.popFirst() // "orange"
// colors: ["red", "blue", "yellow"]

colors.prepend(contentsOf: ["purple", "teal"])
// colors: ["purple", "teal", "red", "blue", "yellow"]
```

Unlike arrays, deques do not currently provide direct unsafe access to their
underlying storage. They also lack a `capacity` property -- the size of the
storage buffer at any given point is an unstable implementation detail that
should not affect application logic. (However, deques do provide a
`reserveCapacity` method.)
