Theory
The line with two doors
The canteen adds a parcel counter. Parcels join the line at the rear like everyone else, but two new situations appear:
- A delivery rider with a paid slip is waved in at the front.
- A customer at the rear cancels and walks off with their parcel.
The simple queue forbids both: one door in at the rear, one door out at the front. What the counter needs is a line with a door at each end.
Theory
A train corridor, both ends open
Think of a train corridor with a door at each end. Passengers may board or alight at either door, front or rear.
Lock one door for boarding and you get a stricter corridor; lock the right pair and the corridor behaves exactly like the plain queue, or even like a stack. The deque is the general corridor; the structures you already know are just this corridor with doors bolted.
Theory
Deque, formally
A deque (double-ended queue) is a linear structure that permits insertion and deletion at both ends. Four operations replace the queue's two:
insertFront(x)andinsertRear(x)deleteFront()anddeleteRear()
It is usually built on a circular array (last lesson's ring), because the front must be able to step backwards and wrap:
- rear grows:
rear = (rear + 1) % SIZE - front retreats:
front = (front - 1 + SIZE) % SIZE
That + SIZE guards against a negative index when front is 0.
At a glance
The deque family
| Variant | Insert allowed | Delete allowed |
|---|---|---|
| Deque (unrestricted) | Both ends | Both ends |
| Input-restricted | Rear only | Both ends |
| Output-restricted | Both ends | Front only |
| Plain queue (compare) | Rear only | Front only |
Quiz
At the parcel counter, cancellations must leave from the rear, riders may enter at the front, BUT management rules that parcels may only ever be handed out at the front. Which structure is this?
- Output-restricted deque: insertion at both ends, deletion only at the front
- Input-restricted deque: insertion only at the rear
- A plain circular queue
- A stack, since the rear acts like a top
Show the answer
Output-restricted deque: insertion at both ends, deletion only at the front
Insertions happen at both ends (regular joins at rear, riders at front) while deletion is restricted to the front: the definition of an output-restricted deque. Input-restricted is its mirror (both-end deletes, rear-only inserts). Naming which END is restricted, and for which operation, is exactly what this exam question tests: match the restriction to the operation, not to the word order.
Think first
Front steps backwards: compute the wrap
SIZE 5, and the deque currently has front = 0, rear = 2. A rider is inserted at the FRONT. Using front = (front - 1 + SIZE) % SIZE, what is the new front, and why would (front - 1) % SIZE alone be dangerous?
Show the answer
front = (0 - 1 + 5) % 5 = 4 % 5 = 4: the front wraps to the array's last cell, the ring working in reverse.
Without the + SIZE, you compute (-1) % 5, and in C++ the result of modulo on a negative number is implementation-headachy (typically -1): an invalid index. The + SIZE keeps the arithmetic positive before the wrap. Exams award the formula; interviews award knowing why.
Watch out
Deque is a toolbox, not a discipline
A queue promises FIFO; a stack promises LIFO. A deque promises neither: the order of service depends entirely on which of the four operations your code calls.
Use insertRear + deleteFront only, and it IS a queue. Use insertRear + deleteRear only, and it behaves as a stack. Write that pair of sentences in the exam when asked how a deque generalizes both, it is worth easy marks.
Theory
Where both doors earn their keep
Undo history with a limit: new actions push at one end; when the history is full, the oldest falls off the other end. Palindrome checking: load the word, compare deleteFront() against deleteRear() until they meet. Sliding-window problems in coding rounds lean on deques for the same reason: fresh data in one door, expired data out the other.
Summary
Key takeaways
- Deque: insertion AND deletion at both ends; four operations replace the queue's two.
- Built on a circular array; front retreats with (front - 1 + SIZE) % SIZE to avoid negative indexes.
- Input-restricted: insert at rear only. Output-restricted: delete at front only.
- Choosing operation pairs makes a deque act as a queue or a stack: it generalizes both.
- Applications: capped undo history, palindrome checks, sliding windows.
- Memory hook: a train corridor with both doors open.