Algorithms For Main Data Structures

Question 1

Stacks

Answer 1

Stacks: First in, last out (FILO) data structure
- Often implemented as array
- Uses single pointer which keeps track of the top of stack (top pointer)
- Top Pointer initialised at -1; 1st element in stack is in position 0, having top initialised at 0 suggests there is an element in stack, when stack is empty

Question 2

Stack Operations

Answer 2

Check size = size()
Check if empty= isEmpty()
Return top element (but don’t remove) = peek()
Add to the stack = push(element)
Remove top element from stack & return element = pop()

Question 3

Queues

Answer 3

Queues: First in, first out (FIFO) data structure
- Often represented as arrays
- Uses of 2 pointers: front & back
- Front: Holds position of 1st element
- Back: Stores next available space

Question 4

Queue Operations

Answer 4

Check size = size()
Check if empty = isEmpty()
Return front element (but don’t remove) = peek()
Add to the queue = enqueue(element)
Remove front element from queue & return removed element = dequeue()

Question 5

Linked Lists

Answer 5

Linked Lists: Composed of nodes, each of which has a pointer to the next item in the list
- 1st item in a list is referred to as head & the last as the tail
- Searching list performed using linear search, carried out by until desired element is found

Question 6

Trees

Answer 6

Trees: Formed from nodes & edges, which cannot contain cycles & aren’t directed
- Useful because they can be traversed

Question 7

Depth First (Post-Order) Traversal

Answer 7

Depth First Search: Goes as far down into the tree as possible before backtracking
- Uses a stack & goes to the left child node of the current node when it can
- If there is no left child then the algorithm goes to the right child
- If no child nodes, algorithm visits current node, outputting the value of the node before backtracking to the next node on the stack & moving right

Question 8

Breadth First Traversal

Answer 8

Breadth First: Visits all children of the start node
- Algorithm then visits all nodes directly connected to each of those nodes in turn, continuing until every node has been visited
- Breadth first uses a queue