Dremendo Tag Line

Double Ended Queue in Python Programming

User-Defined Data Structures in Python

In this lesson, we will understand what is Double Ended Queue in Python Programming and how to create them along with some examples.

What is Double Ended Queue in Python

A Double Ended Queue in Python, also known as Deque, is a user-defined queue data structure in which insertion and deletion can be done from both left and right ends.

python double ended queue example

From the above image of the deque, we can see that when we add an element from the rear end, the R moves towards the right, and when we delete an element from the rear end, the R moves towards the left.

Similarly, when we delete an element from the front end, the F moves towards the right, and when we add an element from the front end, the F moves towards the left.

video-poster

Operation on Circular Queue

There are four operations possible on the double ended queue.

  • Add Rear When we add an element from the rear end.
  • Delete Rear When we delete an element from the rear end.
  • Add Front When we add an element from the front end.
  • Delete Front When we delete an element from the front end.

Note: We will use the circular array to implement the Double Ended Queue.

Add Rear Operation in Deque

For adding an element from the rear end, first, we check if the value of te is equal to the size of the array. Then, we will display a message Queue is full. Else we will increase the value of R by R=(R+1)%Size and add the element in the array at the new location of R, and then increase the value of te by 1.

Here, te is a variable that keeps the total number of elements present in the array. When an element is added, the value of te increases by 1. When an element has been deleted, the value of te is decreased by 1.

Example

size = 5
arr = array('i',[])
R = -1
F = 0
te = 0

if te==size:
    print('Queue is full')
else:
    R=(R+1)%size
    arr[R]=new_item
    te=te+1

Delete Rear Operation in Deque

For deleting an element from the rear end first, we check if the value of te is equal to 0 then, we will display a message Queue is empty, else we will check if the value of R is -1, then we will initialize the value of R=size-1. After that, we will display the deleted element on the screen and decrease the value of R and te by 1.

Example

if te==0:
    print('Queue is empty')
else:
    if R==-1:
        R=size-1
    print('Number Deleted From Rear End = %d' %(arr[R]))
    R=R-1
    te=te-1

Add Front Operation in Deque

For adding an element from the front end, first, we check if the value of te is equal to the size of the array. Then, we will display a message Queue is full. Otherwise, we will check if the value of F is 0, and then we will initialize the value of F=size-1 or decrease the value of F by 1. At last, add the element in the array at the new location of F and then increase the value of te by 1.

Example

if te==size:
    print('Queue is full')
else:
    if F==0:
        F=size-1
    else:
        F=F-1
    arr[F]=new_item
    te=te+1

Delete Front Operation in Deque

For deleting an element from the front end, first, we check if the value of te is equal to 0. Then, we will display a message Queue is empty. Else we will display the deleted element on the screen, then we will increase the value of F by F=(F+1)%Size and then decrease the value of te by 1.

Example

if te==0:
    print('Queue is empty')
else:
    print('Number Deleted From Front End = %d' %(arr[F]))
    F=(F+1)%size;
    te=te-1;

Program of Deque using Circular Array

Below is the complete program of double ended queue in python using a circular array having size 5.

Example

from array import *
import os

size = 5    # Maximum numbers to be stored in the array. We can increase the quantity by changing the value 5 with a new one
arr = array('i',[])     # An empty array for queue implementation
R = -1
F = 0
te = 0

# Initilise the array with 0
for i in range(0,size):
    arr.append(0)


while 1:    # An infinite while loop
    os.system('cls')    # Clear the console screen in Windows OS. For Linux and MacOS use os.system('clear')
    print('F=%d R=%d' %(F,R))
    print('1. Add Rear')
    print('2. Delete Rare')
    print('3. Add Front')
    print('4. Delete Front')
    print('5. Display')
    ch=int(input('Enter your choice '))

    if ch==1:
        # Check if the queue is full
        if te==size:
            print('Queue is full')
            input('Press enter to continue...')     # Pause the loop so that the user can see the above message Queue is full
        else:
            # If queue is not full then append the number in the array
            n=int(input('Enter a number '))
            R=(R+1)%size
            arr[R]=n
            te = te + 1

    elif ch==2:
        # Check if the queue is empty
        if te==0:
            print('Queue is empty')
            input('Press enter to continue...')     # Pause the loop so that the user can see the above message Queue is empty
        else:
            if R==-1:
                R=size-1
            print('Number Deleted From Rear End = %d' %(arr[R]))
            R=R-1
            te=te-1
            input('Press enter to continue...')     # Pause the loop so that the user can see the above message Number Removed = ?

    elif ch==3:
        # Check if the queue is full
        if te==size:
            print('Queue is full')
            input('Press enter to continue...')     # Pause the loop so that the user can see the above message Queue is full
        else:
            # If queue is not full then append the number in the array
            n=int(input('Enter a number '))
            if F==0:
                F=size-1
            else:
                F=F-1
            arr[F]=n
            te = te + 1

    elif ch==4:
        # Check if the queue is empty
        if te==0:
            print('Queue is empty')
            input('Press enter to continue...')     # Pause the loop so that the user can see the above message Queue is empty
        else:
            print('Number Deleted From Front End = %d' %(arr[F]))
            F=(F+1)%size;
            te=te-1;
            input('Press enter to continue...')     # Pause the loop so that the user can see the above message Number Removed = ?

    elif ch==5:
        # Check if the queue is empty
        if te==0:
            print('Queue is empty')
            input('Press enter to continue...')     # Pause the loop so that the user can see the above message Queue is empty
        else:
            # if queue is not empty then display all the number
            x = F
            for i in range(1,te+1):
                print(arr[x], end=' ')
                x=(x+1)%size
            input('\nPress enter to continue...')     # Pause the loop so that the user can see full queue on the screen
    else:
        print('Invalid Choice')
        input('Press enter to continue...')     # Pause the loop so that the user can see the above message Invalid Choice