DS The Queue Abstract Data Type

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.

🔗

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 boolean true if the queue is empty, false otherwise.
🔗

🔗
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.

🔗

Table 3.11.1. Example Queue Operations

🔗

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`

As we did with the stack, here is the specification of the queue ADT as an interface. By specifying it as an interface, it will help us later on in making sure that we remember to implement all of the appropriate functions, and we can switch more easily between implementations.

🔗

Listing 3.11.2. Interface representing Queue ADT

🔗

interface QueueADT<T> {
    // Returns true if there are no items in the queue;
    // false otherwise.
    fun isEmpty(): Boolean

    // Add an item to the tail of the queue
    fun enqueue(item: T)

    // Remove the item at the head of the queue and return it.
    fun dequeue(): T

    // Return the item at the head of the queue, but do not remove it.
    // If the queue is empty, throws an exception.
    fun peek(): T

    // Returns the number of items in the queue.
    fun size(): Int
}

You have attempted of activities on this page.

🔗

Prev Top Next