Noesis
3.2.8 · D5Linear Data Structures

Question bank — Deque (double-ended queue) — operations, use cases

1,899 words9 min read↑ Back to topic

Before we start, one shared vocabulary reminder so no symbol sneaks in undefined:

True or false — justify

A deque supports insertion and deletion at both ends in
True. That is its defining property; every legal end-operation touches a fixed number of pointers or slots, independent of size.
A deque can only be built from a linked list
False. It has two standard implementations: a Doubly Linked List and a circular dynamic array — both give ends.
Every Stack is a restricted deque
True. Use only push_back + pop_back and you get pure LIFO behaviour — a deque that ignores its front.
Every Queue is a restricted deque
True. Use only push_back + pop_front and you get FIFO — a deque that only ever grows at one end and shrinks at the other.
A single linked list (only next pointers) is enough for an deque
False. pop_back needs the node before the last one instantly; with only next you'd walk from the head, which is . You need the prev pointer, hence doubly linked.
Random access by index is in every deque implementation
False. It is in the array version (compute the slot directly) but in the linked-list version, since you must hop node by node.
Doubling the array on overflow makes a single push_back sometimes cost
True. The copy is — but it happens rarely enough that the amortized cost per push is still .
In a circular array, push_front physically shifts elements to make room at the start
False. Nothing shifts. You only move the front index left (with wraparound); the data never moves. That is the whole reason circular beats a plain array.
A deque is always faster than a plain array for push_back
False. Both are amortized at the back. The deque's advantage is at the front, where a plain array is .
The formula (front + k) % C gives the physical slot of the -th element from the front
True. Walking steps right from front and wrapping past the last slot is exactly what % C encodes.
front = (front - 1) % C is a safe way to move the front left
False. If front is then can be negative or implementation-defined in many languages. You must write (front - 1 + C) % C; the +C guards the wraparound.
A deque can replace a Priority Queue in every algorithm
False. Only in 0-1 BFS, where edge weights are exactly 0 or 1: weight-0 → push_front, weight-1 → push_back keeps the deque sorted "for free". General weights still need a real priority queue.
Peeking (front() / back()) removes the element
False. Peek reads the end without removing it; pop_front/pop_back remove and return. Confusing them corrupts your trace.
Sliding Window Maximum needs a deque because it uses all three: back-insert, back-pop, and front-pop
True. New indices enter at the back, smaller useless ones are popped from the back, and out-of-window indices leave the front — three ends/ops, all only in a deque.

Spot the error

"To pop the back of a singly linked list in O(1), just follow next to the last node."
The error: reaching the last node is fine, but to delete it you need the node before it to fix its pointer — that's the walk. Fix: store a prev pointer (doubly linked).
"push_front on a normal array is O(1) because arrays are fast."
The error: inserting at index 0 forces every existing element to shift right — that's , and over inserts. Fix: use a circular buffer and move the front pointer instead of the data.
"In a circular array, when size == C we just overwrite the oldest element."
The error: silently overwriting loses data — that's a ring buffer with a fixed cap, not a general deque. A deque instead doubles capacity and copies, so nothing is lost.
"front = (front - 1 + C) % C — the % C is pointless since we already added C."
The error: without % C, if front was in the middle, front - 1 + C overshoots past into illegal indices. The +C fixes negatives; the % C wraps overflow. Both are needed.
"A deque and a queue behave identically, so any queue problem should use a deque."
The error: a deque is a superset, but using it where a queue suffices wastes the extra flexibility and can hide intent. Use the most restricted structure that solves the problem — it documents your constraints.
"Deque random access is O(1), so binary search on a deque is fine like on an array."
Partly wrong: it's only for the array-backed deque. On a linked-list deque, each index access is , so binary search degrades to — worse than a linear scan.

Why questions

Why must the linked-list deque be doubly linked and not singly?
pop_back needs the second-to-last node instantly to relink the tail; only a prev pointer gives that in instead of an walk.
Why does a circular array avoid the cost of push_front?
It never moves data — it moves the front index left (wrapping with modular arithmetic), so only one integer changes regardless of size.
Why is dynamic-array push still called despite the occasional doubling copy?
The rare copies are spread across the many cheap pushes; total work for pushes is , so the amortized per-push cost is constant.
Why do we store indices (not values) in the sliding-window-maximum deque?
Indices let us detect when the front candidate has slid out of the window (compare its index to the window start) — values alone can't tell you where an element came from.
Why does 0-1 BFS use push_front for weight-0 edges?
A weight-0 edge keeps the same distance, so that node must be processed before anything farther; putting it at the front preserves the deque's sorted-by-distance order without a priority queue.
Why is a deque the natural tool for a palindrome check?
You must compare and remove from both ends simultaneously (pop_front vs pop_back), which is precisely the deque's dual-end strength; a stack or queue can only reach one end.
Why does (front + k) % C use addition of k but front-decrement uses subtraction?
Elements extend to the right of front, so the -th element is front + k; but a new front is inserted to the left, which is front - 1. Direction of growth dictates the sign.
Why can a deque implement both undo and redo cleanly?
Undo pops from one end and redo pops from the other, letting one structure hold two opposing histories with access to each.

Edge cases

pop_front on an empty deque returns the last element
False — it's an error/underflow. There is nothing to return; a correct implementation raises an exception or signals empty, never fabricates a value.
A deque of size 1: pop_front and pop_back return the same element
True. With one element the front is the back, so either pop removes that single element and empties the deque.
In the palindrome loop "while size > 1", what happens for an odd-length word?
The loop stops with exactly one element (the middle character) left; it never needs comparing, so odd length is handled correctly with no special case.
In the palindrome loop, what about an even-length word?
The loop peels pairs until size hits 0, comparing every character against its mirror — the last comparison empties the deque, so size > 1 is the right guard.
Circular array with front = 0 and we call push_front: where does the new front go?
To index (the last slot), because (0 - 1 + C) % C = C - 1 — the pointer wraps to the far end of the ring.
When size == C in a circular deque and another push arrives, is it an error?
No — unlike a fixed ring buffer, a deque grows: it doubles capacity and copies existing elements in order, then completes the push (amortized ).
push_back then immediately pop_back on a deque — net effect on order and cost?
The deque returns to its prior state; both ops are , so the round trip is with no data movement.
A window of size in sliding-window-maximum: what does the deque hold?
Just the single current index each step; every element is its own window maximum, so the answer is simply the array itself — the algorithm still works, degenerately.
Can front and rear point to the same slot with size > 0?
Yes, exactly when size == 1: the sole element is simultaneously the front and the rear, so both indices coincide.
Does moving front left ever collide with the existing rear before a resize?
Only when size == C (the ring is full). The resize is triggered before that overwrite, so a correctly implemented deque never lets front cross rear into live data.

Connections