Deque

The essentials

A deque (double-ended queue, pronounced "deck") is a linear data structure in which elements can be inserted and deleted at both ends, the front and the rear. It is therefore more flexible than both a stack and a queue, and can be used as either.

Key points

• Operations: insertFront, insertRear, deletionFront, deletionRear, getFront (peek front), getRear (peek rear), isEmpty and size.
• Python list implementation: insertFront → d.insert(0, x); insertRear → d.append(x); deletionFront → d.pop(0); deletionRear → d.pop(); getFront → d[0]; getRear → d[-1].
• As a stack: insert and delete at the same end (for example, append() and pop()).
• As a queue: insert at one end and delete at the other (for example, append() and pop(0)).
• Python's collections module also provides a deque class with methods such as append(), appendleft(), pop() and popleft().
• Applications: checking whether a string is a palindrome (compare and remove characters from both ends), browser history with a limited size, undo/redo, and job scheduling where tasks may be added at either end.
• Deleting from an empty deque is underflow.

Exam tips

• To check a palindrome with a deque, put all characters in, then repeatedly remove one from each end and compare.
• Trace the list after each operation to answer "what is the deque now" questions.

Common mistakes

• Thinking a deque allows insertion or deletion in the middle; only the two ends are used.
• Confusing insert(0, x) (front) with append(x) (rear).