8.5 Queue

Section	Topic	Main rule
8.4	Stack	Last in, first out
8.5	Queue	First in, first out
8.6	Binary trees	Data arranged using parent–child relationships
8.7	Hash tables	Keys are converted directly into array positions

Your earlier WA2 scope ended at Tutorial 8A, so these are the topics that come after that assessment scope. The full chapter learning outcomes include implementing stacks, queues, binary trees, tree traversals and hash tables with collision handling. 8.DataStructures.pdfPDF

1. Stack

A stack follows:

LIFO — Last In, First Out

Imagine a stack of plates:

TOP →   C
        B
        A

C was placed in last, so C must be removed first.

The notes begin the Stack section immediately after Tutorial 8A and define a stack as a structure where access is restricted to one end called the top. 8.DataStructures.pdfPDF

Important stack operations

Operation	Meaning
`push(item)`	Add an item to the top
`pop()`	Remove and return the top item
`peek()`	Return the top item without removing it
`isEmpty()`	Check whether the stack is empty
`len(stack)`	Find the number of items

Example

Starting with an empty stack:

push("A")     A

push("B")     B
              A

push("C")     C
              B
              A

Now:

pop()

removes C.

The stack becomes:

B
A

Using a Python list

stack = []
 
# Push items
stack.append("A")
stack.append("B")
stack.append("C")
 
# Look at the top item
print(stack[-1])       # C
 
# Pop the top item
item = stack.pop()
print(item)            # C

The end of the Python list represents the top of the stack.

Stack underflow and overflow

Stack underflow means trying to pop from an empty stack.

stack = []
stack.pop()             # Error

Stack overflow means trying to push into a fixed-size stack that is already full.

For example, if the stack capacity is 5 and it already contains 5 items, another push is not allowed.

What are stacks used for?

Stacks are commonly used for:

undo operations;
browser back buttons;
reversing data;
checking brackets;
function calls and recursion.

For example, when functions call other functions, information about each call is pushed onto the call stack. When a function finishes, its information is popped.

Stack implementation

Your notes implement stacks in two ways:

Stack ADT
├── ArrayStack
└── LinkedStack

The behaviour is the same. Only the internal storage changes.

With an array, top records the index of the top item. With a linked structure, the first node is normally treated as the top.

2. Queue

A queue follows:

FIFO — First In, First Out

Imagine students lining up at a canteen:

FRONT → A → B → C ← REAR

A joined first, so A leaves first.

The notes describe insertion at the rear and removal from the front. 8.DataStructures.pdfPDF

Important queue operations

Operation	Meaning
`enqueue(item)`	Add an item at the rear
`dequeue()`	Remove and return the front item
`peek()`	Return the front item without removing it
`isEmpty()`	Check whether the queue is empty
`len(queue)`	Find the number of items

Example

Starting empty:

enqueue("A")

FRONT → A ← REAR

Then:

enqueue("B")
enqueue("C")

The queue becomes:

FRONT → A → B → C ← REAR

Now:

dequeue()

removes A, not C.

The queue becomes:

FRONT → B → C ← REAR

This is the main difference:

Stack: remove newest item
Queue: remove oldest item

Simple Python representation

queue = []

# Enqueue
queue.append("A")
queue.append("B")
queue.append("C")

# Peek at front
print(queue[0])         # A

# Dequeue
item = queue.pop(0)
print(item)             # A

This shows the idea, although removing index 0 requires the remaining Python-list items to shift.

Queue using a linked list

A linked queue keeps two pointers:

front                         rear
  ↓                             ↓
 [A | •] → [B | •] → [C | None]

Why use both?

front allows fast deletion;
rear allows fast insertion.

To enqueue a new node D:

1. Create D
2. Make the old rear point to D
3. Move rear to D

Your notes specifically describe these three linked-queue enqueue steps. 8.DataStructures.pdfPDF

To dequeue:

1. Save the item at front
2. Move front to front.next
3. Return the saved item

If the last item is removed, both front and rear should become None.

3. Circular queue

A normal fixed-size array queue may appear full even when there are unused spaces at the beginning.

Suppose the array has five cells:

Index:  0    1    2    3    4
       [ ]  [ ]  [C]  [D]  [E]
                  ↑         ↑
                front      rear

Cells 0 and 1 are empty, but rear has reached the final array position.

A circular queue allows rear to wrap back to the beginning:

0 → 1 → 2 → 3 → 4
↑                 ↓
└─────────────────┘

The movement is normally:

rear = (rear + 1) % capacity

For a capacity of 5:

rear = 4

(4 + 1) % 5
= 0

So the next position becomes index 0.

A circular queue does not physically form a circle. The index calculation behaves circularly.

A simple implementation often tracks:

self._front
self._rear
self._size
self._items

Then:

Empty when size == 0
Full when size == capacity

4. Binary tree

Stacks, queues and linked lists are linear:

A → B → C → D

A tree is non-linear:

The notes explain that trees replace the ideas of predecessor and successor with parent and child. Every node except the root has exactly one parent. 8.DataStructures.pdfPDF

Tree vocabulary

Using this tree:

A is the root.
A is the parent of B and C.
B and C are children of A.
D and E are children of B.
D, E and C are leaf nodes because they have no children.
The tree beginning at B is a subtree.

Binary tree

A binary tree is a tree where every node has at most two children:

left child
right child

A node may have:

0 children
1 child
2 children

It cannot have three children. 8.DataStructures.pdfPDF

A tree node can be represented as:

class TreeNode:
    def __init__(self, data):
        self.left = None
        self.data = data
        self.right = None

Each node contains:

left pointer | data | right pointer

5. Binary search tree

A binary search tree, or BST, follows an ordering rule:

Values smaller than a node go left.
Values larger than a node go right.

Example:

        8
       / \
      3   10
     / \    \
    1   6    14

For the root 8:

3, 1 and 6 are smaller, so they are on the left;
10 and 14 are larger, so they are on the right.

Your notes define the same left-smaller and right-greater rule. 8.DataStructures.pdfPDF

Searching for 6

Start at 8:

6 < 8
Go left

Reach 3:

6 > 3
Go right

Reach 6:

Found

You do not need to inspect every node.

Inserting 5

Start at 8:

5 < 8 → left

At 3:

5 > 3 → right

At 6:

5 < 6 → left

The left side of 6 is empty, so insert 5 there:

        8
       / \
      3   10
     / \    \
    1   6    14
       /
      5

The notes exclude deletion from a binary search tree, so you mainly need to know creation, search, insertion and traversal.

6. Tree traversals

A traversal means visiting every node.

Consider:

There are three main depth-first traversals.

Pre-order

Root → Left → Right

Mnemonic:

NLR
Node, Left, Right

Result:

A, B, D, E, C

In-order

Left → Root → Right

Mnemonic:

LNR
Left, Node, Right

Result:

D, B, E, A, C

For a binary search tree, in-order traversal returns the values in ascending order.

For example:

        8
       / \
      3   10
     / \    \
    1   6    14

In-order:

1, 3, 6, 8, 10, 14

Post-order

Left → Right → Root

Mnemonic:

LRN
Left, Right, Node

Result:

D, E, B, C, A

A useful memory pattern is:

Pre-order:  Root first
In-order:   Root in the middle
Post-order: Root last

Breadth-first search

Breadth-first search visits the tree level by level:

        A          Level 0
       / \
      B   C        Level 1
     / \
    D   E          Level 2

Order:

A, B, C, D, E

BFS normally uses a queue.

Depth-first search

Depth-first search travels as far down one branch as possible before returning.

It normally uses:

recursion; or
a stack.

Pre-order, in-order and post-order are different forms of depth-first traversal.

7. Hash table

A hash table stores data in an array but uses a hash function to calculate where an item should go.

Suppose the hash table has 11 positions:

def hash_function(key):
    return key % 11

For key 26:

26 % 11 = 4

So key 26 should be stored at index 4.

Index: 0  1  2  3  4  5  6  7  8  9  10
                     26

This can make searching very fast:

Calculate hash → go directly to expected position

Collision

A collision happens when two keys generate the same index.

For example:

26 % 11 = 4
15 % 11 = 4

Both keys want index 4.

The notes teach two collision-handling methods:

1. Linear probing
2. Chaining

8.DataStructures.pdfPDF

Linear probing

If the calculated position is occupied, check the next position.

Insert 26:

26 % 11 = 4
Store at index 4

Insert 15:

15 % 11 = 4
Index 4 occupied
Check index 5
Store at index 5

Result:

Index: 0  1  2  3   4   5  6  7  8  9  10
                   [26][15]

If the search reaches the end of the array, it wraps around to index 0.

Chaining

Each array position stores a linked list of items.

Index 4 → 26 → 15 → 37

All three values can remain connected to index 4.

The basic difference is:

Linear probing:
Store colliding items in other array positions.

Chaining:
Store colliding items in a linked list at the same position.

Good hash function

A good hash function should:

distribute keys evenly;
always produce the same result for the same key;
be fast to calculate.

Poor distribution creates many collisions and slows down searching. 8.DataStructures.pdfPDF

The entire second half in one picture

DATA STRUCTURES AFTER TUTORIAL 8A

Stack
└── LIFO
    ├── push
    ├── pop
    └── peek

Queue
└── FIFO
    ├── enqueue at rear
    ├── dequeue from front
    ├── linear queue
    └── circular queue

Binary Tree
├── root, parent, child, leaf
├── Binary Search Tree
├── pre-order
├── in-order
├── post-order
├── breadth-first search
└── depth-first search

Hash Table
├── hash function
├── collision
├── linear probing
└── chaining

The best order to learn this is Stack → Queue → Binary trees → Hash tables, because queues and stacks are later used to perform tree traversals.

Quartz 5

Explorer

8. Data Structure (8.5-8.7)

1. Stack

Important stack operations

Example

Using a Python list

Stack underflow and overflow

What are stacks used for?

Stack implementation

2. Queue

Important queue operations

Example

Simple Python representation

Queue using a linked list

3. Circular queue

4. Binary tree

Tree vocabulary

Binary tree

5. Binary search tree

Searching for 6

Inserting 5

6. Tree traversals

Pre-order

In-order

Post-order

Breadth-first search

Depth-first search

7. Hash table

Collision

Linear probing

Chaining

Good hash function

The entire second half in one picture

Graph View

Table of Contents