Describe how a queue, stack and linked list can be implemented using arrays

Implementing Stacks, Queues and Linked Lists Using Arrays

1. Why use arrays for ADTs?

• Contiguous memory gives O(1) access by index – ideal for exam‑style algorithms.
• Fixed maximum size forces the programmer to handle overflow/underflow explicitly, a common Cambridge exam requirement.
• Only a few extra variables (top, front, rear, head, free) are needed to give the array the behaviour of a stack, queue or (static) linked list.

2. Assessment Objectives (AO)

3. Stack – LIFO (Last‑In, First‑Out)

3.1 Concept

A stack stores items so that the most recently added item is the first to be removed.

3.2 Array implementation

• Array: stack[0 … N‑1]
• Pointer: top – index of the current top element (‑1 when empty)

3.3 Initialisation

INTEGER top ← -1               // empty stack
INTEGER N   ← size of stack    // maximum capacity

3.4 Operations (Cambridge‑style pseudocode)

PROCEDURE Push(value)
    IF top = N‑1 THEN
        DISPLAY "Stack overflow"
        RETURN
    ENDIF
    top ← top + 1
    stack[top] ← value
END PROCEDURE

FUNCTION Pop() RETURNS INTEGER
    IF top = -1 THEN
        DISPLAY "Stack underflow"
        RETURN -1               // sentinel
    ENDIF
    value ← stack[top]
    top ← top - 1
    RETURN value
END FUNCTION

FUNCTION Peek() RETURNS INTEGER
    IF top = -1 THEN
        DISPLAY "Stack empty"
        RETURN -1
    ENDIF
    RETURN stack[top]
END FUNCTION

3.5 Worked example

Push the values 5, 8, 3 onto a stack of size 5, then pop twice.

1. After pushes: top = 2, stack = [5,8,3,_,_]
2. First pop returns 3, top = 1
3. Second pop returns 8, top = 0

3.6 Common pitfalls (exam focus)

• Checking top = N‑1 *before* inserting – prevents writing past the array.
• Using top = 0 as the empty condition (the correct sentinel is -1).
• Forgetting to reset the array element after a pop – not required for correctness but useful for debugging.

4. Queue – FIFO (First‑In, First‑Out)

4.1 Concept

A queue removes items in the same order they were added.

4.2 Array implementation – circular buffer

• Array: queue[0 … N‑1]
• Indices: front (position of first element) and rear (position for next insertion)
• Variable size to distinguish empty from full.

4.3 Initialisation

INTEGER front ← 0
INTEGER rear  ← 0
INTEGER size  ← 0
INTEGER N     ← size of queue

4.4 Operations (Cambridge‑style pseudocode)

PROCEDURE Enqueue(value)
    IF size = N THEN
        DISPLAY "Queue overflow"
        RETURN
    ENDIF
    queue[rear] ← value
    rear ← (rear + 1) MOD N
    size ← size + 1
END PROCEDURE

FUNCTION Dequeue() RETURNS INTEGER
    IF size = 0 THEN
        DISPLAY "Queue underflow"
        RETURN -1
    ENDIF
    value ← queue[front]
    front ← (front + 1) MOD N
    size ← size - 1
    RETURN value
END FUNCTION

FUNCTION Peek() RETURNS INTEGER
    IF size = 0 THEN
        DISPLAY "Queue empty"
        RETURN -1
    ENDIF
    RETURN queue[front]
END FUNCTION

4.5 Worked example

Enqueue 10, 20, 30 into a queue of size 4, then dequeue twice.

1. After enqueues: front = 0, rear = 3, size = 3, queue = [10,20,30,_]
2. First dequeue returns 10, front = 1, size = 2
3. Second dequeue returns 20, front = 2, size = 1

4.6 Common pitfalls (exam focus)

• Using front = rear alone to test emptiness – you cannot tell full from empty without a size counter or a “one slot empty” rule.
• Omitting the modulo operation when advancing front or rear – leads to index‑out‑of‑range errors.
• Updating size before moving the pointer (or vice‑versa) – causes off‑by‑one bugs.

5. Static Linked List Using Arrays

5.1 Concept

A static (or “array‑based”) linked list replaces dynamic memory allocation with two parallel arrays:

• data[0 … N‑1] – stores the actual values.
• next[0 … N‑1] – stores the index of the next node; -1 denotes “null”.

A head variable points to the first logical node, and a free list (implemented as a stack of unused indices) manages allocation.

5.2 Initialisation

PROCEDURE InitialiseStaticList()
    FOR i ← 0 TO N‑1 DO
        next[i] ← i + 1               // build free list
    ENDFOR
    next[N‑1] ← -1                    // end of free list
    head ← -1                         // logical list empty
    free ← 0                          // first free cell
END PROCEDURE

5.3 Core operations

Insert at the beginning (head)

PROCEDURE InsertHead(value)
    IF free = -1 THEN
        DISPLAY "Static list overflow"
        RETURN
    ENDIF
    newNode ← free                    // take first free cell
    free ← next[free]                // remove it from free list
    data[newNode] ← value
    next[newNode] ← head
    head ← newNode
END PROCEDURE

Delete the first node

FUNCTION DeleteHead() RETURNS INTEGER
    IF head = -1 THEN
        DISPLAY "Static list underflow"
        RETURN -1
    ENDIF
    delNode ← head
    head ← next[head]                // advance head
    value ← data[delNode]            // optional return
    next[delNode] ← free             // return node to free list
    free ← delNode
    RETURN value
END FUNCTION

Search for a value (linear traversal)

FUNCTION Search(target) RETURNS INTEGER
    index ← head
    WHILE index ≠ -1 DO
        IF data[index] = target THEN
            RETURN index            // found
        ENDIF
        index ← next[index]
    ENDWHILE
    RETURN -1                       // not found
END FUNCTION

Insert after a given position (general case)

PROCEDURE InsertAfter(pos, value)
    IF pos = -1 THEN                // treat as InsertHead
        InsertHead(value)
        RETURN
    ENDIF
    IF free = -1 THEN
        DISPLAY "Static list overflow"
        RETURN
    ENDIF
    newNode ← free
    free ← next[free]
    data[newNode] ← value
    next[newNode] ← next[pos]
    next[pos] ← newNode
END PROCEDURE

Delete a node given its index

PROCEDURE DeleteNode(pos)
    IF head = -1 OR pos = -1 THEN
        DISPLAY "Invalid delete"
        RETURN
    ENDIF
    IF pos = head THEN
        CALL DeleteHead()
        RETURN
    ENDIF
    // find predecessor
    pred ← head
    WHILE pred ≠ -1 AND next[pred] ≠ pos DO
        pred ← next[pred]
    ENDWHILE
    IF pred = -1 THEN
        DISPLAY "Node not found"
        RETURN
    ENDIF
    next[pred] ← next[pos]          // bypass node
    next[pos] ← free                 // return to free list
    free ← pos
END PROCEDURE

5.4 Complexity summary

5.5 Common pitfalls (exam focus)

• Forgetting to update free after an insertion – leads to “memory leaks” inside the static list.
• Using -1 both for “null” and for a legitimate array index – initialise head and free correctly.
• When deleting, move head *before* returning the node to the free list; otherwise the list can become corrupted.

6. Comparison of Operations (Array‑based ADTs)

7. Link to the Cambridge AS & A‑Level Syllabus (9618)

8. Practical Component (Paper 4 – Programming)

Students should complete the following lab in Java (or Python) and submit the source code with a short test report.

1. Setup – IDE (Eclipse/IntelliJ or VS Code), JDK 17 or Python 3.10.
2. Task A – Stack
   • Implement a class ArrayStack with methods push, pop, peek.
   • Write a driver that pushes 10 integers, then pops and prints them.
   • Include test cases for overflow and underflow.
3. Task B – Queue
   • Implement a class CircularQueue using a circular buffer.
   • Demonstrate enqueue/dequeue with at least 8 operations, showing wrap‑around.
   • Test full‑queue and empty‑queue conditions.
4. Task C – Static Linked List
   • Create two parallel arrays data[] and next[] inside a class StaticList.
   • Provide methods insertHead, deleteHead, search, and insertAfter.
   • Write a driver that builds the list 5 → 3 → 9, searches for 3, deletes the head, then prints the remaining elements.
5. Testing & maintenance checklist
   • Boundary testing (empty, full, single element).
   • Code comments using Cambridge pseudocode conventions.
   • Complexity annotation in the source file.

9. Key Points to Remember

• All array‑based ADTs have a **fixed maximum capacity** – always check for overflow/underflow.
• A **circular buffer** is essential for an efficient queue; it eliminates costly element shifting.
• A **static linked list** gives the logical flexibility of a linked list while keeping memory usage predictable – useful for exam questions that forbid dynamic allocation.
• When answering exam questions, use Cambridge pseudocode style (capitalised keywords, explicit IF … THEN … ENDIF, separate PROCEDURE/FUNCTION blocks) and always state the time complexity of each operation.

10. Diagram Suggestions (to be drawn by the student)

• Stack – array with a top arrow pointing to the last filled cell.
• Queue – circular array showing front and rear positions, with arrows indicating the direction of movement.
• Static linked list – two parallel columns (data and next) with arrows linking indices, plus separate arrows for head and free pointers.