Write the operations.

Stacks and queues in code.

In the lab, fill the circular queue, dequeue a few items and enqueue again: the rear pointer wraps round to index 0. The pseudocode below does exactly what the lab does, using a count to tell a full queue from an empty one.

DECLARE Stack : ARRAY[0:7] OF INTEGER
DECLARE TopPointer : INTEGER       // -1 when the stack is empty

PROCEDURE Push(Item : INTEGER)
    IF TopPointer = 7 THEN
        OUTPUT "Stack full"
    ELSE
        TopPointer ← TopPointer + 1
        Stack[TopPointer] ← Item
    ENDIF
ENDPROCEDURE

FUNCTION Pop() RETURNS INTEGER
    DECLARE Item : INTEGER
    IF TopPointer = -1 THEN
        OUTPUT "Stack empty"
        RETURN -1
    ENDIF
    Item ← Stack[TopPointer]
    TopPointer ← TopPointer - 1
    RETURN Item
ENDFUNCTION

DECLARE Queue : ARRAY[0:5] OF INTEGER
DECLARE FrontPointer : INTEGER     // starts at 0
DECLARE RearPointer : INTEGER      // starts at -1
DECLARE NumberInQueue : INTEGER    // starts at 0

PROCEDURE Enqueue(Item : INTEGER)
    IF NumberInQueue = 6 THEN
        OUTPUT "Queue full"
    ELSE
        RearPointer ← (RearPointer + 1) MOD 6
        Queue[RearPointer] ← Item
        NumberInQueue ← NumberInQueue + 1
    ENDIF
ENDPROCEDURE

FUNCTION Dequeue() RETURNS INTEGER
    DECLARE Item : INTEGER
    IF NumberInQueue = 0 THEN
        OUTPUT "Queue empty"
        RETURN -1
    ENDIF
    Item ← Queue[FrontPointer]
    FrontPointer ← (FrontPointer + 1) MOD 6
    NumberInQueue ← NumberInQueue - 1
    RETURN Item
ENDFUNCTION

• Check first: every insert tests for full (overflow) and every delete tests for empty (underflow) before touching a pointer. These checks are separate mark points.
• Order of steps: Push moves the pointer then stores; Pop reads then moves the pointer. Enqueue moves the rear pointer then stores; Dequeue reads at the front then moves the front pointer.
• −1 as a rogue value: returning −1 for "empty" only works if −1 can never be real data. Otherwise return a Boolean through a BYREF parameter.

Linked lists in code.

In the lab, insert and delete items and watch only the pointers change. Below, the list is an array of records, each with a Data field and a Pointer field. The table shows the starting state used in the examples.

StartPointer = 1, FreeListPointer = 2. The list is Ava → Bea → Cole → Dan → Eli → null; the free list is 2 → 5 → 7 → null.

TYPE ListNode
    DECLARE Data : STRING
    DECLARE Pointer : INTEGER
ENDTYPE
DECLARE List : ARRAY[0:7] OF ListNode
DECLARE StartPointer : INTEGER
DECLARE FreeListPointer : INTEGER
CONSTANT NullPointer = -1

FUNCTION FindItem(SearchItem : STRING) RETURNS INTEGER
    DECLARE Current : INTEGER
    Current ← StartPointer
    WHILE Current <> NullPointer
        IF List[Current].Data = SearchItem THEN
            RETURN Current
        ENDIF
        Current ← List[Current].Pointer
    ENDWHILE
    RETURN NullPointer
ENDFUNCTION

PROCEDURE DeleteItem(DeleteThis : STRING)
    DECLARE Current : INTEGER
    DECLARE Previous : INTEGER
    DECLARE Found : BOOLEAN
    Current ← StartPointer
    Previous ← NullPointer
    Found ← FALSE
    WHILE Current <> NullPointer AND Found = FALSE
        IF List[Current].Data = DeleteThis THEN
            Found ← TRUE
        ELSE
            Previous ← Current
            Current ← List[Current].Pointer
        ENDIF
    ENDWHILE
    IF Found = TRUE THEN
        IF Previous = NullPointer THEN
            StartPointer ← List[Current].Pointer
        ELSE
            List[Previous].Pointer ← List[Current].Pointer
        ENDIF
        List[Current].Pointer ← FreeListPointer
        FreeListPointer ← Current
    ENDIF
ENDPROCEDURE

Trees, dictionaries and graphs.

In the lab, insert a value into the binary tree and watch the comparisons from the root: left if smaller, right if larger or equal, until a null pointer is found. The new node is attached there. Then search for a value that is not in the tree.

TYPE TreeNode
    DECLARE LeftPointer : INTEGER
    DECLARE Data : INTEGER
    DECLARE RightPointer : INTEGER
ENDTYPE
DECLARE Tree : ARRAY[0:9] OF TreeNode
DECLARE RootPointer : INTEGER
DECLARE FreePointer : INTEGER
CONSTANT NullPointer = -1

PROCEDURE InsertNode(NewItem : INTEGER)
    DECLARE NewNode : INTEGER
    DECLARE Current : INTEGER
    DECLARE Previous : INTEGER
    DECLARE GoLeft : BOOLEAN
    IF FreePointer = NullPointer THEN
        OUTPUT "Tree full"
    ELSE
        NewNode ← FreePointer
        FreePointer ← Tree[NewNode].LeftPointer
        Tree[NewNode].Data ← NewItem
        Tree[NewNode].LeftPointer ← NullPointer
        Tree[NewNode].RightPointer ← NullPointer
        IF RootPointer = NullPointer THEN
            RootPointer ← NewNode
        ELSE
            Current ← RootPointer
            WHILE Current <> NullPointer
                Previous ← Current
                IF NewItem < Tree[Current].Data THEN
                    GoLeft ← TRUE
                    Current ← Tree[Current].LeftPointer
                ELSE
                    GoLeft ← FALSE
                    Current ← Tree[Current].RightPointer
                ENDIF
            ENDWHILE
            IF GoLeft = TRUE THEN
                Tree[Previous].LeftPointer ← NewNode
            ELSE
                Tree[Previous].RightPointer ← NewNode
            ENDIF
        ENDIF
    ENDIF
ENDPROCEDURE

• Find in a binary tree: start at the root; if the node holds the item, stop; if the item is smaller go left, otherwise go right; reaching a null pointer means it is not there. A balanced tree of n nodes needs about log₂ n comparisons, but a tree built from sorted data is one long branch and needs up to n.
• Dictionary: an ADT of key-value pairs with unique keys; operations add a pair, look up the value for a key, and delete a pair. It can be built from two parallel arrays, an array of records, or a hash table for fast look-up.
• Graph: a set of vertices (nodes) joined by edges (arcs). Edges may be directed (one way) or undirected, and weighted (a cost, distance or time). Unlike a tree, a graph can contain cycles and has no root. Use it to model road maps, computer networks, social networks or dependencies. (You will not be asked to code a graph.)
• ADTs from ADTs: a stack, a queue, a linked list or a binary tree can be built from an array (of records) and pointers; a queue can be built from two stacks; a stack can be built from a linked list by always inserting and deleting at the start; a dictionary can be built from a hash table.