2.3.2 Data Structures

• Stacks

  • Implemented as an array
  • single pointer keeps track of the top of the stack (top pointer)
  • top pointer is initialised at -1
  • Operations shown below:

  
• Queues

  • FIFO structure
  • represented as arrays
  • two pointers: front and back
  • front holds the position of the first element
  • back stores the next available space

  
• Linked List

  • composed of nodes, each has a pointer to the next item in the list
  • first item in a list is referred to as the head
  • last item as the tail
  • Searching a list is performed using a linear search
• Trees

  • formed from nodes and edges
  • depth first (post-order) and breadth first traversal
• Depth-first traversal

  • goes as far down into the tree as possible before backtracking
  • think of lines around tree
  • below example gives 2, 4, 3, 4, 5
  • number put to right
  • uses a stack

  
• Breadth-first traversal

  • visits all children of the start node
  • visits all nodes directly connected to each of those nodes in turn
  • uses a queue
  • example below gives 5, 3, 8, 2, 4