# Array Implementation of Deque

Implementation of Deque using Circular Array asks to implement the following functions of a Deque using a circular array:

1. insertFront(x) : inserts an element x at the front of the deque
2. insertRear(x)  : inserts an element x at the rear of the deque
3. deleteFront(x) : delete an element x at the front of the deque
4. deleteRear(x)  : delete an element x at the rear of the deque
5. getFront()     : return the element present at the front of the deque
6. getRear()     : return the element present at the rear of the deque
7. isEmpty()     : return whether or not the Deque is empty
8. isFull()     : return whether or not the Deque is full

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Algorithm for Each Operation

• insertFront(x)
1. If the array is full, the element cannot be inserted.
2. If there are no elements in the Deque(or array), that is, front equals -1, increment front and rear, and set arr[front] as x.
3. Else decrement front and set arr[front] as x.

Time Complexity: O(1)

• insertRear()
1. If the array is full, the element cannot be inserted.
2. If there are no elements in the Deque, that is, rear equals -1, increment front and rear and set arr[rear] as x.
3. Else increment rear and set arr[rear] as x.

Time Complexity: O(1)

• deleteFront()
1. If the Deque is empty, return.
2. If there is only one element in the Deque, that is, front equals rear, set front and rear as -1.
3. Else increment front by 1.

Time Complexity: O(1)

• deleteRear()
1. If the Deque is empty, return.
2. If there is only one element in the Deque, that is, rear equals front, set front and rear as -1.
3. Else decrement rear by 1.

Time Complexity: O(1)

• getFront()
1. If the Deque is empty, return.
2. Else return arr[front].

Time Complexity: O(1)

• getRear()
1. If the Deque is empty, return.
2. Else return arr[rear].

Time Complexity: O(1)

• isEmpty()

If the front is equal to -1 the Deque is empty, else it is not.

Time Complexity: O(1)

• isFull()

If (rear + 1) % n equals to the front then the Deque is full, else it is not. Here n is the maximum size of Deque.

Time Complexity: O(1)

Code:

## C++ Code

``````#include <iostream>
using namespace std;
const int MAX_SIZE = 100;
int deque[MAX_SIZE];

int front = -1;
int rear = -1;

bool isEmpty() {
if (front == -1) {
return true;
}
return false;
}

bool isFull() {
if ((rear + 1) % MAX_SIZE == front) {
return true;
}
return false;
}
void insertFront(int x) {
if (!isFull()) {
if (front == -1) {
front = rear = 0;
deque[front] = x;
}
else {
if (front == 0) {
front = MAX_SIZE - 1;
} else {
front--;
}
deque[front] = x;
}
}
}
void insertRear(int x) {
if (!isFull()) {
if (rear == -1) {
front = rear = 0;
deque[rear] = x;
}
else {
if (rear == MAX_SIZE - 1) {
rear = 0;
} else {
rear++;
}

deque[rear] = x;
}
}
}
void deleteFront() {
if (!isEmpty()) {
if (front == rear) {
front = rear = -1;
}
else {
if (front == MAX_SIZE - 1) {
front = 0;
} else {
front++;
}
}
}
}
void deleteRear() {
if (!isEmpty()) {
if (front == rear) {
front = rear = -1;
}
else {
if (rear == 0) {
rear = MAX_SIZE - 1;
} else {
rear--;
}
}
}
}
int getFront() {
if (!isEmpty()) {
return deque[front];
}
return -1;
}
int getRear() {
if (!isEmpty()) {
return deque[rear];
}
return -1;
}
int main() {
insertFront(5);
insertRear(10);
insertRear(11);
insertFront(19);
cout<<getFront()<<endl;
cout<<getRear()<<endl;
if (isFull()) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}
deleteRear();
cout<<getRear()<<endl;
deleteFront();
cout<<getFront()<<endl;
if (isEmpty()) {
cout<<"true"<<endl;
} else {
cout<<"false"<<endl;
}

return 0;
}
``````

Output:

19
11
false
10
5
false

## Java Code

``````class ImplementationOfDequeUsingCircularArray {
private static final int MAX_SIZE = 100;
private static int deque[];
private static int front = -1;
private static int rear = -1;

private static void insertFront(int x) {
if (!isFull()) {
if (front == -1) {
front = rear = 0;
deque[front] = x;
}
else {
if (front == 0) {
front = MAX_SIZE - 1;
} else {
front--;
}
deque[front] = x;
}
}
}
private static void insertRear(int x) {
if (!isFull()) {
if (rear == -1) {
front = rear = 0;
deque[rear] = x;
}
else {
if (rear == MAX_SIZE - 1) {
rear = 0;
} else {
rear++;
}
deque[rear] = x;
}
}
}
private static void deleteFront() {
if (!isEmpty()) {
if (front == rear) {
front = rear = -1;
}
else {
if (front == MAX_SIZE - 1) {
front = 0;
} else {
front++;
}
}
}
}
private static void deleteRear() {
if (!isEmpty()) {
if (front == rear) {
rear = front = -1;
}
else {
if (rear == 0) {
rear = MAX_SIZE - 1;
} else {
rear--;
}
}
}
}
private static int getFront() {
if (!isEmpty()) {
return deque[front];
}
return -1;
}
private static int getRear() {
if (!isEmpty()) {
return deque[rear];
}
return -1;
}
private static boolean isEmpty() {
if (front == -1) {
return true;
}
return false;
}
private static boolean isFull() {
if ((rear + 1) % MAX_SIZE == front) {
return true;
}
return false;
}
public static void main(String[] args) {
deque = new int[MAX_SIZE];

insertFront(5);
insertRear(10);
insertRear(11);
insertFront(19);
System.out.println(getFront());
System.out.println(getRear());
System.out.println(isFull());
deleteRear();
System.out.println(getRear());
deleteFront();
System.out.println(getFront());
System.out.println(isEmpty());
}
}
``````

Output:

19
11
false
10
5
false