Deque

A deque (pronounced 'deck'), short for double-ended queue, is a linear list that allows insertion and deletion at both ends, but not in the middle.

Its operations:

• INSERTFRONT and INSERTREAR: add at the front or the rear;
• DELETIONFRONT and DELETIONREAR: remove from the front or the rear;
• plus IS EMPTY, PEEK (at either end) and SIZE.

A deque is flexible enough to act as either of the other structures:

• If you always insert and delete at the same end, it behaves as a stack.
• If you insert at one end and delete at the other, it behaves as a queue.

Uses:

• A person who has just stepped out of a ticket queue to get a missing document may be allowed back in at the front.
• At a toll plaza, the vehicle at the rear of one line may move to a vacant booth.
• Browser history and undo lists, which drop the oldest items from one end while adding new ones at the other.
• Checking whether a word is a palindrome.

To check for a palindrome (Algorithm 4.1), insert every character at the rear, then repeatedly remove one character from each end and compare them. If they always match until zero or one character is left, the word is a palindrome. For 'level': l and l match, e and e match, and only v is left, so it is a palindrome.