Advanced C++ - Class 3

• Review of C++ Chapter 15
  
  
• Describe the self referential class
  
  Classes that contain pointers to objects of this same type
  
  
• Review purpose and architecture of the array, list, stack, queue and binary tree data structures
  
  Array:  Linear arrangement, accessible via  index, typically static in size.  Dynamic arrays in the STL are called vectors and act as singly linked list.
  
  List:  Single and double linked list.  SLL and DLL insertion at the head and tail.  DLL enable list maintenance for fast removals and insertion in the middle of the list.  Lists can typically be sorted.
  
  Stack:  Object are pushed onto the stack and popped of the stack.  Data behaviors if FILO or first in last out.  In compilers, stack represent the scope of objects.  We push objects on to the stack as the are instantiated.
  
  Queue:  A queue represents a waiting line with data behavior of FIFO.  Queue insert at the tail and remove from the head.  Queue can be sorted as lists where is sort is based on the queue priority.  Queue play an important role in operating systems for process management and communication systems for transaction management.  It is common to memory map the queue to a file for persistent and recoverable storage.
  
  Binary Tree:  These data structures are sorted and allow only unique nodes as represented by the leaf nodes of the tree.  Searching the tree is extremely fast, Log₂n, however tree inserting can be expensive, so that BSTs are great for lookup tables.
  
  
• Example of a Queue Template
  
  Main Index