Implementation of Deque using Circular Array asks to implement the following functions of a Deque using a circular array:
- insertFront(x) : inserts an element x at the front of the deque
- insertRear(x) : inserts an element x at the rear of the deque
- deleteFront(x) : delete an element x at the front of the deque
- deleteRear(x) : delete an element x at the rear of the deque
- getFront() : return the element present at the front of the deque
- getRear() : return the element present at the rear of the deque
- isEmpty() : return whether or not the Deque is empty
- 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)
- If the array is full, the element cannot be inserted.
- 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.
- Else decrement front and set arr[front] as x.
Time Complexity: O(1)
- insertRear()
- If the array is full, the element cannot be inserted.
- If there are no elements in the Deque, that is, rear equals -1, increment front and rear and set arr[rear] as x.
- Else increment rear and set arr[rear] as x.
Time Complexity: O(1)
- deleteFront()
- If the Deque is empty, return.
- If there is only one element in the Deque, that is, front equals rear, set front and rear as -1.
- Else increment front by 1.
Time Complexity: O(1)
- deleteRear()
- If the Deque is empty, return.
- If there is only one element in the Deque, that is, rear equals front, set front and rear as -1.
- Else decrement rear by 1.
Time Complexity: O(1)
- getFront()
- If the Deque is empty, return.
- Else return arr[front].
Time Complexity: O(1)
- getRear()
- If the Deque is empty, return.
- 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
Special thanks to Sagar Srivastava for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article