How does a deque give you both stack and queue behavior, and what does each of its four operations cost?

## What a deque is A **deque** (double-ended queue, pronounced "deck") is a linear sequence whose defining property is not what it stores but what it *costs*: you may add and remove at **either** end in constant time. The core surface is four mutating operations — push at the front, push at the back, pop from the front, pop from the back — usually joined by non-destructive peeks at each end and a size query. What makes that contract notable is that the obvious sequence structures do **not** offer it: | Structure | push back | pop back | push front | pop front | |---|---|---|---|---| | Growth-doubling dynamic array | O(1) amortized | O(1) | **O(n)** | **O(n)** | | Singly linked list (head pointer only) | **O(n)** | **O(n)** | O(1) | O(1) | | Deque | O(1) | O(1) | O(1) | O(1) | A dynamic array is slow at the front because element 0 is pinned to slot 0: inserting or removing there shifts every other element one position. A deque removes that pin. An array-backed deque stores a *head offset* and lets the occupied region float (and wrap) inside the buffer, so there is spare room at both ends; a node-based deque simply keeps a pointer to each end and links nodes in both directions. Either way, both ends are cheap. ## Recovering a stack and a queue Because a deque is unrestricted, you get the two classic disciplines by *choosing which pair of operations you use*: - **Stack (LIFO)** — push and pop at the **same** end. Push back / pop back and push front / pop front are equally valid; the items come out newest-first either way. This is what a call-frame stack or a backtracking search wants. - **Queue (FIFO)** — push at **one** end and pop at the **other**. Push back / pop front is the conventional choice, and push front / pop back is its mirror. Items leave in arrival order, which is what a breadth-first frontier or a work backlog wants. So a deque is a strict superset of both abstractions, at the same asymptotic cost. That is why it is the default recommendation when you need one of them and have no reason to prefer a specialized type. ## What "O(1)" does and does not promise here This is where the question is actually won or lost in an interview. - In a **single growable array** backing, pushes are **amortized** O(1): most cost a couple of instructions, but the push that overflows the buffer allocates a bigger one and copies every element, costing O(n). Averaged over a worst-case *sequence* of n pushes the total is O(n), hence O(1) each — but no individual push is guaranteed fast. Amortized is a statement about a sequence, not about a distribution of inputs and not about one call. - In a **node-based or fixed-block** backing, each operation touches a bounded amount of memory, so the bound is O(1) worst case per operation (block-based designs still occasionally grow a small index table). - Pops are O(1) in every reasonable backing; array-backed deques usually clear the vacated slot so the removed element is not kept reachable. ## The two things people wrongly assume **"A deque is indexable."** Only sometimes. An array-backed deque can compute the slot for logical position i from the head offset in constant time, so indexed reads are O(1). A node-based deque has to walk, so position i costs O(i). If your algorithm indexes into the middle, the backing you get matters and you should not assume. **"Insertion in the middle is cheap too."** It is not part of the contract. Middle insertion is O(n) in an array backing (shifting) and O(n) in a node backing (finding the node), even though relinking, once you already hold the node, is O(1). ## The API-surface caution A deque's flexibility has a real cost on a team: a type that offers all four operations no longer documents the ordering discipline the code depends on. If a background worker drains a shared backlog and someone "fixes" a line to pop from the back, the backlog silently turns from FIFO into LIFO — no crash, no type error, just old items starving under load. That is why many codebases keep the deque as the *implementation* and expose narrow stack-shaped or queue-shaped wrappers as the *interface*, so the restriction is enforced by the type rather than by reviewer attention. ## How to answer out loud Name the four operations, state the constant-time contract, give the two restrictions that recover LIFO and FIFO, and then volunteer the amortized-versus-worst-case distinction before you are asked. Adding "and indexing is only O(1) if it is array-backed" signals that you know a deque is an interface with several implementations, not one structure.