Stacks, Queues & Deques

A list lets you touch any element. A stack and a queue deliberately restrict you to one or two ends — and that restriction is the whole point. By controlling where items enter and leave, they enforce an order: a stack always returns the most recent item, a queue always returns the oldest. Pick the structure whose order matches your problem, and the rest is just 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. Use it when you need flexibility at the front and the back. 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. Every operation on all three is O(1).

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 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 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 just 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 contrast is the entire lesson.

Quick check