2.3.2 Algorithms for the Main Data Structures

• Stacks are examples of (FILO) first in, last out data structures. They are often structured as an array and have a single pointer that keeps track of the stack.
• Key terms

  1.  Size () = checks size
  2. isEmpty () = checks if empty.
  3. push(element) = adds to the stack
  4. pop() = remove the top element off the stack and returns the removed element.
• Size() returns the number of elements from the stack. The +1 is pointing to the 1st position at 0.

  
• isEmpty() checks if the stack is empty. We need to check whether the pointer is less than 0 and if it is the stack is empty.

  
• push(element) adds an item to the stack, the new item must be passed through a parameter. The top+=1 is updated accordingly, so that the new element can be tracked by the pointer.

  
• pop() removes an item from the stack and returns the item that was at the top of the stack before the pop(). It is important to check that there are actually items to pop before calling pop()

  
• Queues are first in, first out (FIFO) data structures. Queues are represented by arrays. However queues use two pointers: front and back. While front is the head of the queue, back stores the next available space.
• Trees are formed in nodes and edges and they can be traversed
• Depth first search goes as far down into the tree as possible before backtracking. The algorithm uses a stack and 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.
• First you visit 3, then its checks nodes 2 and 4 but then goes to 2. It then backtracks to node 3 as there are no more nodes to visit so it then goes to 4. It back tracks back to 5 and then goes to 8.

  
• Breadth first starts on the left and visits all children nodes that are directly connected to each of those nodes, continuing until all of the nodes have been directly connected. Breadth first uses a queue.
• It starts at 5 and visits child node 3 and then backtracks to visit the other connected node which is 8. It then backtracks to 5 and then goes to 3 and connects to both 2 and 4. It first goes to 2 and then backtracks to 3 and then goes to 4.