Implementing ADTs using arrays
| English | Chinese | Pinyin |
|---|---|---|
| overflow | 溢出 | yì chū |
| underflow | 下溢 | xià yì |
| circular array | 循环数组 | xún huán shù zǔ |
| free list | 空闲列表 | kòng xián liè biǎo |
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.
A 2-D array (a table) with row and column indices
Implementing ADTs with arrays
FIFO
A queue is first-in-first-out — enqueue at the back, dequeue from the front.
Pushing an item onto a stack that is already full causes a stack ______.
Overflow = push when Top = MaxSize; popping from an empty stack (Top = 0) is underflow.
Match each array-stack condition to what it means.
Top counts the items: 0 = empty, MaxSize = full; the two error cases are underflow and overflow.
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.
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.
A circular queue uses MOD so the front/rear pointers wrap around and reuse the cells freed at the start of the array.
(pointer MOD MaxSize) + 1 wraps the index back to the first cell, so a linear queue no longer wastes the cells Front has passed.
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.
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
- 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