DS The Deque Abstract Data Type

Section 3.16 The Deque Abstract Data Type

The deque abstract data type is defined by the following structure and operations. A deque is structured, as described above, as an ordered collection of items where items are added and removed from either end, either head or tail. The deque operations are given below.

🔗

addHead(item) adds a new item to the head of the deque. It needs the item and returns nothing.
🔗

🔗
addTail(item) adds a new item to the tail of the deque. It needs the item and returns nothing.
🔗

🔗
removeHead() removes the head item from the deque. It needs no parameters and returns the item. The deque is modified.
🔗

🔗
removeTail() removes the tail item from the deque. It needs no parameters and returns the item. The deque is modified.
🔗

🔗
peekHead() returns, but does not remove, the head item from the deque. It needs no parameters and does not modify the deque.
🔗

🔗
peekTail() returns, but does not remove, the tail item from the deque. It needs no parameters and does not modify the deque.
🔗

🔗
isEmpty() tests to see whether the deque is empty. It needs no parameters and returns a boolean value.
🔗

🔗
size() returns the number of items in the deque. It needs no parameters and returns an integer.
🔗

🔗

🔗

As an example, if we assume that d is a deque that has been created and is currently empty, then Table 3.16.1 shows the results of a sequence of deque operations. Note that the contents at the head are listed on the right. It is very important to keep track of the head and the tail as you move items in and out of the collection, as things can get a bit confusing.

🔗

Table 3.16.1. Examples of Deque Operations

🔗

Deque Operation	Deque Contents	Return Value
`d.isEmpty()`	`[]`	`True`
`d.addTail(4)`	`[4]`
`d.addTail(505)`	`[505, 4]`
`d.addHead(1066)`	`[505, 4, 1066]`
`d.addHead(4711)`	`[505, 4, 1066, 4711]`
`d.size()`	`[505, 4, 1066, 4711]`	`4`
`d.is_empty()`	`[505, 4, 1066, 4711]`	`False`
`d.addTail(217)`	`[217, 505, 4, 1066, 4711]`
`d.removeTail()`	`[505, 4, 1066, 4711]`	`217`
`d.removeHead()`	`[505, 4, 1066]`	`4711`

Here is a definition of a deque, expressed as a Kotlin interface.

🔗

Listing 3.16.2. Interface representing Queue ADT

🔗

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

    // Add an item to the head of the deque
    fun addHead(item: T)

    // Add an item to the tail of the deque
    fun addTail(item: T)

    // Remove the item at the head of the deque and return it.
    // If the deque is empty, throws an exception.
    fun removeHead(): T

    // Remove the item at the tail of the deque and return it.
    // If the deque is empty, throws an exception.
    fun removeTail(): T

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

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

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

You have attempted of activities on this page.

🔗

Prev Top Next