# 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