Containers

Containers are abstract data types that hold stuff. They don't do much more than hold it so that it can be retrieved later. Still, they are critical to the functioning of society. We will use the term container to denote a data structure that permits storage and retrieval of data items independently of content. The two fundamental operations of any container are:  

• Put(C,x): Insert a new data item x into the container C.
• Get(C): Retrieve the next item from the container C. Different types of containers support different retrieval orders, based on insertion order or position.

Containers are typically most useful when they will contain only a limited number of items and when the retrieval order is predefined or irrelevant. The most popular type of containers are:

• Stacks: Supports retrieval in last in, first out order (LIFO). Stacks are simple to implement, and very efficient. Indeed, stacks are probably the right container to use when the retrieval order doesn't matter at all, as when processing batch jobs. The put and get operations for stacks are usually called push and pop.    
• Queues: Supports retrieval in first in, first out order (FIFO). FIFO may seem the fairest way to control waiting times. However, for many applications, data items have infinite patience. Queues are trickier to implement than stacks and are appropriate only for applications (like certain simulations) where the order is important. The put and get operations for queues are usually called enqueue and dequeue.    
• Tables: Supports retrieval by position, so that put and get each accept an index as an argument. Tables are naturally implemented using arrays.  

Each of these containers can be implemented using either arrays or linked lists. With the exception of tables, the choice of lists versus tables probably doesn't matter very much. The key issue is whether an upper bound on the size of the container is known in advance, thus permitting a statically allocated array. Using arrays, put and get can be implemented in constant time per operation for each of the containers.