Implementation of Array Deque

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

Back to: Data Structure > Data Structure - Arrays

Leave a Reply

Your email address will not be published. Required fields are marked *