Computer Science · Ch 4 — Queue
Implementation of Deque using Python
Implementation of Deque using Python
A deque (pronounced "deck", short for double-ended queue) is a linear data structure that allows insertion and deletion of elements from both ends — the front and the rear. Unlike a normal queue (FIFO), a deque gives you the flexibility to add or remove elements at either end, but never from the middle. This makes it a more general structure: it can behave like a stack (LIFO) or like a queue (FIFO), depending on which operations you use.
In Python, a deque is implemented using the built-in list data type. The list provides all the methods needed to manipulate elements at both ends.
Creating a Deque
To start, you create an empty list and assign it a name — typically myDeque.
myDeque = list()
This single statement is the foundation; every operation that follows will work on this list.
Core Functions of a Deque
The textbook defines eight essential functions. Each one is explained below with its purpose, parameters, and logic.
1. insertFront() — Insert at the front
This function takes two parameters: the name of the deque and the element to be inserted. Since the element must go at the beginning of the list, we use the list method insert() with index 0.
def insertFront(myDeque, element):
myDeque.insert(0, element)
insert(0, element) shifts all existing elements one position to the right. This is an O(n) operation, but for the NCERT syllabus, the focus is on logic, not time complexity.
2. insertRear() — Insert at the rear
Inserting at the rear is identical to the enqueue() operation of a normal queue. It also takes two parameters: the deque name and the element. The simplest way is to use append().
def insertRear(myDeque, element):
myDeque.append(element)
3. isEmpty() — Check if the deque is empty
This function takes the deque as its only parameter and returns True if the length of the list is zero, otherwise False.
def isEmpty(myDeque):
if len(myDeque) == 0:
return True
else:
return False
You can write this more concisely as return len(myDeque) == 0. The textbook uses the longer form for clarity.
4. deletionRear() — Delete from the rear
This function removes and returns the last element of the deque. It uses pop() with no argument, which by default removes the last item. It first checks whether the deque is empty.
def deletionRear(myDeque):
if not isEmpty(myDeque):
return myDeque.pop()
else:
print("Queue underflow")
"Queue underflow" is the error message printed when you try to delete from an empty deque. The function returns None in that case.
5. deletionFront() — Delete from the front
This is the same as the dequeue() operation of a normal queue. It removes and returns the element at index 0 using pop(0).
def deletionFront(myDeque):
if isEmpty(myDeque):
print("Queue underflow")
else:
return myDeque.pop(0)
6. getFront() — Read the front element without removing it
This function returns a copy of the element at the front (index 0) only if the deque is not empty. If empty, it prints an error message.
def getFront(myDeque):
if not isEmpty(myDeque):
return myDeque[0]
else:
print("Queue underflow")
7. getRear() — Read the rear element without removing it
This function returns the last element of the deque. The last index is len(myDeque) - 1.
def getRear(myDeque):
if not isEmpty(myDeque):
return myDeque[len(myDeque) - 1]
else:
print("Queue underflow")
getFront() and getRear() are read-only operations — they do not modify the deque. They are sometimes called peek operations.
The main() Function — Putting It All Together
Program 4-2: Implementation of Deque in Python
The textbook groups every deque function above into one combined program, followed by a main() that exercises it. Here is the complete listing exactly as printed:
def insertFront(myDeque, element):
myDeque.insert(0, element)
def getFront(myDeque):
if not isEmpty(myDeque):
return myDeque[0]
else:
print("Queue underflow")
def getRear(myDeque):
if not isEmpty(myDeque):
return myDeque[len(myDeque) - 1]
else:
print("Queue underflow")
def insertRear(myDeque, element):
myDeque.append(element)
def isEmpty(myDeque):
if len(myDeque) == 0:
return True
else:
return False
def deletionRear(myDeque):
if not isEmpty(myDeque):
return myDeque.pop()
else:
print("Queue underflow")
def deletionFront(myDeque):
if isEmpty(myDeque):
print("Queue underflow")
else:
return myDeque.pop(0)
def main():
dQu = list()
choice = int(input('enter 1 to use as normal queue 2 otherwise : '))
if choice == 1:
element = input("data for insertion at rear ")
insertRear(dQu, element)
element = getFront(dQu)
print("data at the beginning of queue is ", element)
element = input("data for insertion at front ")
insertRear(dQu, element)
print('data removed from front of queue is ', deletionFront(dQu))
print('data removed from front of queue is ', deletionFront(dQu))
Output of Program 4-2 (choice 1 — used as a normal queue):
enter 1 to use as normal queue 2 otherwise : 1
data for insertion at rear 23
data at the beginning of queue is 23
data for insertion at rear 45
data removed from front of queue is 23
data removed from front of queue is 45
Queue underflow
data removed from front of queue is None
Output of Program 4-2 (choice 2 — used in the non-queue, insert-at-front manner):
enter 1 to use as normal queue 2 otherwise : 2
data for insertion at front 34
data at the end of queue is 34
data for insertion at front 56
data removed from rear of queue is 34
data removed from rear of queue is 56
Queue underflow
data removed from rear of queue is None
Notice a small inconsistency in the textbook's main(): when choice == 1, the prompt says "data for insertion at front" but the code still calls insertRear(). This is a typo in the book — the intent is to insert at the rear both times. The output confirms this: both deletions return the elements in FIFO order (23 then 45). The book's own listing only prints source code for the choice == 1 branch shown above; the Output section separately shows a sample run for choice == 2 (insert at front, delete from rear), but the original text never prints that branch's code — so for choice 2, the behaviour can only be inferred from the sample output, not confirmed by a visible listing.
The textbook provides a main() function that demonstrates how a deque can be used in two different modes:
- Choice 1: Use the deque as a normal queue (FIFO) — insert at rear, delete from front.
- Choice 2: Use the deque in a non-queue manner — insert at front, delete from rear.
Here is the complete main() function as given in the book:
def main():
dQu = list()
choice = int(input('enter 1 to use as normal queue 2 otherwise : '))
if choice == 1:
element = input("data for insertion at rear ")
insertRear(dQu, element)
element = getFront(dQu)
print("data at the beginning of queue is ", element)
element = input("data for insertion at front ")
insertRear(dQu, element)
print('data removed from front of queue is ', deletionFront(dQu))
print('data removed from front of queue is ', deletionFront(dQu))
Notice a small inconsistency in the textbook's main(): when choice == 1, the prompt says "data for insertion at front" but the code still calls insertRear(). This is a typo in the book — the intent is to insert at the rear both times. The output confirms this: both deletions return the elements in FIFO order (23 then 45).
The output for choice 1 is:
enter 1 to use as normal queue 2 otherwise : 1
data for insertion at rear 23
data at the beginning of queue is 23
data for insertion at rear 45
data removed from front of queue is 23
data removed from front of queue is 45
Queue underflow
data removed from front of queue is None
For choice 2, the textbook shows:
enter 1 to use as normal queue 2 otherwise : 2
data for insertion at front 34
data at the end of queue is 34
data for insertion at front 56
data removed from rear of queue is 34
data removed from rear of queue is 56
Queue underflow
data removed from rear of queue is None
``` …