2. 3. 2 Main Data Structures Algorithms

Question 1

Stacks

Answer 1

• First In Last Out (FILO) data structure, implemented as an array using single pointer (top pointer)
• The top pointer points to the element currently at the top of the stack, initialised at -1 because first position in stack is position 0

Question 2

Pseudocode for size()

Answer 2

Returns number of elements in stack, does this by increasing top pointer by 1 (First element in position 0)

Question 3

Pseudocode for isEmpty()

Answer 3

Checks if the stack is empty, does this by checking if the pointer is less than 0 (If its 0 there is one item in the stack)

Question 4

Pseudocode for peek()

Answer 4

• Checks what the top pointer value is without removing the value
• First check if the stack is empty to avoid an error
• A is our array representing a stack

Question 5

Pseudocode for push()

Answer 5

• New item to be added to stack passed as a parameter
• Top pointer is updated prior to addition so that no data is overwritten
• The new element is then inserted at the position of the top pointer

Question 6

Pseudocode for pop()

Answer 6

• Before removing an item, a check is done to make sure the stack is not empty
• The element at the top of the pointer is recorded before being removed
• The top pointer is decremented by one before the removed item is returned

Question 7

Example of a Stack

Answer 7

• What would the result be of the following 3-element stack?
• Keep in mind that 3 is not added to the stack because it is only a 3-element array, therefore attempting to add another item when the stack was full lead to an error

Question 8

Queues

Answer 8

• First In First Out (FIFO) data structure, implemented as an array, make use of two pointers (front and back)
• Front points to (stores) position of first element
• Back points to (stores) position of the next available space

Question 9

Pseudocode for size()

Answer 9

• Work out size of queue by subtracting the back pointer from the top pointer
• For example, if front is 0 and back is 5, there are 5 elements in the queue

Question 10

Pseudocode for isEmpty()

Answer 10

When queue is empty, front and back should be the same value, check if this is the case to determine if the queue is empty

Question 11

Pseudocode for peek()

Answer 11

Peek returns element at the front of the queue without removing it

Question 12

Pseudocode for enqueue(element)

Answer 12

To add an element, element placed in position of back pointer, back pointer is then incremented by 1

Question 13

Pseudocode for dequeue()

Answer 13

Items removed from queue from position of front pointer, important to check if queue is empty before doing so to avoid an error

Question 14

Example of a Queue

Answer 14

What happens if the following operations are ran on the queue above?

Question 15

Linked Lists

Answer 15

• Composed of nodes, each node has a pointer to the next item in the list
• Lets say a node is N, the node after than would be N.next
• The first item/element is the head, the last item/element is the tail
• Lists are searched using a linear search, sequential “next” operation till desired element found

Question 16

Trees

Answer 16

• Formed from nodes and edges, cannot contain cycles and are not directed
• Trees are useful because they can be traversed
• The two types of traversals to cover are depth first (post-order) and breadth first
• Both can be implemented recursively, differ in order nodes are visited
• Pre-order and in-order traversal are not required in the exam