Stacks

What is a stack?
 In A Level Computer Science, stacks are a last in first out (LIFO) data structure
 Items can only be added to or removed from the top of the stack
 Stacks are key structures in the computing world as they are used to reserve an action,
such as go back a page or undo
 A real-life example of a stack would be a pile (or stack) of plates at a buffet; you can only
take a plate from the top, and if you need to reach the bottom one you have to remove
all the others first
 It is often implemented using an array
 Where the maximum size required is known in advance, static stacks are preferred as
they are easier to implement and make more efficient use of memory
 A stack has 6 main operations, which can be seen below

Operation Description
isEmpty() This checks is the stack is empty by checking the value of the top pointer
This adds a new value to the end of the list, it will need to check the stack is not full
push(value)
before pushing to the stack.
This returns the top value of the stack. First check the stack is not empty by looking at
peek()
the value of the top pointer.
This removes and returns the top value of the stack. This first checks if the stack is not
pop()
empty by looking at the value of the top pointer.
size() Returns the size of the stack
Checks if the stack is full and returns the boolean value, this compares the stack size to
isFull()
the top pointer.

 Stacks use a pointer which points to the top of the stack, where the next piece of data
will be added (pushed) or the current piece of data can be removed (popped)
Adding & Removing Data From a Stack
Pushing data to a stack
 When pushing (adding) data to a stack, the data is pushed to the position of the pointer
 Once pushed, the pointer will increment by 1, signifying the top of the stack
 Since the stack is a static data structure, an attempt to push an item on to a full stack
is called a stack overflow

Visual example
 This would push Bunny onto the empty stack

 This would push Dog to the top of the stack

  This would push Ant to the top of the stack

Popping data from a stack

 When popping (removing) data from a stack, the data is popped from the position of the
pointer
 Once popped, the pointer will decrement by 1, to point at the new top of the stack
 Since the stack is a static data structure, an attempt to pop an item from an empty stack
is called a stack underflow

Visual example
 This would pop Ant From the top of the stack. The new top of the stack would become
Dog

 Note that the data that is „popped‟ isn‟t necessarily erased; the pointer 'top' moves to
show that Ant is no longer in the stack and depending on the implementation, Ant can be
deleted or replaced with a null value, or left to be overwritten
Worked Example
Stacks and queues are both data structures.

A stack is shown below before a set of operations are carried out on it.

Draw what the stack shown below would look like after the following operations:

pop(), push(“A”), push(“B”), pop(), push(“E”), push(“F”)

Pointer Data
→ Z
Y
X
2 marks

Answer:

 Start by using the operation pop() to remove Z from the top of the stack

Pointer Data
→ Y
X
 Use the operation push(“A”) to add A to the top of the stack

Pointer Data
→ A
Y
X
 Then use the operation push(“B”) to add B to the top of the stack

Pointer Data
→ B
A
Y
X
 Then use pop() to remove the top item in the stack

Pointer Data
→ A
Y
X
  Then use push(“E”) to add E to the top of the stack

Pointer Data
→ E
A
Y
X
 Finally use push(“F") to add F to the top of the stack

Pointer Data
→ F
E
A
Y
X
 F at the top of the stack with E directly below it [1]
 A,Y,X. directly below E (with no other entries) [1]

F
E
A
Y
X

Queues
What is a queue?
 A queue is a First in First out (FIFO) data structure
 Items are added to the end of the queue and removed from the front
o Imagine a queue in a shop where customers are served from the front and new
customers join the back
 A queue has a back (tail) pointer and a front (head) pointer.
 Much the same as with a stack, an attempt to enqueue an item when the queue is full is
called a queue overflow. Similarly, trying to dequeue an item from an empty queue is
called a queue underflow.
 A queue can be static or dynamic
 There are three types of queues

1. Linear Queue
2. Circular Queue
3. Priority Queue
Main operations
Operation Description
enQueue(value) Adding an element to the back of the queue
deQueue() Returning an element from the front of the queue
Return the value of the item from the front of the queue without removing it from the
peek()
queue
isEmpty() Check whether the queue is empty
isFull() Check whether the queue is full (if the size has a constraint)
Queue keywords
Keyword Definition
An abstract data structure that holds an ordered, linear sequence of items. It is a
Queue
First in First out structure.
FIFO First In First Out
Static Data
Has a fixed size and can’t change at run time.
Structure
Dynamic Data Able to adapt and accommodate changes to the data inside it so it doesn’t waste
Structure as much space in memory.
Pointer An object that stores a memory address
Linear Queues
What are linear queues?
 A linear queue is a data structure that consists of an array.
 Items are added to the next available space in the queue starting from the front
 Items are then removed from the front of the queue
Enqueue data
 Before adding an item to the queue you need to check that the queue is not full
 If the end of the array has not been reached, the rear index pointer is incremented and
the new item is added to the queue
 In the example below, you can see the queue as the data Adam, Brian and Linda are
enqueued.
Dequeue data
 Before removing an item from the queue, you need to make sure that the queue is not
empty
 If the queue is not empty the item at the front of the queue is returned and the front is
incremented by 1
 In the example below, you can see the queue as the data Adam is dequeued

Circular Queues
What are circular queues?
 A circular queue is a static array that has a fixed capacity
 It means that as you add items to the queue you will eventually reach the end of the
array
 When items are dequeued, space is freed up at the start of the array
 It would take time to move items up to the start of the array to free up space at the end,
so a Circular queue (or circular buffer) is implemented
 It reuses empty slots at the front of the array that are caused when items are dequeued
 As items are enqueued and the rear index pointer reaches the last position of the array,
it wraps around to point to the start of the array as long as it isn‟t full
 When items are dequeued the front index pointer will wrap around until it passes the rear
index points which would show the queue is empty
Enqueue data
 Before adding an item to the circular queue you need to check that the array is not full
 It will be full if the next position to be used is already occupied by the item at the front of
the queue
 If the queue is not full then the rear index pointer must be adjusted to reference the next
free position so that the new item can be added
 In the example below, you can see the circular queue as the data Lauren is enqueued.
Dequeue data
 Before removing an item from the queue, you need to make sure that the queue is not
empty
 If the queue is not empty the item at the front of the queue is returned
 If this is the only item that was in the queue the rear and front pointers are reset,
otherwise the pointer moves to reference the next item in the queue
 In the example below, you can see the queue as the data Adam is dequeued
Examiner Tips and Tricks
When asked to display a queue visually, make sure that you also identify the position of the
front and rear pointers.

Worked Example
The current contents of a queue called 'colours', have been implemented in an array are
shown below:

0 1 2 3 4 5 6 7
red yellow green blue grey
↑ front ↑ back
Front = 0
End = 4

The queue has the subprograms enqueue and dequeue. The subprogram 'enqueue' is used to
add items to the queue and the subprogram 'dequeue' removes items from the queue.

Use the following diagram to show the queue shown above after the following program
statements have run:

enqueue(“orange”)
dequeue()
enqueue(“maroon”)
dequeue()
dequeue()

4 marks
Answer:

1. The first thing is to enqueue orange.

0 1 2 3 4 5 6 7
red yellow green blue grey orange
↑ front ↑ back
2. Then apply a dequeue() this will remove the first item in the queue.

0 1 2 3 4 5 6 7
yellow green blue grey orange
↑ front ↑ back
3. Then enqueue maroon.

0 1 2 3 4 5 6 7
yellow green blue grey orange maroon
↑ front ↑ back
4. Then apply another dequeue to remove the next item from the front.

0 1 2 3 4 5 6 7
green blue grey orange maroon
↑ front ↑ back
5. Then apply the final dequeue command to remove the next item from the front.

0 1 2 3 4 5 6 7
blue grey orange maroon
↑ front ↑ back
 Elements are in the queue (correct four colours)
 … in the correct positions
 'Front' points to the first element in the queue
 'End 'points to the last element in the queue
Graphs
What is a Graph?
 A graph is a set of vertices/nodes that are connected by edges/pointers. Graphs can be
placed into the following categories:
 Directed Graph: The edges can only be traversed in one direction
 Undirected Graph: The edges can be traversed in both directions
 Weighted Graph: A value is attached to each edge

Computers are able to process graphs by using either an adjacency matrix or an adjacency
list.

The examples below will be illustrated using an adjacency matrix, more information on
programming using both matrices and lists is available in section 8.

Undirected, Unweighted Graph

For unweighted graphs:

 1 is set when an edge exists between 2 nodes

 0 is set when there is no edge between 2 nodes

Below is the adjacency matrix for an undirected, unweighted graph:

For this graph, the names are abbreviated to the first letter.

 The data in an adjacency matrix for an unweighted graph is symmetric

 To determine the presence or absence of an edge, you inspect the row (or column) that
represents a node. Example: If you wanted to see if there is an edge between Frogmore
and Hartlepool you can look at the cross-section of row 3 (for Frogmore) and column 4
(for Hartlepool)
  You need a method (e.g Dictionary) to record which row/column is used for a specific
node‟s edge data
 The data values for the nodes (in this example names of towns) are not stored in the
matrix

Directed, Unweighted Graph

Above is the adjacency matrix for a directed, unweighted graph.
For this graph, the names are abbreviated to the first letter.

 Due to the lack of symmetry in this matrix, you cannot access the data by both row and
column, you must know the direction in which the values are stored
 E.g.: In row 0 for Bolton there is only one neighbour (Dunkirk) because there is a single
directed edge from Bolton towards Dunkirk. This is because there are 3 edges directed
towards Bolton (from Dunkirk, Hartlepool and Frogmore)
 If you are implementing a graph as an adjacency matrix you will need to choose the
direction and make sure that the data is stored and accessed correctly

Undirected, Weighted Graph

 For weighted graphs the values of the weights are stored in the adjacency matrix
 If an edge does not exist between two nodes, then a very large number (normally the
infinity symbol ∞) is set
Above is the adjacency matrix for an undirected, unweighted graph.
For this graph, the names are abbreviated to the first letter.

Directed, Weighted Graph

Above is the adjacency matrix for a directed weighted graph:

For this graph, the names are abbreviated to the first letter.

The Applications of Graphs

Graphs have many uses in the world of Computer Science, for example:

 Social Networks
 Transport Networks
 Operating Systems
 Keyword Definition
A directed graph is a set of objects that are connected together, where the edges are
Directed Graph
directed from one vertex to another.
Undirected An undirected graph is a set of objects that are connected together, where the edges
Graph do not have a direction.
A weighted graph is a set of objects that are connected together, where a
Weighted Graph
weight is assigned to each edge.
Adjacency Also known as the connection matrix is a matrix containing rows and columns
Matrix which is used to present a simple labelled graph.
Adjacency List This is a collection of unordered lists used to represent a finite graph.
Vertices/Nodes A vertex (or node) of a graph is one of the objects that are connected.
An edge (or arc) is one of the connections between the nodes (or vertices) of the
Edges/Arcs
network.
A collection of names, definitions, and attributes about data elements that are being
Dictionary
used or captured in a database, information system, or part of a research project.

Graphs: Traversing, Adding & Removing Data

How do you traverse a graph?
 There are two approaches to traversing a graph:
o A breadth-first search
o A depth-first search

Breadth-first search
 A breadth-first search is a graph traversal algorithm which systematically visits all
neighbours of a given vertex before moving on to their neighbours. It then repeats this
layer by layer.
 This method makes use of a queue data structure to enqueue each node as long as it is
not already in a list of visited nodes.
 1. Take the example above, the root node, Dunkirk, would be set as the current node and
then added to the visited list

Dunkirk
1. Moving from left to right, we must check if the connected node isn't already in the visited
list, if it is not, it is enqueued to the queue.

The first version of the queue would have appeared as

Front Pointer Back Pointer Position Data

5
4
3
→ → 2 Hartlepool
→ → 1 Moulton
→ → 0 Bolton
→ → -1 Empty
1. That linked vertex is then added to the visited list. Finally, it is removed from the queue
as this process repeats. This means that all nodes, from left to right are enqueued to the
queue in turn, before being added to the visited list, and then dequeued from the queue
2. Output all of the visited vertices

Our final visited list would appear as

Dunkirk, Bolton, Moulton, Hartlepool, Frogmore, Teesside, Cardiff

The final version of the queue would have appeared as

Front Pointer Back Pointer Position Data

→ → 5 Cardiff
→ → 4 Teesside
→ → 3 Frogmore
→ → 2 Hartlepool
→ → 1 Moulton
→ → 0 Bolton
→ → -1 Empty
Depth-first search
 In A Level Computer Science, a depth-first search is a graph traversal algorithm which
uses an edge-based system
 This method makes use of a stack data structure to push each visited node onto the
stack and then pop them from the stack when there are no nodes left to visit

Examiner Tips and Tricks

There is no right method to use when performing a depth-first search, it simply depends on how
the algorithm is implemented. Most mark schemes commonly traverse the left-most path first,
therefore that will be used in this example.
Using the example from above, Dunkirk, would be set as the current node and then added to
the visited list

Dunkirk
1. Then check if the connected node isn't already in the visited list, if it is not, it pushed to
the stack.

The first version of the stack would appear as

Pointer Position Data

5
4
3
→ 2 Bolton
→ 1 Moulton
→ 0 Hartlepool
→ -1 Empty
1. Next, any connected node that is not on the visited list is then pushed to the stack.
2. Then pop the stack to remove the item and set it as the current node.
3. Output all of the visited nodes

Our final visited list would appear as

Dunkirk, Bolton, Frogmore, Moulton, Hartlepool, Teesside, Cardiff

You could visualise how the graph has been traversed below, with the left-most column first,
then the middle, then the right-most column.
Adding & removing data in graphs
 There is no single algorithm for adding or deleting a node in a graph. This is because a
graph can have a number of nodes connected to any number of other nodes.
 As a result, it is more important that there are a clear set of instructions to easily traverse
the graph to find the specific node.

 A Binary Tree is a special type of graph and it does have an algorithm for adding and
deleting items. This is covered in the content titles‟ Binary Search Trees‟.

Examiner Tips and Tricks

It is important to note that it is not important what the graph looks like, but which vertices are
connected.
Worked Example
A puzzle has multiple ways of reaching the end solution. The graph below shows a graph
that represents all possible routes to the solution. The starting point of the game is
represented by A, the solution is represented by J. The other points in the graph are
possible intermediary stages.

The graph is a visualisation of the problem.

i. Identify one difference between a graph and a tree [1]

 A graph has cycles [1]

 A graph can be directed/undirected [1]
 A tree has a hierarchy (e.g. Parent/Child) [1]

ii. Explain how the graph is an abstraction of the problem [2]

 The puzzle is not shown in the diagram [1]

 The graph shows different sequences of sub-problems in the puzzle that can be solved
to get the final solution [1]
 The puzzle does not have all states visible at once [1]

iii. Identify two advantages of using a visualisation such as the one shown above [2]

 Visualisation benefits humans rather than computers [1]

 Visualisations present the information in a simpler form to understand [1]
 Visualisation can best explain complex situations [1]
Trees Data Structures
What is a tree?
 A tree is a connected, undirected form of a graph with nodes and pointers
 Trees have a root node which is the top node; we visualise a tree with the roots at the
top and the leaves at the bottom
 Nodes are connected to other nodes using pointers/edges/branches, with the lower-level
nodes being the children of the higher-level nodes
 The endpoint of a tree is called a leaf
 The height of a tree is equal to the number of edges that connect the root node to the
leaf node that is furthest away from it

 Nodes are connected by parent-child relationships

 If a path is marked from the root towards a node, a parent node is the first one and the
child node is the next
 A node can have multiple children
 A leaf node is a node with no children

What are trees used for?

 Trees can be used for a range of applications:
o Managing folder structures
o Binary Trees are used in routes to store routing tables
o Binary Search Trees can be built to speed up searching
o Expression trees can be used to represent algebraic and Boolean
expressions that simplify the processing of the expression
Traversing Tree Data Structures
What is a binary tree?
 A binary tree is a rooted tree where every node has a maximum of 2 nodes
 A binary tree is essentially a graph and therefore can be implemented in the same way
 For your A Level Computer Science exam, you must understand:
o tree traversal of a tree data structure
o add new data to a tree
o remove data from a tree

 The most common way to represent a binary tree is by storing each node with a left and
right pointer. This information is usually implemented using 2D arrays
Tree traversal
 There are 2 methods of traversing a binary tree; depth-first and breadth-first
 Both are important to understand and you should be able to output the order of the
nodes using both methods

Depth-first traversal of a binary tree

 There are 3 methods to traverse a binary tree using a depth-first traversal: Pre-Order, In-
Order and Post-Order. For the OCR specification, you are only required to understand
post-order traversal
 Post-order traversal
o Left Subtree
o Right Subtree
o Root Node
 Using the outline method, imagine there is a dot on the right-hand side of each node
 Nodes are traversed in the order in which you pass them on the right
o Start at the bottom left of the binary tree
o Work your way up the left half of the tree
o Visit the bottom of the right half of the tree
o Making your way back up toward the root node at the top
  The order of traversal is: 4, 2, 14, 6, 7, 1, 8, 9, 10

Breadth first traversal of a binary tree

 The breadth-first traversal of a tree simply means to:
o Begin with the root node
o Move to the left-most node under the root
o Output each node, moving from left to right, just as though you were reading a
book
o Continue through each level of the tree

 Using the image above, a breadth-first traversal would output:

o 10, 6, 15, 2, 8, 19, 4, 17, 21
Adding Data to a Tree
How do you add data to a binary tree?
 As mentioned above, a tree is a fundamental data structure in Computer Science and
students must be able to understand how data can be added and removed in trees
 To add a value to a binary tree you need to complete the following:

1. Start with an empty tree or existing tree

2. Identify the position where the new value should be inserted according to the rules of a
binary tree
 If the tree is empty, the new value will become the root node
 If the value is less than the current node‟s value, move to the left child
 If the value is greater than the current node‟s value, move to the right child
 Repeat this process until you reach a vacant spot where the new value can be
inserted
 3. Insert the new value into the identified vacant spot, creating a new node at that position

4. After insertion, verify that the binary tree maintains its structure and properties

Removing Data From a Tree

How do you remove data from a binary tree?
 To remove a value from a binary tree you need to complete the following:

1. Start with an existing tree

2. Search for the node containing the value you want to remove

3. If the node is found:

a. If the node has no children (leaf node), simply remove it from the tree
b. If the node has one child, replace the node with its child
c. If the node has two children, find the replacement node by:
 Option 1: Find the minimum value in its right subtree (or the maximum value in its
left subtree)
 Option 2: Choose either the leftmost node in the right subtree or the rightmost
node in the left subtree. Remove the replacement node from its original location
and place it in the position of the node to be deleted.

4. After removal, adjust the binary tree structure if necessary to maintain its properties and
integrity
Tree keywords
Keyword Definition
Node An item in a tree
Edge Connects two nodes together and is also known as a branch or pointer
Root A single node which does not have any incoming nodes
Child A node with incoming edges
Parent A node with outgoing edges
Subtree A subsection of a tree consisting of a parent and all the children of a parent
Leaf A node with no children
Traversing The process of visiting each node in a tree data structure, exactly once