Double-Ended Queue (Deque)

We have now seen two limited-access structures.

• A stack adds and removes at the same end, so the most recent item is the first one removed: last in, first out.
• A queue adds at the back and removes from the front, so the oldest item is the first one removed: first in, first out.

A double-ended queue, usually shortened to deque and pronounced “deck”, combines these two ideas.

A deque has two ends, called the first end and the last end, and both ends are active. You can add or remove at the first end, and you can add or remove at the last end.

                    ┌───────┬─────────────┬──────┐
add/remove/access ↔ │ first │     ...     │ last │ ↔ add/remove/access
                    └───────┴─────────────┴──────┘

That makes the deque more flexible than either structure by itself.

• If you only use one end, it behaves like a stack: add at the first end and remove from the first end.
• If you add at one end and remove from the other, it behaves like a queue: add at the last end and remove from the first end.

The deque still does not let a client touch the middle. There is no way to remove or insert at an arbitrary index.

That extra flexibility makes the implementation harder. We will write the ADT first, then build two implementations: one with a linked list and one with a circular array.