Stacks, queues, and deques are conceptually trivial — the interview difficulty lives entirely in picking the right underlying structure, because the 'obvious' choice in each language hides a complexity trap of its own.
Language Verdict: Pros, Cons & Recommendation
collections.deque gives true O(1) append/appendleft/pop/popleft at both ends via block-based doubly-linked storagedeque(maxlen=n) gives a free auto-evicting bounded queue with zero hand-rolled code- Single blessed structure for stack/queue/deque work — no legacy synchronized alternative to accidentally reach for
list.pop(0)/list.insert(0, x) are O(n) — the same reindexing trap as JS's shift/unshift, easy to reach for by mistake- No dedicated peek method or null-safe peek/throw pair like Java's
peek/element split — just raw indexing that raises IndexError on empty
ArrayDeque is a single resizable circular-array structure that's O(1) amortized at both ends — covers stack, queue, and deque uses- Deliberate
peek*/poll* (null on empty) vs getFirst/removeFirst (throws) method pairs let you choose fail-safe vs fail-fast explicitly - Javadoc itself steers you away from footguns — explicitly recommends
ArrayDeque over the legacy Stack and LinkedList ConcurrentLinkedDeque/PriorityBlockingQueue-style concurrent variants exist if concurrency ever comes up
- Three overlapping options (
ArrayDeque, LinkedList, legacy Stack) mean you must actively know to avoid the two worse ones - Legacy
Stack extends Vector and is internally synchronized — a real, if usually small, perf cost for unneeded thread-safety if picked by habit
- A slice is a perfect stack:
append / s[len(s)-1] / s = s[:len(s)-1] are all O(1) amortized with unboxed ints container/list gives a real doubly-linked deque when you actually need O(1) both ends- No legacy synchronized
Stack class to accidentally reach for
- No stdlib deque — naive front-pop either copies O(n) or reslices O(1) and leaks the backing-array prefix; use a head index, ring buffer, two stacks, or
container/list - No dedicated peek that returns a comma-ok or error; empty-slice index panics
container/list stores any (boxed) and uses *list.Element — verbose compared to a slice, rarely what interviews want
Array's push/pop are genuinely O(1) amortized — perfectly fine as a pure stack with zero setup- No type ceremony — a plain array is immediately usable, no class or import needed
- No built-in deque or true FIFO queue at all —
shift/unshift are O(n) because every element must be reindexed shift() in a loop silently degrades an O(n) algorithm to O(n²) — one of the most common JS interview complexity bugs- Genuine O(1)-both-ends behavior requires hand-rolling a circular buffer or linked-list deque under time pressure
Recommendation: Python's collections.deque and Java's ArrayDeque remain the best O(1)-both-ends tools. Go is a fine stack (slice); for a queue use a head index, ring buffer, two stacks, or container/list — s = s[1:] is O(1) time but leaks the backing-array prefix. In JavaScript, arrays are fine as a stack, but never shift() in a loop.
Coding Mechanics, Side by Side
This is the single most common performance bug JS candidates introduce without realizing it — and Go's s = s[1:] is the same trap with different spelling.
from collections import deque
q = deque()
q.append(1) # O(1) — right end
q.appendleft(0) # O(1) — left end
q.popleft() # O(1) — left end
Not really a Python trap: list.pop(0) IS O(n) (the same problem as JS shift), which is exactly why collections.deque exists — reach for it any time you need FIFO behavior or work at the front of a sequence.
stack = []
stack.append(1) # O(1)
stack.pop() # O(1)
from collections import deque
dq = deque()
dq.append(1); dq.appendleft(0) # both O(1)
dq.pop(); dq.popleft() # both O(1)
list is a dynamic array: append/pop (from the end) are O(1) amortized, but list.pop(0)/list.insert(0, x) are O(n) — the same reindexing cost as JS's shift/unshift. deque is implemented as a doubly linked list of small fixed-size blocks (not single-element nodes), giving true O(1) push/pop at BOTH ends with better cache behavior than a naive node-per-element linked list, at the cost of O(n) random access (dq[5] is not O(1) like list[5]).
# Python doesn't have this three-way split — deque is the one blessed
# implementation, and it's already block-based (not per-node), so there's
# no "legacy synchronized" trap to avoid.
from collections import deque
stack = deque()
There's no analog to Java's legacy Stack pitfall in Python — deque has been the single recommended structure for stack/queue work since it was added, with no competing synchronized or per-node-linked-list alternative in the standard library to accidentally reach for.
stack = []
for i, x in enumerate(nums):
while stack and nums[stack[-1]] < x:
top = stack.pop()
# process `top` using current index i as the resolving boundary
stack.append(i)
Store indices, not values, so you can compute distances/widths once an element is resolved. stack[-1] peeks without popping; the while stack and ... guard is the whole trick — get the comparison direction right (< for a decreasing stack, > for increasing) and everything else is boilerplate.
from collections import deque
window = deque() # stores indices
for i, x in enumerate(nums):
while window and nums[window[-1]] <= x:
window.pop()
window.append(i)
if window[0] <= i - k:
window.popleft()
popleft()/appendleft() are what make deque the right tool the moment a sliding-window problem needs to evict from the front — using a plain list here would reintroduce the O(n) pop(0) cost on every eviction.
stack = [1, 2, 3]
if not stack:
print("empty")
top = stack[-1] # peek, no removal; raises IndexError if empty
No dedicated peek method — indexing with [-1] (or [0] for a deque's front) both peeks. There's no null-safe variant; peeking an empty sequence raises IndexError, so the emptiness check must come first when it matters.
class CircularQueue:
def __init__(self, capacity):
self.buf = [None] * capacity
self.head = self.size = 0
self.capacity = capacity
def enqueue(self, val):
if self.size == self.capacity:
raise OverflowError("queue full")
self.buf[(self.head + self.size) % self.capacity] = val
self.size += 1
def dequeue(self):
val = self.buf[self.head]
self.head = (self.head + 1) % self.capacity
self.size -= 1
return val
This 'design a circular queue' pattern shows up directly in interviews. The trick is tracking head and size and always wrapping index arithmetic with % capacity — never physically shift elements. collections.deque(maxlen=n) gives a built-in bounded, auto-evicting version for free when you don't need to implement it by hand.
Not deeply relevant to interview correctness, but worth knowing as a one-liner per language (Go's ordinary slices/maps are not concurrent-safe).
from collections import deque
dq = deque()
# Individual append()/pop() calls are atomic w.r.t. other threads
# because of the GIL, but compound operations (check-then-act) are not.
deque's single append/pop operations are thread-safe as a side effect of the GIL (each is a single atomic bytecode-level step), but this is an implementation detail, not a documented contract to design around — any multi-step sequence still needs a lock.