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 front or rear. The deque operations are given below.

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

Table 1: Examples of Deque Operations

Deque Operation

Deque Contents

Return Value

d.empty()

[]

True

d.push_back(4)

[4]

d.push_back(17)

[17,4]

d.push_front(93)

[17,4,93]

d.push_front(65)

[17,4,93,65]

d.size()

[17,4,93,65]

4

d.empty()

[17,4,93,65]

False

d.push_back(25)

[25,17,4,93,65]

d.pop_back()

[17,4,93,65]

d.pop_front()

[17,4,93]

You have attempted of activities on this page