Stacks and Queues

Abstract data types

A stack and a queue are abstract data types (ADTs) — logical models of how data is organised and accessed, independent of how they're physically stored (often implemented using an array or a linked list).

Stacks — LIFO

A stack follows Last In, First Out (LIFO): the last item pushed on is the first taken off — like a stack of plates. It uses a single pointer to the top of the stack.

Operations:

• push(item) — add to the top (check for stack overflow if full first).
• pop() — remove and return the top item (check for stack underflow if empty first).
• peek()/top() — look at the top item without removing it.
• isEmpty() / isFull().

Pseudocode for push:

if top == maxSize - 1 then
   report "stack overflow"
else
   top = top + 1
   stack[top] = item
endif

Uses: function call stack (storing return addresses), undo functions, reversing items, evaluating expressions, backtracking, converting/evaluating Reverse Polish Notation.

Queues — FIFO

A queue follows First In, First Out (FIFO): the first item added is the first removed — like a queue of people. It uses two pointers: front and rear.

Operations:

• enqueue(item) — add to the rear.
• dequeue() — remove from the front.
• isEmpty() / isFull().

Linear vs circular queue

• A linear queue wastes space as the front pointer advances (freed slots at the start can't be reused).
• A circular queue wraps the rear/front pointers back to the start using modulo arithmetic (rear = (rear + 1) MOD maxSize), reusing freed space efficiently.

Priority queue

Items are dequeued by priority rather than arrival order (e.g. an OS scheduling high-priority processes first).

Uses: print/job queues, buffering (keyboard input), breadth-first traversal, scheduling.

Comparison

	Stack	Queue
Order	LIFO	FIFO
Pointers	1 (top)	2 (front, rear)
Add / remove	push / pop (same end)	enqueue (rear) / dequeue (front)

Worked example

Items 3, 7, 5 are pushed onto a stack, then two pops occur. What is returned and what remains?

• Push order: 3, 7, 5 (5 on top). pop → 5, then pop → 7. The stack now holds only 3. ✓

Common mistakes

• Removing from the wrong end — stack pop and push are the same end; a queue removes from the front, adds at the rear.
• Forgetting to check for overflow/underflow before push/pop.
• Not using modulo for a circular queue's wrap-around.

Exam tips

• State the access rule (LIFO / FIFO) and the pointer(s) each structure uses.
• Be ready to write push/pop/enqueue/dequeue pseudocode with the overflow/underflow checks.
• Learn the circular-queue MOD wrap-around and why it beats a linear queue.

Key facts to remember

• Stack = LIFO, one top pointer, push/pop at the same end (function calls, undo, backtracking).
• Queue = FIFO, front and rear pointers (buffers, scheduling); circular queues reuse space via MOD.
• Both are ADTs, usually implemented with arrays or linked lists; always check overflow/underflow.