Ctrl+K

Deque

Deque#

A deque, also known as a double-ended queue, is an ordered collection of items similar to the queue. It has two ends, a front and a rear, and the items remain positioned in the collection. What makes a deque different is the unrestrictive nature of adding and removing items. New items can be added at either the front or the rear. Likewise, existing items can be removed from either end. In a sense, this hybrid linear structure provides all the capabilities of stacks and queues in a single data structure.

It is important to note that even though the deque can assume many of the characteristics of stacks and queues, it does not require the LIFO and FIFO orderings that are enforced by those data structures.

flowchart TB; subgraph id3 [ ] direction TB c1(Add to front) c2(Remove from front) end subgraph id2 [Deque] direction TB b1(3.14) b2(True) b3(dog) b4(20) end subgraph id1 [ ] direction TB a1(Add to rear) a2(Remove from rear) end a1-->b1 b1-->a2 c1-->b4 b4-->c2 style id1 fill:#FFFFFF, stroke-width:0px style id3 fill:#FFFFFF, stroke-width:0px

Examples

  • Cine for getting a movie ticket.

  • Check-out line at a grocery store, and we wait in the cafeteria line (so that we can pop the tray stack).

  • Operating systems use a number of different queues to control processes within a computer. The scheduling of what gets done next is typically based on a queuing algorithm that tries to execute programs as quickly as possible and serve as many users as it can.

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.

Deque Operations#

  • Deque() creates a new deque that is empty. It needs no parameters and returns an empty deque.

  • add_front(item) adds a new item to the front of the deque. It needs the item and returns nothing.

  • add_rear(item) adds a new item to the rear of the deque. It needs the item and returns nothing.

  • remove_front() removes the front item from the deque. It needs no parameters and returns the item. The deque is modified.

  • remove_rear() removes the rear item from the deque. It needs no parameters and returns the item. The deque is modified.

  • is_empty() 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.

d = Deque() creates a deque that starts out empty, table below shows the results of a sequence of deque operations.

Deque Operation

Deque Contents

Return Value

d.is_empty()

[]

True

d.add_rear(4)

[4]

d.add_rear('dog')

['dog',4,]

d.add_front('cat')

['dog',4,'cat']

d.add_front(True)

['dog',4,'cat',True]

d.size()

['dog',4,'cat',True]

4

d.is_empty()

['dog',4,'cat',True]

False

d.add_rear(8.4)

[8.4,'dog',4,'cat',True]

d.remove_rear()

['dog',4,'cat',True]

8.4

d.remove_front()

['dog',4,'cat']

True

Implementing a Deque in Python#

An abstract data type (ADT) when given a physical implementation then we refer to the implementation as a data structure.

In any object-oriented programming language, the implementation of choice for an abstract data type such as a Deque is the creation of a new class. The deque operations are implemented as methods. Further, to implement a queue, which is a collection of elements, it makes sense to utilize the primitive collections provided.

class Deque:
    
    def __init__(self):
        self.items = []

    def is_empty(self):
        return self.items == []

    def add_front(self, item):
        self.items.append(item)
    
    def add_rear(self, item):
        self.items.insert(0, item)

    def remove_front(self):
        return self.items.pop()

    def remove_rear(self):
        return self.items.pop(0)

    def size(self):
        return len(self.items)

# Create a new deque
d = Deque()

# Check if the deque is empty
print(d.is_empty())

# Add 4 at rear
d.add_rear(4)

# Add "dog" at rear
d.add_rear('dog')

# Add "cat" at front
d.add_front('cat')

# Add True at front
d.add_front(True)

# Give the size of the deque
print(d.size())

# Check if the deque is empty
print(d.is_empty())

# Add 8.4 at rear
d.add_rear(8.4)

# Remove item from rear
print(d.remove_rear())

# Remove item from front
print(d.remove_front())

True
4
False
8.4
True

Practical usage in python#

collections.deque module provides an implementation of the dequeue data structure, also known as the double ended queue.

And you can find more information about the interface and api from docs.

Practice Problem#

Write a function check_pallindrome(string) that return true if the input string is palindrome otherwise return false.#

A palindrome is a string that reads the same forward and backward.

Example: radar, toot, madam etc.

def check_pallindrome(string):
    characters = Deque()

    for char in string:
        characters.add_rear(char)

    while characters.size() > 1:
        rear = characters.remove_rear()
        front = characters.remove_front()

        if rear != front:
            return False
    
    return True

print(check_pallindrome("radar"))
print(check_pallindrome("toot"))
print(check_pallindrome("lsdkjfskf"))
print(check_pallindrome("abb"))
print(check_pallindrome("abba"))

True
True
False
False
True
Contents