3.11. The Queue Abstract Data Type

The queue abstract data type is defined by the following structure and operations. A queue is structured, as described above, as an ordered collection of items which are added at one end, called the “rear,” and removed from the other end, called the “front.” Queues maintain a FIFO ordering property. The queue operations are given below.

As an example, if we assume that q is a queue that has been created and is currently empty, then Table 1 shows the results of a sequence of queue operations. The queue contents are shown such that the front is on the right. 4 was the first item enqueued so it is the first item returned by dequeue.

Table 1: Example Queue Operations
Queue Operation Queue Contents Return Value
q.isEmpty() [] True
q.enqueue(4) [4]  
q.enqueue('dog') ['dog',4]  
q.enqueue(True) [True,'dog',4]  
q.size() [True,'dog',4] 3
q.isEmpty() [True,'dog',4] False
q.enqueue(8.4) [8.4,True,'dog',4]  
q.dequeue() [8.4,True,'dog'] 4
q.dequeue() [8.4,True] 'dog'
q.size() [8.4,True] 2
Next Section - 3.12. Implementing a Queue in Python