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, Log2n, however tree inserting can be
expensive, so that BSTs are great for lookup tables.
- Example of a Queue Template
Main Index