Stacks and Queues as List

DSA, Database System & Operating System — Data Structure, Lists, Linked Lists and Trees, NEC licence examination syllabus (Nepal Engineering Council).

Stacks and Queues as a List

Neither is a new structure. Each is a list with a rule about which end you are allowed to touch — and the rule is the whole point.

The same storage, two access rules

📚 Stack — LIFO

RuleLast In, First Out. Add and remove at the SAME end.

Operationspush (add), pop (remove), peek (look without removing).

CostAll O(1) — one end, no shifting.

🚶 Queue — FIFO

RuleFirst In, First Out. Add at one end (rear), remove from the other (front).

Operationsenqueue (add at rear), dequeue (remove from front).

CostO(1) each — if implemented carefully. See below.

Restricting access is not a limitation being worked around; it is the feature. A structure that guarantees LIFO ordering can be reasoned about — you know what comes out next without inspecting it — and that guarantee is what makes a stack the right model for function calls, undo history and expression evaluation.

The queue trap: why a naive array queue fails

Queue in an array, front at index 0: enqueue A, B, C [A][B][C][ ][ ] dequeue [B][C][ ][ ][ ] ← everything shifted O(n) per dequeue Worse, using a moving front pointer instead: after 3 dequeues [ ][ ][ ][D][E] the front two slots are free but UNUSABLE — the rear pointer has run out of room.

The fix is a circular queue: when the rear pointer reaches the end of the array it wraps to the beginning, reusing the vacated slots. Both operations return to O(1), and no element ever moves.

💡 The circular queue's classic exam point is telling full from empty. In both states front and rear meet, so the pointers alone cannot distinguish them. The usual answers are to keep a count of stored elements, or to deliberately leave one slot unused so that "rear is one behind front" means full and "rear equals front" means empty.

What each is used for, and why

Stack — anywhere the most recent thing must be handled first. Function calls, because the innermost call must return before its caller. Undo, because the last action is the one to reverse. Expression evaluation and bracket matching, because the most recent unclosed bracket is the one a closing bracket belongs to. Depth-first traversal, for the same reason.

Queue — anywhere fairness matters. Print jobs, process scheduling, and breadth-first traversal, where every node at one depth must be handled before any node deeper.

🔧 The pairing is worth remembering as a single fact: depth-first uses a stack, breadth-first uses a queue. That is not a convention, it follows from the ordering — going deep means handling the most recently discovered node first, going wide means handling the earliest discovered node first. Recursion uses a stack implicitly, which is why depth-first traversals are usually written recursively and breadth-first ones are not.

Commonly confused

Stack the structure and the call stack. The second is an instance of the first — the memory region holding call frames, managed exactly LIFO.

Queue and priority queue. A queue serves in arrival order. A priority queue serves by priority regardless of arrival, and is usually a heap rather than a list.

Peek and pop. Peek reads the top; pop removes it.

Rapid revision

Stack: one end, LIFO. Queue: two ends, FIFO.

A naive array queue is O(n) per dequeue or leaks slots — use a circular queue.

Full and empty look identical in a circular queue: keep a count or waste one slot.

Depth-first → stack. Breadth-first → queue.

Syllabus points

Stack/queue represented using lists

Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.