Implementing ADTs using arrays
Introduced| English | Meaning |
|---|---|
| overflow/ˌəʊvəˈfləʊ/ | A condition in which a result exceeds the range representable by the available storage or number format. |
| underflow/ˌʌndəˈfləʊ/ | A numerical result too close to zero to be represented normally in the chosen number format. |
| circular array/ˈsɜːkjʊlə əˈreɪ/ | An array used so that moving beyond its last position wraps around to the first, for example in a circular queue. |
| free list/friː lɪst/ | A data structure recording available memory blocks or other unused storage locations. |
There is no such thing as a stack in memory
- Open a computer and look for the stack. You will not find one. Memory is one enormous array of numbered cells, and that is all there is.
- Every stack, every queue, every linked list is that array plus two or three integer variables that remember where things are. Push is "add one to a number and store"; dequeue is "read a cell and add one to a different number".
- The whole of this lesson is bookkeeping: which pointers, which checks, and what happens at the edges.
- The exam asks you to describe the declarations, walk the pointers through a few operations, and say why the checks are there.
A stack in an array
- Hold the items in
Stack[1:MaxSize]with an integerTop, 0 when the stack is empty. - Push(x): if
Top = MaxSizethe stack is full, an overflow 溢出; otherwiseTop ← Top + 1andStack[Top] ← x. - Pop(): if
Top = 0the stack is empty, an underflow 下溢; otherwise returnStack[Top]andTop ← Top − 1.
The array never moves; only Top does
Pushing an item onto a stack that is already full causes a stack ______.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Overflow = push when Top = MaxSize; popping from an empty stack (Top = 0) is underflow.
Match each array-stack condition to what it means.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Top counts the items: 0 = empty, MaxSize = full; the two error cases are underflow and overflow.
Worked example: declare and initialise the stack
- Describe the declarations and initialisation needed to implement a stack of up to 50 integers using an array. [5]
- An array of 50 elements of type
INTEGER,DECLARE Stack : ARRAY[1:50] OF INTEGER, to hold the items. - A constant or variable
MaxSizeset to 50, so that push can test for full. - An
INTEGERtop-of-stack pointer,Top, initialised to 0 to show the stack is empty; pop tests it for underflow, and push compares it withMaxSizefor overflow.
Which belong in the declaration and initialisation of an array-based stack? Select all that apply.
Difficulty 2/5 · 140 coins + a small bonus on first completion today
A stack needs one pointer, Top. A front pointer belongs to a queue.
A queue in a plain array
- Two pointers:
Frontfor the next item to leave,Rearfor the next free space. Enqueue stores atRearand moves it on; dequeue reads atFrontand moves it on. - Both pointers only ever move forward, so after a few operations they march off the end of the array while the cells at the start sit empty and unusable.
- The fix is to let the pointers wrap around.
The circular array
- A circular array 循环数组 wraps a pointer back to the first cell when it passes the last: with 1-based indices,
Rear ← (Rear MOD MaxSize) + 1. - Enqueue(x): check not full;
Rear ← (Rear MOD MaxSize) + 1;Queue[Rear] ← x. Dequeue(): check not empty; returnQueue[Front];Front ← (Front MOD MaxSize) + 1. - Keep a separate count: when the queue is completely full and when it is completely empty the two pointers are in the same relative position, so the pointers alone cannot tell the two apart.
After the last cell comes the first cell
Implementing ADTs with arrays
FIFO
A queue is first-in-first-out — enqueue at the back, dequeue from the front.
Why use a circular array for a queue?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
(pointer MOD MaxSize) + 1 wraps the index back to the first cell, so a linear queue no longer wastes the cells Front has passed.
Worked example: walk the pointers
- With
MaxSize = 6: ifRear = 5, then(5 MOD 6) + 1 = 6, so the next item goes in cell 6. IfRear = 6, then(6 MOD 6) + 1 = 1: the pointer wraps to cell 1. - A circular queue is held in an array of size 5, indices 0 to 4, with
Front = 3,Rear = 3and one item stored. Two items are added, then two removed. With 0-based indices each move is(pointer + 1) MOD 5. - Adding twice moves
Rear: 3 → 4, then 4 → 0, because (4 + 1) MOD 5 = 0. Removing twice movesFront: 3 → 4 → 0. One item remains, at index 0, and the queue reused the cells freed at the start of the array.
A circular queue uses cells 1 to 6 and Rear = 6. After Rear ← (Rear MOD 6) + 1, where does the next item go?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
6 MOD 6 = 0, plus 1 gives 1. The pointer wraps to the start of the array.
Worked example: the enqueue algorithm in words
- Describe the algorithm for adding an item to a circular queue. [4]
- If the count equals the size, report that the queue is full and stop.
- Otherwise add one to the rear pointer; if it is now past the last index, set it to the first index.
- Store the item at the rear pointer and add one to the count.
Put the steps of adding to a circular queue in order.
Difficulty 3/5 · 200 coins + a small bonus on first completion today
Check, move, wrap, store, count. The wrap is what makes the array circular.
A linked list in an array
- Use an array of node records, each with a
NextIndexindex;-1marks the end. AHeadindex marks the first node,-1if the list is empty. - The unused slots are chained into a free list 空闲列表 from
FreeListHead, exactly as the data list chains its used ones.
TYPE TNode
DECLARE Value : INTEGER
DECLARE NextIndex : INTEGER // index of the next node, or -1
ENDTYPE
DECLARE Nodes : ARRAY[1:MaxSize] OF TNode
DECLARE Head : INTEGER // -1 when empty
DECLARE FreeListHead : INTEGER // first unused slot
- Insert: take the slot at
FreeListHead, set itsValueandNextIndex, then rewire the previous node'sNextIndexorHead. Delete: unlink the node and return its slot to the front of the free list.
Two lists share one array: the data list and the free list
In an array-based linked list, the free list:
Difficulty 1/5 · 100 coins + a small bonus on first completion today
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.
Worked example: insert into the array-held list
DataandPointerarrays hold the list 1 → 3 → 4, withStart = 1; index 1 holdsD40, index 3 holdsD32, index 4 holdsD11with a null pointer. The free list starts at index 2 and continues 2 → 5. InsertD6betweenD32andD11.- Take the first free node, index 2, and set
FreeStartto its pointer, 5. StoreD6inData[2]. - Set
Pointer[2]to the valuePointer[3]held, which is 4. Then setPointer[3]to 2. - The list now reads 1 → 3 → 2 → 4 and the free list is 5 → null. The implementation, if asked: an array for the data, a parallel array (or record field) for the pointers, a start pointer, and a free-list pointer.
In the worked example, after D6 is inserted the free list starts at index ____.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Index 2 was taken from the free list, so FreeStart moves to what index 2 pointed to, which was 5.
When inserting into the list, the previous node's pointer should be changed before the new node's pointer is set.
Difficulty 1/5 · 100 coins + a small bonus on first completion today
Set the new node's pointer to the old next node first. Rewiring the previous node first loses the address of the rest of the list.
Marks that slip away
- The checks come first: full before push or enqueue, empty before pop or dequeue. Describe them; they are marks.
- The wrap formula depends on the indices:
(Rear MOD MaxSize) + 1for 1-based,(Rear + 1) MOD Sizefor 0-based. Match the question's bounds. - The count is what tells a full circular queue from an empty one. Pointers alone cannot.
- Set the new node's
NextIndexbefore rewiring the previous node, and return a deleted node's slot to the free list, or the array slowly fills with unreachable cells.
You've got it
- stack in an array:
Stack[1:MaxSize]and aToppointer starting at 0;Top = MaxSizeis overflow,Top = 0is underflow - circular queue:
FrontandRearwrap withMOD; a separate count distinguishes full from empty - linked list in an array: node records with a
NextIndexindex, aHead, and a free list chaining the spare slots - every operation is check, then pointer arithmetic, then store or read; the ADT's behaviour is unchanged by how it is stored