Section 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 tail, and removed from the other end, called the head. Queues maintain a FIFO (First In, First Out) ordering property. The queue operations are given below.
Queue()creates a new queue that is empty. It needs no parameters and returns an empty queue.enqueue(item)adds a new item to the tail of the queue. It needs the item and returns nothing.dequeue()removes the head item from the queue. It needs no parameters and returns the item. The queue is modified.peek()returns the head item from the queue. It needs no parameters. The queue is not modified.isEmpty()tests to see whether the queue is empty. It needs no parameters and returns booleantrueif the queue is empty,falseotherwise.size()returns the number of items in the queue. It needs no parameters and returns an integer.
As an example, if we assume that
q is a queue that has been created and is currently empty, then Table 3.11.1 shows the results of a sequence of queue operations. The queue contents are shown such that the head is on the right. The first item enqueued was 4 so it is the first item returned by dequeue.| Queue Operation | Queue Contents | Return Value |
|---|---|---|
q.is_empty() |
[] |
true |
q.enqueue(4) |
[4] |
|
q.enqueue(27) |
[27,4] |
|
q.enqueue(1066) |
[1066, 27, 4] |
|
q.size() |
[1066, 27, 4] |
3 |
q.is_empty() |
[1066, 27, 4] |
False |
q.enqueue(4711) |
[4711, 1066, 27, 4] |
|
q.dequeue() |
[4711, 1066, 27] |
4 |
q.dequeue() |
[4711, 1066] |
27 |
q.size() |
[4711, 1066] |
2 |
You have attempted of activities on this page.
