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.