Implementing ADTs using arrays
Building ADTs from arrays
- ADTs hide their implementation — and a common one is a plain array.
- A few pointers turn an array into a stack, a queue, or a linked list.
- This gives the flexibility of the ADT with the simple, static storage of an array.
A stack in an array
- Hold items in
Stack[1:MaxSize]with an integerTop(0 when empty). - Push(x): if
Top = MaxSizeit's full (overflow); elseTop ← Top + 1,Stack[Top] ← x. - Pop(): if
Top = 0it's empty (underflow); else returnStack[Top],Top ← Top − 1.
Practice
When implementing a stack in an array, "overflow" happens when you:
Overflow = pushing when Top = MaxSize. Popping from an empty stack (Top = 0) is underflow.
Practice
A stack stored in an array is empty when:
Top counts items; Top = 0 means none. Top = MaxSize means full.
A queue in a circular array
- A simple queue lets
Front/Rearmarch off the end, wasting the start. - A circular array wraps a pointer back to 1 when it reaches
MaxSize: - Enqueue(x):
Rear ← (Rear MOD MaxSize) + 1, thenQueue[Rear] ← x. - Dequeue(): return
Queue[Front], thenFront ← (Front MOD MaxSize) + 1. - Keep a separate count to tell empty from full.
Practice
Why use a circular array for a queue?
A linear queue wastes the cells at the start as Front advances; wrapping with MOD reuses them.
Practice
In a circular queue, the pointer wraps back to the start using which operator?
(pointer MOD MaxSize) + 1 wraps the index from the last cell back to cell 1.
A linked list in an array
- Use an array of node records, each with a
Nextindex (−1 = end):
TYPE TNode
DECLARE Value : INTEGER
DECLARE Next : INTEGER // index of the next node, or -1
ENDTYPE
- A
Headindex marks the first node; a free list chains the unused slots. - Insert: take a slot from the free list, set its value/Next, rewire the previous Next. Delete: unlink it and return its slot to the free list.
Practice
In an array-based linked list, the free list:
The free list links the spare slots, so an insert can grab one and a delete can return one — like a second linked list of empties.
You've got it
Key idea
- stack in an array: a
Toppointer; full → overflow, empty → underflow - circular queue: wrap
Front/RearwithMOD; keep a count for empty-vs-full - linked list in an array: node records with a
Nextindex + a free list of spare slots - this combines ADT flexibility with static array storage