Stack and Queue

Stack and Queue

A stack and a queue are the two simplest ways to answer a single question: when I take something out, which one comes out? Both hold a linear sequence of items and both restrict you to adding and removing only at the ends — but they pick opposite ends, and that one choice changes everything about how they behave.

The everyday pictures are exact, not loose analogies. A stack is a pile of plates: you add to the top, and the next plate you grab is the one you put down most recently. A queue is a line at a ticket counter: you join at the back, and the person served next is the one who has waited longest. Nothing is allowed to reach into the middle.

Precise definition

Both are abstract data types (ADTs) — defined by their operations and ordering rule, not by how they are stored. A stack can be built on an array or a linked list; so can a queue. The contract is what matters.

Stack — LIFO (Last In, First Out). Insertion and removal happen at the same end, called the top.

• push(x) — add x to the top.
• pop() — remove and return the top element.
• peek() / top() — read the top without removing it.
• isEmpty(), size() — status.

Queue — FIFO (First In, First Out). Insertion at one end (the back/rear), removal at the other (the front).

• enqueue(x) — add x at the back.
• dequeue() — remove and return the front element.
• front() — read the front without removing it.

Every one of these operations is O(1) — best, worst, and average — when implemented well, because each touches only a fixed end and never scans the sequence.

Worked example — same inputs, opposite outputs

Run the identical operation script on an empty stack and an empty queue, and count what happens. Operations in order: add 10, add 20, add 30, remove, add 40, remove.

Stack (LIFO):

• push 10 → [10]
• push 20 → [10,20]
• push 30 → [10,20,30]
• pop → returns 30 (newest) → [10,20]
• push 40 → [10,20,40]
• pop → returns 40 → [10,20]

Values popped, in order: 30, 40. Final contents: [10, 20].

Queue (FIFO):

• enqueue 10 → [10]
• enqueue 20 → [10,20]
• enqueue 30 → [10,20,30]
• dequeue → returns 10 (oldest) → [20,30]
• enqueue 40 → [20,30,40]
• dequeue → returns 20 → [30,40]

Values dequeued, in order: 10, 20. Final contents: [30, 40]. Six operations each, all O(1); the only difference is which end removal touches, and that flips the output completely.

Common pitfalls and what an interviewer probes

• The naive array queue. If dequeue removes index 0 of an array by shifting every remaining element left, it costs O(n), not O(1). Interviewers watch for this. The fix is a circular buffer (two indices, front and back, that wrap around with modulo) or a linked list with head and tail pointers, or two stacks.
• Underflow. Calling pop/dequeue on an empty structure. Decide the contract up front: throw, or return a sentinel/optional. Say it out loud.
• Overflow on fixed arrays. An array-backed stack must handle a full buffer — either reject, or grow by doubling (amortized O(1) push; the occasional resize is O(n) but averages out).
• peek vs pop confusion. Reading the top and removing it are different; conflating them is a classic off-by-one bug.
• "Implement a queue using two stacks" (and the reverse). A staple question. Push onto an inbox stack; when dequeuing, if the outbox is empty, pour the inbox into it (reversing order) then pop. Each element is moved at most twice, so it is amortized O(1) even though a single dequeue can be O(n).
• Spotting the pattern. Interviewers rarely say "use a stack." They describe matching brackets, undo, backtracking, or "most recent" logic (stack), or level-by-level / oldest-first processing (queue). Naming the ADT is half the answer.

When it matters in practice + trade-offs

Stacks power anything with nesting or reversal: the call stack that tracks function returns, expression evaluation and bracket matching in parsers, undo/redo, browser back-history, and depth-first search (DFS) — an explicit stack is exactly a recursion you manage by hand (useful to dodge deep-recursion stack overflow).

Queues power fair, in-order processing: task and message queues, request buffering, CPU/print scheduling, and breadth-first search (BFS), where FIFO ordering is what guarantees shortest paths in an unweighted graph. Variants extend the idea: a deque (double-ended queue) allows O(1) at both ends and underlies sliding-window algorithms; a priority queue abandons pure FIFO to serve the highest-priority item and is usually a heap with O(log n) operations.

Trade-offs vs neighbours. The whole appeal is that restriction buys speed: because access is confined to the ends, every core operation is O(1), beating a general dynamic array's O(n) middle-insertion and a hash map's constant-with-overhead lookups. The cost is expressiveness — you cannot index, search, or reorder. If you need element[i] or "does it contain x?", a stack or queue is the wrong tool; reach for an array, tree, or hash set. Choose a stack/queue precisely because your problem only ever needs the newest or the oldest item.

Key takeaways

• Same shape, opposite rule: a stack is LIFO (remove newest, from the top), a queue is FIFO (remove oldest, from the front) — the only real difference is which end removal uses.
• All core operations — push/pop/peek and enqueue/dequeue/front — are O(1) when backed by a linked list or a circular/amortized array; a queue built by shifting an array degrades to O(n).
• The restriction is the feature: giving up indexing and search is what buys guaranteed constant-time ends — use them only when you need just the newest or oldest item.
• Recognize them by pattern: nesting, reversal, backtracking, and DFS → stack; fair in-order processing and BFS → queue; and know the classic "queue from two stacks" amortized trick.