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 |
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 ______.
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.
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.
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?
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.
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?
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.
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
Nextindex;-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 Next : 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 itsValueandNext, then rewire the previous node'sNextorHead. 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:
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 ____.
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.
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
Nextbefore 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
Nextindex, 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