Implementation of Deque using circular array

Difficulty Level Medium
Frequently asked in Amazon GE Healthcare Google Microsoft
Array Linked-List QueueViews 3698

Problem Statement

“Implementation of Deque using circular array” asks to implement the following functions of a Deque(Doubly Ended Queue) using circular array,

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

Example

Input
insertFront(5)
insertRear(10)
insertRear(11)
insertFront(19)
getFront()
getRear()
isFull()
deleteRear()
getRear()
deleteFront()
getFront()
isEmpty()

Output
19
11
false
10
5
false

Algorithm for Implementation of Deque using circular array

To implement Deque using a circular array we need to keep track of two pointer front and rear in the array. All the operations will be on these two pointers.
The meaning of circular array can be understood by the image below

Implementation of Deque using circular array

In this image the rear is behind the front, that is when rear was at the end of array and there were some empty slots in the starting of the array, so insertion of an element at the rear would cause the rear to come at position 0, this is because the circular array is circular in nature.

Create an array of size n, where n is the maximum size of Deque and initialize front and rear as -1, before any operation on the Deque.
As the array is circular increment front or rear when they are present at the end of the array will take them to the starting point and similarly decrementing front and rear when they are at the starting point will take them to the end of the array.

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 front is equals 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)

Java Code for Implementation of Deque using circular array

class ImplementationOfDequeUsingCircularArray {
    // Maximum size of Deque
    private static final int MAX_SIZE = 100;
    // Array to implement Deque
    private static int deque[];
    // Variables to represent front and rear of dequeue
    private static int front = -1;
    private static int rear = -1;

    private static void insertFront(int x) {
        // if array is not full
        if (!isFull()) {
            // case 1 : there are no elements
            // increment front and rear and add element at arr[front]
            if (front == -1) {
                front = rear = 0;
                deque[front] = x;
            }
            // else, decrement front circularly and add the
            // new element at arr[front]
            else {
                if (front == 0) {
                    front = MAX_SIZE - 1;
                } else {
                    front--;
                }
                deque[front] = x;
            }
        }
    }

    private static void insertRear(int x) {
        // if array is not full
        if (!isFull()) {
            // if this is the first element to be inserted
            // increment front and rear and add element at arr[rear]
            if (rear == -1) {
                front = rear = 0;
                deque[rear] = x;
            }
            // else increment rear circularly and add
            // new element at arr[rear]
            else {
                if (rear == MAX_SIZE - 1) {
                    rear = 0;
                } else {
                    rear++;
                }
                deque[rear] = x;
            }
        }
    }

    private static void deleteFront() {
        // if array is not empty
        if (!isEmpty()) {
            // if there is only 1 element
            // make front and rear as -1
            if (front == rear) {
                front = rear = -1;
            }
            // else increment front circularly
            else {
                if (front == MAX_SIZE - 1) {
                    front = 0;
                } else {
                    front++;
                }
            }
        }
    }

    private static void deleteRear() {
        // if array is not empty
        if (!isEmpty()) {
            // if there is only 1 element
            // make front and rear as -1
            if (front == rear) {
                rear = front = -1;
            }
            // else decrement rear circularly
            else {
                if (rear == 0) {
                    rear = MAX_SIZE - 1;
                } else {
                    rear--;
                }
            }
        }
    }

    private static int getFront() {
        // if array is not empty return arr[front]
        if (!isEmpty()) {
            return deque[front];
        }
        return -1;
    }

    private static int getRear() {
        // if array is not empty return arr[rear]
        if (!isEmpty()) {
            return deque[rear];
        }
        return -1;
    }

    private static boolean isEmpty() {
        // if front is -1 then deque is empty
        if (front == -1) {
            return true;
        }
        return false;
    }

    private static boolean isFull() {
        // if front is 1 ahead of rear then
        // deque is full
        if ((rear + 1) % MAX_SIZE == front) {
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
         deque = new int[MAX_SIZE];

         // Example
        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());
    }
}
19
11
false
10
5
false

C++ Code for Implementation of Deque using circular array

#include <iostream>
using namespace std;

// Maximum size of Deque
const int MAX_SIZE = 100;
// Array to implement Deque
int deque[MAX_SIZE];
// Variables to represent front and rear of dequeue
int front = -1;
int rear = -1;

bool isEmpty() {
    // if front is -1 then deque is empty
    if (front == -1) {
        return true;
    }
    return false;
}

bool isFull() {
    // if front is 1 ahead of rear then
    // deque is full
    if ((rear + 1) % MAX_SIZE == front) {
        return true;
    }
    return false;
}

void insertFront(int x) {
    // if array is not full
    if (!isFull()) {
        // case 1 : there are no elements
        // increment front and rear and add element at arr[front]
        if (front == -1) {
            front = rear = 0;
            deque[front] = x;
        } 
        // else, decrement front circularly and add the
        // new element at arr[front]
        else {
            if (front == 0) {
                front = MAX_SIZE - 1;
            } else {
                front--;
            }
            
            deque[front] = x;
        }
    }
}

void insertRear(int x) {
    // if array is not full
    if (!isFull()) {
        // if this is the first element to be inserted
        // increment front and rear and add element at arr[rear]
        if (rear == -1) {
            front = rear = 0;
            deque[rear] = x;
        } 
        // else increment rear circularly and add
        // new element at arr[rear]
        else {
            if (rear == MAX_SIZE - 1) {
                rear = 0;
            } else {
                rear++;
            }
            
            deque[rear] = x;
        }
    }
}

void deleteFront() {
    // if array is not empty
    if (!isEmpty()) {
        // if there is only 1 element
        // make front and rear as -1
        if (front == rear) {
            front = rear = -1;
        } 
        // else increment front circularly
        else {
            if (front == MAX_SIZE - 1) {
                front = 0;
            } else {
                front++;
            }
        }
    }
}

void deleteRear() {
    // if array is not empty
    if (!isEmpty()) {
        // if there is only 1 element
        // make front and rear as -1
        if (front == rear) {
            front = rear = -1;
        } 
        // else decrement rear circularly
        else {
            if (rear == 0) {
                rear = MAX_SIZE - 1;
            } else {
                rear--;
            }
        }
    }
}

int getFront() {
    // if array is not empty return arr[front]
    if (!isEmpty()) {
        return deque[front];
    }
    return -1;
}

int getRear() {
    // if array is not empty return arr[rear]
    if (!isEmpty()) {
        return deque[rear];
    }
    return -1;
}

int main() {
    // Example
    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;
}
19
11
false
10
5
false
Translate ยป