224 5. Engine Support Systems
- Linked list. An ordered collection of elements not stored contiguously
in memory but rather linked to one another via pointers (e.g., STL’s
std::list). - Stack. A container that supports the last-in-fi rst-out (LIFO) model
for adding and removing elements, also known as push/pop (e.g.,
std::stack). - Queue. A container that supports the fi rst-in-fi rst-out (FIFO) model for
adding and removing elements (e.g., std::queue). - Deque. A double-ended queue—supports effi cient insertion and removal
at both ends of the array (e.g., std::deque). - Priority queue. A container that permits elements to be added in any or-
der and then removed in an order defi ned by some property of the ele-
ments themselves (i.e., their priority). It can be thought of as a list that
stays sorted at all times. A priority queue is typically implemented as a
binary search tree (e.g., std::priority_queue). - Tr e e. A container in which elements are grouped hierarchically. Each ele-
ment (node) has zero or one parent and zero or more children. A tree is
a special case of a DAG (see below). - Binary search tree (BST). A tree in which each node has at most two chil-
dren, with an order property to keep the nodes sorted by some well-de-
fi ned criteria. There are various kinds of binary search trees, including
red-black trees, splay trees, SVL trees, etc. - Binary heap. A binary tree that maintains itself in sorted order, much like
a binary search tree, via two rules: the shape property, which specifi es that
the tree must be fully fi lled and that the last row of the tree is fi lled from
left to right; and the heap property, which states that every node is, by some
user-defi ned criterion, “greater than” or “equal to” all of its children. - Dictionary. A table of key-value pairs. A value can be “looked up” ef-
fi ciently given the corresponding key. A dictionary is also known as a
map or hash table, although technically a hash table is just one possible
implementation of a dictionary (e.g., std::map, std::hash_map). - Set. A container that guarantees that all elements are unique according to
some criteria. A set acts like a dictionary with only keys, but no values. - Graph. A collection of nodes connected to one another by unidirectional
or bidirectional pathways in an arbitrary patt ern. - Directed acyclic graph (DAG). A collection of nodes with unidirectional
(i.e., directed) interconnections, with no cycles (i.e., there is no non-empty
path that starts and ends on the same node).