Implementation of Deque using a circular array

Implementation of Deque using a circular array
Implementation of Deque using a circular array

To implement Deque employing a circular array we should track 2 pointer front and rear within the array, all the operations are on these 2 pointers.

The which means of circular array will be understood by the image below.

In this image the rear is behind the front, that’s once rear was at the top of the array and there have been some empty slots within the beginning of the array, thus the insertion of part at the rear would cause the rear to return at position zero, this can be as a result of the circular array is circular in nature.

Create an associate array of size n, wherever n is that the most size of Deque and initialise front and rear as -1, before any operation on the Deque. because the array is circular increment front or rear once they are a gift at the top of the array can take them to the start line and equally decrementing front and rear once they are at the start line can take them to the top of the array.

insertFront(x)

  • If the array is full, the component can’t be inserted.
  • If there are not any components within the Deque(or array) it means the front is equal to  -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 already full then it not possible to insert more elements.
  • If there are not any elements within the Deque, that is rear which is equal to -1, increase 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’s just one component within the Deque, that is, rear equals front, set front and rear as -1.
  • Else decrement rear by one.

Time Complexity = O(1)

getFront()

  • If the Deque is empty, return.
  • Else come arr[front].

Time Complexity = O(1)

getRear()

  • If the Deque is empty, return.
  • Else come arr[rear].

Time Complexity = O(1)

isEmpty()
If front is equals to -1 the Deque is empty, else it’s not.
Time Complexity = O(1)
isFull()
If (rear + 1) % n equals to the front then the Deque is full, else it’s not. Here n is that the most size of Deque.
Time Complexity = O(1)

Implementation of Deque using circular array in Java:

class ImplementationOfDequeUsingCircularArray {
// Maximum size of Deque
private static final int MAXIMUM SIZE = 100;
// Array to implement Deque
private static int deque[];
// Variables for representing the 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 : If the array is empty of there is no element
// increase the 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 = MAXIMUM SIZE – 1;
} else {
front–;
}
deque[front] = x;
}
}
}
private static void insertRear(int x) {
// if array is not full
if (!isFull()) {
// Then we have to check if we are inserting first element in the array
// Now increase the 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 == MAXIMUM 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 == MAXIMUM 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 = MAXIMUM 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 equal to -1 it means dequeue is empty
if (front == -1) {
return true;
}
return false;
}
private static boolean isFull() {
// if front element is 1 ahead of rear element then
// deque is full
if ((rear + 1) % MAXIMUM SIZE == front) {
return true;
}
return false;
}
public static void main(String[] args) {
deque = new int[MAXIMUM 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());
}
}

Time Complexity: As the per all the operations performed we have found that time complexity of all operations like insertfront(), insertlast(), deletefront(), deletelast()is O(1).

Implementation of Deque using circular array in C++

#include <iostream>

using namespace std;
// Maximum size of Deque
const int MAXIMUM SIZE = 100;
// Array to implement Deque
int deque[MAXIMUM SIZE];
//Variables for representing the front and rear of dequeue
int front = -1;
int rear = -1;
bool isEmpty() {
// if front is -1 it means there are not elements i.e. deque is empty
if (front == -1) {
return true;
}
return false;
}
bool isFull() {
// if front element is 1 ahead of rear element then
// deque is full
if ((rear + 1) % MAXIMUM SIZE == front) {
return true;
}
return false;
}
void insertFront(int x) {
// if array is not full
if (!isFull()) {
// case 1 : there are no elements
// increase the 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 = MAXIMUM SIZE – 1;
} else {
front–;
}
deque[front] = x;
}
}
}
void insertRear(int x) {
// if array is not full
if (!isFull()) {
// if we are inserting for first time in the deque
// We have to increase the 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 == MAXIMUM 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 == MAXIMUM 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 = MAXIMUM 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;
}

Let’s try to solve a problem from LeetCode named “Next Greater Element II” which will give you a fair idea about circular array and how it actually works.

Given a circular array (the next element of the last element is the first element of the array), print the Next Greater Number for every element. The Next Greater Number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn’t exist, output -1 for this number.

Example 1:

Input: [1,2,1]
Output: [2,-1,2]
Explanation: The first 1’s next greater number is 2;
The number 2 can’t find next greater number;
The second 1’s next greater number needs to search circularly, which is also 2.

Note: The length of given array won’t exceed 10000.

The first way to approach circular array problems is to extend the original array to twice of its length, 2nd half has the same element as first half. It will simplify the problem. First let’s think of a Naive approach, Just look for the next greater element directly. Time complexity: O(n^2).

public class Solution {
public int[] nextGreaterElements(int[] nums) {
int maximum = Integer.MIN_VALUE;
for (int num : nums) {
maximum = Math.max(maximum, num);
}

    int length = nums.length;
    int[] result = new int[length];
    int[] check = new int[length * 2];

    for (int i = 0; i < length * 2; i++) {
        check[i] = nums[i % length];
    }

    for (int i = 0; i < length; i++) {
        output[i] = -1;
        if (nums[i] == maximum) continue;

        for (int j = i + 1; j < length * 2; j++) {
            if (check[j] > nums[i]) {
                output[i] = check[j];
                break;
            }
        }
    }
    return output;
}

}

The second way is that we can use a stack. First, we have to push all indexes into the stack, smaller index on the top. Then we start from the end of the array finding for the first element (index) in the stack which is greater than the current one. That will surely to be the Next Greater Element. Then push the current element (index) into the stack.
Time complexity: O(n)

public class Solution {
public int[] nextGreaterElements(int[] nums) {
int length = nums.length;
int[] output = new int[length];

    Stack<Integer> stack = new Stack<>();
    for (int i = length - 1; i >= 0; i--) {
        stack.push(i);
    }

    for (int i = length - 1; i >= 0; i--) {
        output[i] = -1;
        while (!stack.isEmpty() && nums[stack.peek()] <= nums[i]) {
            stack.pop();
        }
        if (!stack.isEmpty()){
            output[i] = nums[stack.peek()];
        }
        stack.add(i);
    }
    return output;
}

}

To explore more on Data Structures, click here.

By Yogesh Kumar