Stacks and Queues

An abstract data type (ADT) is defined by its operations and behaviour — not by how it is implemented internally. The interface specifies what the data structure can do; the implementation decides how it does it.

This separation matters because programs that use an ADT depend only on its operations. The underlying implementation can change (for example, switching from an array to a linked list) without affecting any code that uses it.

ADT	Key property	Core operations
Stack	Last In, First Out (LIFO)	push, pop, peek, isEmpty, isFull
Queue	First In, First Out (FIFO)	enqueue, dequeue, peek, isEmpty, isFull
Tree	Hierarchical parent-child links	insert, delete, traverse
Graph	Arbitrary node connections	addEdge, removeEdge, traverse

Two data structures covered in this lesson — stacks and queues — are fundamental ADTs that appear throughout computer science: in operating systems, compilers, network protocols, and algorithms.

A stack is a linear structure where elements are added and removed from the same end — the top. The last element added is the first to be removed: Last In, First Out (LIFO).

Operations:

Operation	Description	Effect on top pointer
push(item)	Add item to the top of the stack	top ← top + 1
pop()	Remove and return the top item	top ← top - 1
peek()	Return the top item without removing it	No change
isEmpty()	Return True if top = −1 (no items)	—
isFull()	Return True if top = maxSize − 1 (array-based implementation)	—

The top pointer holds the index of the current top element. An empty stack has top = −1. Attempting to pop from an empty stack causes a stack underflow error; pushing onto a full stack causes a stack overflow error.

A physical analogy: a stack of plates. You can only add or remove a plate from the top — you never insert into the middle.

Key applications: the call stack manages active function calls (each call pushes a frame; returning from a function pops it), undo/redo in editors, and bracket matching in compilers.

Trace the following operations on a stack with maxSize = 5.

Initial state: stack = [_, _, _, _, _], top = −1

Operation	Action	Stack state	top
push(10)	10 placed at index 0	[10, _, _, _, _]	0
push(20)	20 placed at index 1	[10, 20, _, _, _]	1
push(30)	30 placed at index 2	[10, 20, 30, _, _]	2
peek()	Returns 30; stack unchanged	[10, 20, 30, _, _]	2
pop()	Removes and returns 30	[10, 20, _, _, _]	1
push(40)	40 placed at index 2	[10, 20, 40, _, _]	2
pop()	Removes and returns 40	[10, 20, _, _, _]	1
pop()	Removes and returns 20	[10, _, _, _, _]	0

Note that push(40) reuses index 2 — the slot vacated by pop(). In an array-based implementation, the old data at index 2 (30) may still be present in memory, but it is inaccessible because top = 1. It is effectively overwritten on the next push.

A queue is a linear structure where elements are added at the rear and removed from the front. The first element added is the first to be removed: First In, First Out (FIFO).

Operations:

Operation	Description
enqueue(item)	Add item to the rear of the queue
dequeue()	Remove and return the item at the front
peek()	Return the front item without removing it
isEmpty()	Return True if front > rear (linear) or count = 0
isFull()	Return True if queue is at capacity

A queue uses two pointers: front (index of the next item to dequeue) and rear (index of the last item enqueued).

Trace (maxSize = 4):

Operation	Queue state	front	rear
Start	[_, _, _, _]	0	−1
enqueue(A)	[A, _, _, _]	0	0
enqueue(B)	[A, B, _, _]	0	1
enqueue(C)	[A, B, C, _]	0	2
dequeue()→A	[_, B, C, _]	1	2
enqueue(D)	[_, B, C, D]	1	3

Key applications: print queues, CPU job scheduling, and the breadth-first search graph algorithm all rely on FIFO processing.

In a linear queue, the front pointer only ever moves right. Once the front has advanced past several positions and the rear has reached the end of the array, the queue appears full — even though there is unused space at the beginning.

Example (maxSize = 4, continuing from previous trace):

State: [_, B, C, D], front = 1, rear = 3

Attempting enqueue(E): rear = 3 = maxSize − 1, so the queue reports full — but index 0 is empty.

A circular queue solves this by wrapping the rear pointer back to index 0 when it reaches the end of the array, using modulo arithmetic:

$\text{rear}=(\text{rear}+1)\mathrm{mod}\text{maxSize}$

Continuing the example with circular logic (maxSize = 4):

Operation	Queue state	front	rear	Calculation
enqueue(E)	[E, B, C, D]	1	0	(3+1) mod 4 = 0 → wrap to 0
dequeue()→B	[E, _, C, D]	2	0	front = (1+1) mod 4 = 2
dequeue()→C	[E, _, _, D]	3	0	front = (2+1) mod 4 = 3

After enqueue(E) wraps the rear pointer back to index 0, the array is full and the rear has wrapped around past the front:

The circular queue makes full use of the allocated array. A separate count variable (or front/rear comparison with a full flag) is used to distinguish between the empty and full states, since both have front = rear in a naive pointer-only implementation.

A priority queue is a variant of a queue where each item is assigned a priority value. When an item is removed, the item with the highest priority is dequeued first — regardless of arrival order. If two items share the same priority, they are served in FIFO order within that level.

Insertion works like a standard queue. Only removal is determined by priority, not arrival order.

Operations:

Operation	Description
enqueue(item, priority)	Add item with the given priority value
dequeue()	Remove and return the item with the highest priority
peek()	Return the highest-priority item without removing it
isEmpty()	Return True if the queue has no items
isFull()	Return True if the queue is at capacity

Worked example:

Operation	Queue contents (item : priority)	Returned
enqueue(A, 2)	[A:2]	—
enqueue(B, 5)	[A:2, B:5]	—
enqueue(C, 3)	[A:2, B:5, C:3]	—
dequeue()	[A:2, C:3]	B — priority 5 (highest)
dequeue()	[A:2]	C — priority 3
dequeue()	[]	A — priority 2 (lowest)

In a standard FIFO queue, A would be dequeued first because it arrived first. In a priority queue, B is dequeued first because priority 5 is the highest.

In this example, a higher number means higher priority. Priority ordering depends on the convention given by the question or system — some implementations treat a lower number as higher priority (e.g. priority 1 is served before priority 5). Always check the convention before tracing.

Typical applications: CPU scheduling (high-priority processes run before low-priority ones); Dijkstra's shortest-path algorithm (the node with the lowest accumulated cost is processed next, where lower cost = higher priority); emergency dispatch systems (critical cases are handled before routine ones).

1. Confusing LIFO and FIFO

A stack is LIFO — the most recently added item is the first removed. A queue is FIFO — the first item added is the first removed. Mix-ups cost easy marks. A memory prompt: a queue at a shop — first person in line is served first.

2. Forgetting to update the pointer after push or pop

After push(item), increment top before placing the item (or place at top + 1 and then increment). After pop(), decrement top after reading the value. Showing the wrong pointer state in a trace question loses marks even if the stack contents are correct.

3. Describing a linear queue as full when space exists at the front

A linear queue with front = 2, rear = 3, maxSize = 4 may report full because the rear pointer has reached the end of the array, even though indices 0 and 1 are empty. The mistake is saying the array has no unused space — there is unused space, but a linear queue cannot reuse it because the front pointer never moves back. A circular queue would reclaim those slots.

4. Using the wrong modulo for circular queue wrap-around

The formula is (rear + 1) mod maxSize, not (rear + 1) mod (maxSize − 1). Off-by-one errors in the modulus produce incorrect pointer values. Verify with a small worked example.

5. Treating peek and pop as the same operation

peek() (sometimes called top()) returns the top element without modifying the stack. pop() removes and returns it. After peek(), the top pointer is unchanged; after pop(), it decrements by 1.

6. Assuming dequeue returns the first-arrived item in a priority queue

In a priority queue, dequeue() returns the highest-priority item, not the one that arrived first. FIFO ordering applies only within items of equal priority — a later-arriving item with higher priority is served before an earlier-arriving item with lower priority.