***********
Linear ADTs
***********
Linear ADTs model an ordered (not sorted) homogenous list of data. There are
several common types of linear ADTs that differ in Behaviors.

Common Linear ADTs
==================

List
----
+ Characteristics

  * Sequential - the elements are ordered in a sequence
  * Finite - known number of elements
  * Indexable - each element has a unique positional index to allow random
    access
  * Dynamic - the size of the list can change

+ Behaviors

  * add/remove/access by index
  * search (find index or pointer by value)
  * find size
  * check empty

+ Implementation

  * C array (fast access/read by index)
  * linked-list (fast add/remove in the middle)

Stack
-----
+ Characteristics

  * Finite
  * Last-in-first-out (LIFO)
  * Dynamic

+ Behaviors

  * push
  * pop
  * peek/top
  * check empty

+ Implementation

  * C array (add/remove at the tail, limited max length)
  * linked-list (add/remove at either end, unlimited max length)

+ Application

  * Backtracking algorithm
  * Depth-first traversal

Queue
-----
+ Characteristics

  * Finite
  * First-in-first-out (FIFO)
  * Dynamic

+ Behaviors

  * enqueue
  * dequeue
  * check empty

+ Implementation

  * circular C array (limited max length)
  * linked-list (unlimited max length)

+ Application

  * Breadth-first traversal

Deque
-----
+ Characteristics

  * Finite
  * First-in-first-out (FIFO) and Last-in-first-out (LIFO)
  * Dynamic

+ Behaviors

  * enqueue_front, enqueue_back
  * dequeue_front, dequeue_back
  * check empty

+ Implementation

  * circular C array (limited max length)
  * linked-list (unlimited max length)
  * vector of vectors (std::deque in C++ STL)

Data Structures to Implement Linear ADTs
========================================
There are many data structures suitable in the implementation of the above
ADTs. They should be selected according to the requirements.

+ C style Array

  * Fast indexing
  * Slow insertion, or pre-pending
  * Fast appending
  * Slow to change capacity (with re-allocation and data movement)
  * Circular variation (suitable for queue and deque)

+ Linked-list

  * Fast insertion, appending, pre-pending
  * Slow indexing
  * Complex logics
  * More space overhead

+ Related STL containers and their implementations

  * std::array

    - fixed size
    - static C array

  * std::vector

    - resizable (slow)
    - dynamic C array

  * std::list

    - doubly-linked-list

  * std::forward_list

    - singly-linked-list

  * std::deque

    - vector of vectors

  * std::stack

    - wrapper of other STL containers

  * std::queue

    - wrapper of other STL containers