Relation: explicitly defined linear ordering

An Abstract Stack defined on objects which are linearly ordered by the programmer. A new object placed into the stack is explicitly placed at the front of the stack while the only defined removal is from the front of the stack. This ensures the behaviour that the of any collection of objects inserted into the stack, the first that was inserted will also be the first removed. This behaviour is sometimes called a last-in—first-out.

Critical Operations for Abstract Stacks

• Insert a new object
  void push( Type ) const;
• Examine the head of the stack
  Type top() const
• Remove the object at the front of the stack
  void pop()

By restricting the relevant operations as compared to a general Abstract List, it is possible to make significant improvements in the run times.

Example Data Structures

The most common data structure for implementing stack are cyclic dynamic arrays and singly linked lists. All operations are O(1); however, some operations on for dynamic arrays are amortized O(1).

The requirements of the STL, however, requires a hybrid structure as is shown in Figure 1: A singly linked list requires too many allocations and deallocations of memory and accessing an object in the middle of a deque requires O(n) time; a dynamic array has the occasional operations which run in O(n) time. The stack in the STL is implemented using the deque data structure.

Figure 1. Hybrid implementation of the Abstract Stack.