Relation: explicitly defined linear ordering

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

Critical Operations for Queue ADTs

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

The functions are also referred to as void enqueue( Type ), Type head() const, and void dequeue(), respectively.

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

Example Data Structures

The most common data structure for implementing queues 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 queue in the STL is implemented using the deque data structure.

Figure 1. Hybrid implementation of the Queue ADT.