2.3.2 Algorithms for the main data structures

Question 1

Stacks

Answer 1

. LIFO Data structure

. Often implemented as an array

. Use a single pointer which keeps track of the top of the stack (called the top pointer)

. points to the element which is currently at the top of the stack

. is initialised at -1, as the first element in the stack is in poisiton

Question 2

Stack algorithms

Answer 2

Algorithms for stacks include adding to stack, removing from the and checking if the stack is empty or full

Question 3

Queues

Answer 3

FIFO data structure

. Just like stacks, queues are often represented in arrays

. Unlike stacks, queues make use of two pointers

. Front holds the position of the first element

. Back stores the next available space

. Operations which can be carried out on queues are similar to those of stacks

Question 4

Linked lists

Answer 4

. Comprised of nodes, each of which has a pointer to the next item in the list

. If a node is referred to as N, the next node can be accessed using N.next

. The first item in a list is referred to the head and the last as a tail

. Searching a list is used using a linear search

. Carried out by sequential next operations until the desired element is found

Question 5

Trees

Answer 5

. Formed from nodes and edges

. Cannot contain cycles

. Edges are not directed

. Useful as a data structure because trees can be traversed

. There are two types of traversal to cover, depth in (post order) and breadth first

. Both can be implemented recursively

Question 6

Depth first traversal

Answer 6

Depth first traversal

. Goes as far into the tree before backtracking

. Uses a stack and goes to the left child node of the current node when it can

. If there is no left child then it goes to the right

. If there are no child nodes, the algorithm visits the current node, outputting the value of this node

. It then backtracks to the next node on the stack and moves right

Question 7

Breadth first traversal

Answer 7

Starting from the left, breadth-first visits all of the children of the start node

. The algorithm then visits all nodes directly connected to each of those nodes in turn, continuing until every node has been visited

. Unlike depth first traversal (which uses a stack) breadth first uses a queue