Implementation of Array Deque - Learn Coding Online

Table of Contents

Deque (or double-ended queue) is a data structure that allows us to add and remove items from both ends. It can be quite useful since it can be used as a stack or a queue.

How to implement an Array Deque?

Functionalities

The Deque data structure contains the following functionalities.

isEmpty(): This method checks if the deque is empty.
isFull(): It returns true if the deque is full.
insertFront(): This function adds an item at the front of the deque.
insertRear(): It inserts an item at the end.
removeFront(): It removes an item from the start.
removeRear(): This method deletes an item from the end.
getFront(): It returns an item that is at the front.
getRear(): It returns an element at the rear.
getSize(): This method returns the length of the deque.

Let’s see how we can implement these functionalities using a circular array.

Since the deque is opened at both ends, we will have two variables to keep track of the front and the rear. Initially, we set front = -1 and rear = -1.

Deque is Empty

A deque is empty if the front and rear are equal to -1.

Deque is Full

If front = 0 and rear = n-1 or front = rear+1, then the deque is full. Here, n is the size of the deque.

Insert an Item at the Front

First, we need to check if the deque is full. If it is, we cannot add more items to it, and therefore, we raise an error.
If the deque is empty ( front = -1 and rear = -1), then we set front = 0 and rear = 0.
If front=0, then we change the front to n-1.
Otherwise, we set front – = -1.

Finally, we add an item at the updated front.

Insert an Item at the Rear

If the deque is full, then we raise an error.
If it is the first element to be inserted, we set front = 0 and rear = 0.
If rear = n-1, then we move the rear to index 0.
Otherwise, we increment the rear, i.e., rear += 1.

Then, we insert the new value at the rear.

Delete an Item from the Front

Here, we raise an error if the deque is empty.
If the front=rear, then it is the last item in the deque. Therefore, we set front =-1 and rear =-1.
If the front = n-1, then we change its position to 0.
Otherwise, we increment the front.

Finally, the value of the deleted item gets returned.

Delete an Item from the rear

If there are no items in the deque, an error gets raised.
If the deque has only one item, then we reset the deque, i.e., front =-1 and rear =-1.
We change the location of the rear to n-1 if it is at index 0.
Otherwise, we decrement the rear.

The deleted element gets returned at the end.

Code

Consider the following code that implements deque using a circular array.

class Deque:
  def __init__(self, size):
    self.size = size
    self.array = [None]*self.size
    self.front = -1
    self.rear = -1
  
  def isEmpty(self):
    if (self.front==-1 and self.rear==-1):
      return True
    else:
      return False

  def isFull(self):
    if ((self.front==0 and self.rear==self.size-1) or (self.front==self.rear+1)):
      return True
    else:
      return False

  def insertFront(self, value):
    if (self.isFull()):
      raise Exception("Error: Cannot insert to a full deque")
    elif (self.isEmpty()): #adding to a empty deque
      self.rear=0
      self.front=0  
    elif (self.front==0):
      self.front = self.size-1 
    else:
      self.front -=1 
    self.array[self.front] = value
  
  def insertRear(self, value):
    if (self.isFull()):
      raise Exception("Error: Cannot insert to a full deque")
    elif (self.isEmpty()): #adding to a empty deque
      self.rear=0
      self.front=0  
    elif (self.rear==self.size-1):
      self.rear = 0
    else:
      self.rear +=1 
    self.array[self.rear] = value

  def removeFront(self):
    if (self.isEmpty()):
      raise Exception("Error: Cannot delete from an empty deque")
    elif (self.front==self.rear): #last item
      value=self.array[self.front]
      self.array[self.front] = None
      self.front=-1
      self.rear=-1
    elif (self.front==self.size-1):
      value=self.array[self.front]
      self.array[self.front] = None
      self.front=0
    else:
      value=self.array[self.front]
      self.array[self.front] = None
      self.front += 1
    return value

  def removeRear(self):
    if (self.isEmpty()):
      raise Exception("Error: Cannot delete from an empty deque")
    elif (self.front==self.rear):  #last item
      value=self.array[self.rear]
      self.array[self.rear] = None
      self.front=-1
      self.rear=-1
    elif (self.rear==0):
      value=self.array[self.rear]
      self.array[self.rear] = None
      self.rear=self.size-1
    else:
      value=self.array[self.rear]
      self.array[self.rear] = None
      self.rear -= 1
    return value

  def getFront(self):
    if (self.isEmpty()):
      raise Exception("Error: Cannot access from an empty deque")
    else:
      return self.array[self.front]
  
  def getRear(self):
    if (self.isEmpty()):
      raise Exception("Error: Cannot access from an empty deque")
    else:
      return self.array[self.rear]

  def getSize(self):
    return self.size


d =  Deque(4) #[None, None, None, None]

d.insertFront(3) #[3, None, None, None]
d.insertRear(4) #[3, 4, None, None]
d.insertFront(5) #[3, 4, None, 5]
d.insertRear(6) #[3, 4, 6, 5]

print("Deleted Item:", d.removeFront()) #[3, 4, 6, None]
print("Deleted Item:", d.removeRear()) #[3, 4, None, None]

print("Item at front:", d.getFront())
print("Item at rear:", d.getRear())

Output

Deleted Item: 5
Deleted Item: 6
Item at front: 3
Item at rear: 4