OCR A Level CS 2.3.2 Algorithms for the Main Data Structures

What is a stack?

A First-In, Last-Out (FILO) data structure where elements are added and removed from the top.

What operations are used with stacks?

✅ push(element) – Adds an element to the top
✅ pop() – Removes and returns the top element
✅ peek() – Returns the top element without removing it
✅ isEmpty() – Checks if the stack is empty
✅ size() – Returns the number of elements

How do you check if a stack is empty?

isEmpty():

if top < 0:

return True

else:

return False

How does the pop() operation work?

pop():

if isEmpty():

return error

else:

toRemove = A[top]

top -= 1

return toRemove

What is a queue?

A First-In, First-Out (FIFO) data structure where elements are added at the back and removed from the front.

What operations are used with queues?

✅ enqueue(element) – Adds an element to the back
✅ dequeue() – Removes and returns the front element
✅ peek() – Returns the front element without removing it
✅ isEmpty() – Checks if the queue is empty
✅ size() – Returns the number of elements

How do you add an element to a queue (enqueue)?

enqueue(element):

A[back] = element

back += 1

How does the dequeue() operation work?

dequeue():

if isEmpty():

return error

else:

toDequeue = A[front]

front += 1

return toDequeue

What is a linked list?

A dynamic data structure made up of nodes, where each node contains:

• Data

• A pointer to the next node

What are the key parts of a linked list?

✅ Head – The first node
✅ Tail – The last node
✅ N.next – Pointer to the next node

How do you search in a linked list?

Use a linear search by following the next pointers until the item is found.

What is a tree?

A hierarchical data structure made up of nodes connected by edges, where:

• The top node is called the root

• Each node has child nodes

• Leaves are nodes with no children

What are the two types of tree traversal?

✅ Depth-First Search (DFS) - Post-Order Traversal
✅ Breadth-First Search (BFS)

How does Depth-First Search (DFS) work?

The algorithm goes as deep as possible, visiting the left child, then the right child, and finally the parent node.

What data structure is used for DFS?

A stack.

What is the order of traversal for this tree?

5

/ \

3 8

/ \

2 4

➡ Post-order DFS output: 2, 4, 3, 8, 5

How does Breadth-First Search (BFS) work?

Visits all child nodes first before moving to the next level.

What data structure is used for BFS?

A queue.

What is the order of traversal for this tree?

5

/ \

3 8

/ \

2 4

➡ BFS output: 5, 3, 8, 2, 4