Stacks, Queues & Deques

The last lesson left a promise hanging: the recursion behind every divide-and-conquer sort runs on a call stack — a data structure worth meeting head-on. Here it is, beside its sibling. A list lets you touch any element you like. A stack and a queue deliberately restrict you to one or two ends, and that restriction is the entire point. By controlling where items enter and leave, they enforce an order: a stack always hands back the most recent item, a queue always the oldest. Pick the structure whose order matches your problem, and the rest is bookkeeping.

Stack (LIFO) and queue (FIFO)

A stack is LIFO — last in, first out. You push onto the top, pop from the top, and peek at the top. Think of a stack of plates: you take from whichever you put down last. A queue is FIFO — first in, first out. You enqueue at the back and dequeue from the front, exactly like a checkout line: first to arrive is first to leave.

A deque (double-ended queue) generalises both: you can push and pop at either end. Push and pop at one end and it behaves like a stack; enqueue at the back and dequeue at the front and it behaves like a queue. Use it when you need flexibility at both. Every operation on all three is O(1) — and why that is true is the question the next lesson answers.

Drive the operations yourself — switch between Stack, Queue, and Deque, and watch which end the next item leaves from:

These structures are everywhere. A stack backs the function call stack (the very one your recursive sorts ran on), the undo history in an editor, and balanced-parentheses checking (push each open bracket, pop on each close). A queue drives breadth-first search (BFS), task scheduling, and any “first come, first served” buffer — the same FIFO logic behind the message queues (Kafka, SQS) that stream events into a data pipeline.

How GATE asks this

Almost always an MCQ that traces a sequence: it lists a string of pushes/pops (or enqueues/dequeues) and asks for the final top/front, the popped value, or the size — the 2024 paper used exactly this operation-trace style. There is no formula; you simply simulate carefully and respect the entry/exit ends. The only way to lose marks is to pop from the wrong end.

Worked example — trace a stack, then a queue

Apply the same six operations as a stack with push/pop:

op        action            stack (bottom -> top)
push 1    push 1            [1]
push 2    push 2            [1, 2]
push 3    push 3            [1, 2, 3]
pop       remove top (3)    [1, 2]      <- popped 3
push 4    push 4            [1, 2, 4]
pop       remove top (4)    [1, 2]      <- popped 4

LIFO removes the most recent item each time: the first pop returns 3, the second returns 4. Final stack is [1, 2], so the top is now 2.

Now the analogous queue with enqueue/dequeue (enqueue 1, 2, 3; dequeue; enqueue 4; dequeue):

op         action               queue (front -> back)
enqueue 1  add at back           [1]
enqueue 2  add at back           [1, 2]
enqueue 3  add at back           [1, 2, 3]
dequeue    remove front (1)      [2, 3]      <- dequeued 1
enqueue 4  add at back           [2, 3, 4]
dequeue    remove front (2)      [3, 4]      <- dequeued 2

FIFO removes the oldest item: the first dequeue returns 1, the second returns 2. Final queue is [3, 4], so the front is now 3. Same operation sequence, opposite removal order — that single contrast is the entire lesson.

A question to carry forward

We slipped one claim past you: every operation on all three is O(1). But look closer with the last chapter’s complexity eyes, and it is not obvious at all. A Python list appends to its end in O(1), fine — yet deleting from the front of a list shifts every remaining element left, an O(n) cost. So how can a queue possibly dequeue from the front in true constant time, without that shift? Here is the thread onward: what underlying structure lets you add and remove at an end in genuine O(1), by threading each element to the next instead of packing them in one solid block of memory?

In one breath

• Stack = LIFO (last in, first out): push/pop/peek all at the top — returns the newest item. Plates.
• Queue = FIFO (first in, first out): enqueue at the back, dequeue from the front — returns the oldest item. Checkout line.
• Deque = both ends; all operations O(1) on every one of the three.
• Fits: stack → call stack, undo, balanced parentheses; queue → BFS, scheduling, FIFO buffers.
• GATE traces a sequence — respect entry/exit ends; on push 1,2,3;pop;push 4;pop the stack top is 2, the queue front (same ops) is 3.

Practice