Deque circular array java

Deque or Double Ended Queue is a generalized version of Queue data structure that allows insert and delete at both ends.In previous post we had discussed introduction of deque. Now in this post we see how we implement deque Using circular array.
Operations on Deque:
Mainly the following four basic operations are performed on queue:
insetFront(): Adds an item at the front of Deque.
insertRear(): Adds an item at the rear of Deque.
deleteFront(): Deletes an item from front of Deque.
deleteRear(): Deletes an item from rear of Deque.

In addition to above operations, following operations are also supported
getFront(): Gets the front item from queue.
getRear(): Gets the last item from queue.
isEmpty(): Checks whether Deque is empty or not.
isFull(): Checks whether Deque is full or not.
deque

Circular array implementation deque
For implementing deque, we need to keep track of two indices, front and rear. We enqueue(push) an item at the rear or the front end of qedue and dequeue(pop) an item from both rear and front end.
Working
1. Create an empty array ‘arr’ of size ‘n’
initialize front = -1 , rear = 0
Inserting First element in deque, at either front or rear will lead to the same result.
deque - 1
After insert Front Points = 0 and Rear points = 0
Insert Elements at Rear end


a). First we check deque if Full or Not b). IF Rear == Size-1 then reinitialize Rear = 0 ; Else increment Rear by '1' and push current key into Arr[ rear ] = key Front remain same.

Insert Elements at Front end

a). First we check deque if Full or Not b). IF Front == 0 || initial position, move Front to points last index of array front = size - 1 Else decremented front by '1' and push current key into Arr[ Front] = key Rear remain same.

deque

Delete Element From Rear end

a). first Check deque is Empty or Not b). If deque has only one element front = -1 ; rear =-1 ; Else IF Rear points to the first index of array it's means we have to move rear to points last index [ now first inserted element at front end become rear end ] rear = size-1 ; Else || decrease rear by '1' rear = rear-1;

Delete Element From Front end


a). first Check deque is Empty or Not b). If deque has only one element front = -1 ; rear =-1 ; Else IF front points to the last index of the array it's means we have no more elements in array so we move front to points first index of array front = 0 ; Else || increment Front by '1' front = front+1;

deque -3

Below is the implementation of above idea.

C++

#include<iostream>
using namespace std;
#define MAX 100
class Deque
    int  arr[MAX];
    int  front;
    int  rear;
    int  size;
public :
    Deque(int size)
        front = -1;
        rear = 0;
        this->size = size;
    void  insertfront(int key);
    void  insertrear(int key);
    void  deletefront();
    void  deleterear();
    bool  isFull();
    bool  isEmpty();
    int  getFront();
    int  getRear();
bool Deque::isFull()
    return ((front == 0 && rear == size-1)||
            front == rear+1);
bool Deque::isEmpty ()
    return (front == -1);
void Deque::insertfront(int key)
    if (isFull())
        cout << "Overflow\n" << endl;
        return;
    if (front == -1)
        front = 0;
        rear = 0;
    else if (front == 0)
        front = size - 1 ;
        front = front-1;
    arr[front] = key ;
void Deque ::insertrear(int key)
    if (isFull())
        cout << " Overflow\n " << endl;
        return;
    if (front == -1)
        front = 0;
        rear = 0;
    else if (rear == size-1)
        rear = 0;
        rear = rear+1;
    arr[rear] = key ;
void Deque ::deletefront()
    if (isEmpty())
        cout << "Queue Underflow\n" << endl;
        return ;
    if (front == rear)
        front = -1;
        rear = -1;
        if (front == size -1)
            front = 0;
            front = front+1;
void Deque::deleterear()
    if (isEmpty())
        cout << " Underflow\n" << endl ;
        return ;
    if (front == rear)
        front = -1;
        rear = -1;
    else if (rear == 0)
        rear = size-1;
        rear = rear-1;
int Deque::getFront()
    if (isEmpty())
        cout << " Underflow\n" << endl;
        return -1 ;
    return arr[front];
int Deque::getRear()
    if(isEmpty() || rear < 0)
        cout << " Underflow\n" << endl;
        return -1 ;
    return arr[rear];
int main()
    Deque dq(5);
    cout << "Insert element at rear end  : 5 \n";
    dq.insertrear(5);
    cout << "insert element at rear end : 10 \n";
    dq.insertrear(10);
    cout << "get rear element " << " "
         << dq.getRear() << endl;
    dq.deleterear();
    cout << "After delete rear element new rear"
         << " become " << dq.getRear() << endl;
    cout << "inserting element at front end \n";
    dq.insertfront(15);
    cout << "get front element " << " "
         << dq.getFront() << endl;
    dq.deletefront();
    cout << "After delete front element new "
       << "front become " << dq.getFront() << endl;
    return 0;

Java

class Deque
    static final int MAX = 100;
    int  arr[];
    int  front;
    int  rear;
    int  size;
    public Deque(int size)
        arr = new int[MAX];
        front = -1;
        rear = 0;
        this.size = size;
    boolean isFull()
        return ((front == 0 && rear == size-1)||
            front == rear+1);
    boolean isEmpty ()
        return (front == -1);
    void insertfront(int key)
        if (isFull())
            System.out.println("Overflow"); 
            return;
        if (front == -1)
            front = 0;
            rear = 0;
        else if (front == 0)
            front = size - 1 ;
            front = front-1;
        arr[front] = key ;
    void insertrear(int key)
        if (isFull())
            System.out.println(" Overflow ");
            return;
        if (front == -1)
            front = 0;
            rear = 0;
        else if (rear == size-1)
            rear = 0;
            rear = rear+1;
        arr[rear] = key ;
    void deletefront()
        if (isEmpty())
            System.out.println("Queue Underflow\n");
            return ;
        if (front == rear)
            front = -1;
            rear = -1;
            if (front == size -1)
                front = 0;
                front = front+1;
    void deleterear()
        if (isEmpty())
            System.out.println(" Underflow");
            return ;
        if (front == rear)
            front = -1;
            rear = -1;
        else if (rear == 0)
            rear = size-1;
            rear = rear-1;
    int getFront()
        if (isEmpty())
            System.out.println(" Underflow");
            return -1 ;
        return arr[front];
    int getRear()
        if(isEmpty() || rear < 0)
            System.out.println(" Underflow\n");
            return -1 ;
        return arr[rear];
    public static void main(String[] args)
         Deque dq = new Deque(5);
         System.out.println("Insert element at rear end  : 5 ");
         dq.insertrear(5);
         System.out.println("insert element at rear end : 10 ");
         dq.insertrear(10);
         System.out.println("get rear element : "+ dq.getRear());
         dq.deleterear();
         System.out.println("After delete rear element new rear become : " + 
                                dq.getRear());
         System.out.println("inserting element at front end");
         dq.insertfront(15);
         System.out.println("get front element: " +dq.getFront());
         dq.deletefront();
         System.out.println("After delete front element new front become : " +
                                    +  dq.getFront());

Output: insert element at rear end : 5 insert element at rear end : 10 get rear element : 10 After delete rear element new rear become : 5 inserting element at front end get front element : 15 After delete front element new front become : 5

Time Complexity: Time complexity of all operations like insertfront(), insertlast(), deletefront(), deletelast()is O(1).

In mext post we will discuss deque implementation using Doubly linked list.

This article is contributed by Nishant Singh. If you like GeeksforGeeks and would like to contribute, you can also write an article using contribute.geeksforgeeks.org or mail your article to . See your article appearing on the GeeksforGeeks main page and help other Geeks.

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.


Recommended Posts:


Improved By : programmer2k17


Article Tags :

Queue

circular linked list

circular-array

deque


thumb_up
1

To-do Done

2.2
Based on 45 vote(s)

Please write to us at to report any issue with the above content.

Post navigation

Previous

first_page Distance of nearest cell having 1 in a binary matrix

Next

last_page Paytm Interview Experience | Set 12 (For 1.5 Years Experienced)


Related news

Tabanan bali homestay accommodation
Irib 3 frequency hotbird polarization
Tonality modality difference between
Prevenir conductas de riesgo en adolescentes orquesta
Jeans de moda 2019 mujer rotoshop
Tattvam boutique ahmedabad mirror
Vampire queen series pdf files
Gros ventra quoi faire quebec
Scroll modalpanel rich faces eclipse
Beechcraft queen air a65 specifications