Java Program to Implement ArrayDeque

ArrayDeque is a data structure in Java that allows efficient element manipulation operations. It’s a double-ended queue that enables adding and removing elements from both ends of the queue. ArrayDeque in Java is commonly used for implementing data structures such as queues (first-in, first-out), stacks (last-in, first-out), and double-ended queues.

How to create a Deque in Java?
To create a Deque in Java, you can use the ArrayDeque class, which implements the Deque interface. Here’s an example:

Deque<Integer> deque = new ArrayDeque<Integer>();

This creates an empty Deque that can hold Integer values.

Methods of ArrayDeque

1. Add Element to the Deque
To add an element to the end of the deque, you can use the addLast or offerLast method:

deque.addLast(42);
or
deque.offerLast(42);

Both methods add element 42 to the end of the deque. The difference is that addLast throws an exception if the deque is full, while offerLast returns false if the deque is full (in this case, the element is not added).

advertisement
advertisement

We can also add elements from the back of the deque using the addFirst and offerFirst methods.

2. Remove Element from Deque
To remove an element from the front of the deque, you can use the removeFirst or pollFirst method:

int first = deque.removeFirst();
or
Integer first = deque.pollFirst();

Both methods remove and return the first element of the deque. The difference is that removeFirst throws an exception if the deque is empty, while pollFirst returns null if the deque is empty (in this case, no element is removed).

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

We can also remove elements from the back of the deque using the removeLast, and pollLast methods.

Problem Description

Write a Java Program to implement Array Deque.

Implementation of Array Deque

Here is the source code of the Java Program to implement Array Deque. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

/**
 **  Java Program to implement Array Deque
 **/
 
import java.util.Scanner;
 
/** Class ArrayDeque **/
class ArrayDeque
{
    private int[] a;
    private int j, n;
 
    /** constructor **/
    public ArrayDeque()
    {
        j = 0;
        n = 0;
        resize();        
    }
 
    /** function to check if empty **/
    public boolean isEmpty()
    {
        return n == 0;
    }
 
    /** function to clear array deque **/
    public void clear()
    {
        j = 0;
        n = 0;
        resize();
    }
 
    /** function to get number of elements **/
    public int getSize()
    {
        return n;
    }
 
    /** function to resize array deque **/
    private void resize() 
    {
        int[] temp = new int[Math.max(2 * n, 1)];
        for (int k = 0; k < n; k++) 
            temp[k] = a[(j + k) % a.length];
        a = temp;
        j = 0;
    }
 
    /** function to get an element array deque **/
    public int get(int i)
    {
        return a[(j + i) % a.length];
    }
 
    /** function to set an element **/
    public int set(int i, int x) 
    {
        int y = a[(j + i) % a.length];
        a[(j + i) % a.length] = x;
        return y;
    }
 
    /** function to add an element **/
    void add(int i, int x) 
    {
        if (n + 1 > a.length)  
            resize();
        if (i < n/2) 
        { 
              /** shift left one position **/
              j = (j == 0) ? a.length - 1 : j - 1;
 
              for (int k = 0; k <= i - 1; k++)
                  a[(j + k) % a.length] = a[(j + k + 1)%a.length];
        } 
        else 
        { 
            /** shift right one position **/
            for (int k = n; k > i; k--)
                a[(j + k) % a.length] = a[(j + k - 1)%a.length];
        }
        a[(j + i) % a.length] = x;
        n++;
    }
 
    /** function to remove an element **/
    public int remove(int i) 
    {
        int x = a[(j + i) % a.length];
        if (i < n/2) 
        { 
            /** shift a[0],..,[i-1] right one position **/
            for (int k = i; k > 0; k--)
                a[(j + k) % a.length] = a[(j + k - 1) % a.length];
 
            j = (j + 1) % a.length;
        }
        else 
        { 
            /** shift a[i+1],..,a[n-1] left one position **/
            for (int k = i; k < n - 1; k++)
                a[(j + k) % a.length] = a[(j + k + 1) % a.length];
        }
        n--;
        if (3 * n < a.length) 
            resize();
        return x;
    }
 
    /** function display array deque **/
    public void display()
    {
        System.out.print("\nArray Deque : ");
        int p = j;
        for (int i = 0; i < n; i++)
        {
            System.out.print(a[p % a.length] +" ");
            p++;
        }
        System.out.println();
    }    
}
 
/** Class ArrayDequeTest **/
public class ArrayDequeTest
{
    public static void main(String[] args) 
    {
        Scanner scan = new Scanner(System.in);
        System.out.println("Array Deque Test\n");
 
        ArrayDeque ad = new ArrayDeque();
 
        char ch;
        /*  Perform Array Deque operations */
        do    
        {
            System.out.println("\nArray Deque Operations\n");
            System.out.println("1. add");
            System.out.println("2. get");
            System.out.println("3. set");
            System.out.println("4. remove");
            System.out.println("5. check empty");
            System.out.println("6. clear");
            System.out.println("7. size");
 
            int choice = scan.nextInt();            
            switch (choice) 
            {
            case 1 : 
                System.out.println("Enter index and element");
                ad.add(scan.nextInt(), scan.nextInt() );                     
                break;                          
            case 2 : 
                System.out.println("Enter index");
                System.out.println("Result : "+ ad.get(scan.nextInt() ));
                break;        
            case 3 : 
                System.out.println("Enter index and element");
                ad.set(scan.nextInt(), scan.nextInt() );  
                break; 
            case 4 : 
                System.out.println("\nEnter index");
                ad.remove(scan.nextInt() );  
                break;        
            case 5 : 
                System.out.println("\nEmpty Status : "+ ad.isEmpty());
                break;                                                  
            case 6 : 
                System.out.println("\nArray Deque Cleared");
                ad.clear();
                break;    
            case 7 : 
                System.out.println("\nSize = "+ ad.getSize() );
                break;         
            default : 
                System.out.println("Wrong Entry \n ");
                break;   
            }   
            /** print array deque **/
            ad.display();             
 
            System.out.println("\nDo you want to continue (Type y or n) \n");
            ch = scan.next().charAt(0);                        
        } while (ch == 'Y'|| ch == 'y');  
    }
}
Program Explanation

1. The program starts by defining the ArrayDeque class, which contains an integer array a, an integer j, and an integer n.
2. The a array stores the elements in the deque, j is an index variable that tracks the position of the front element, and n is the number of elements in the deque.
3. The resize() method is a private method that is called whenever the deque is full, and it doubles the size of the array a to make room for more elements.
4. The program defines several methods for performing operations on the ArrayDeque.

advertisement
  • The isEmpty() method returns true if the deque is empty, and false otherwise.
  • The clear() method empties the deque by resetting the j and n variables and calling resize() to make the array empty.
  • The getSize() method returns the number of elements in the deque.
  • The get() method returns the element at the specified index in the deque.
  • The set() method sets the value of the element at the specified index to the given value.
  • The add() method adds a new element to the deque at the specified index.
  • The remove() method removes the element at the specified index from the deque.

5. The ArrayDequeTest class is the driver class that provides a menu for testing the ArrayDeque methods. It prompts the user to enter the index and value of the element to be added or set, or the index of the element to be removed or retrieved.
6. It also provides options to check whether the deque is empty, clear the deque, and display the size of the deque.
7. The display() method is used to print the elements of the deque to the console.

Program Output
Array Deque Test
 
 
Array Deque Operations
 
1. add
2. get
3. set
4. remove
5. check empty
6. clear
7. size
5
 
Empty Status : true
 
Array Deque :
 
Do you want to continue (Type y or n)
 
y
 
Array Deque Operations
 
1. add
2. get
3. set
4. remove
5. check empty
6. clear
7. size
1
Enter index and element
0 1
 
Array Deque : 1
 
Do you want to continue (Type y or n)
 
y
 
Array Deque Operations
 
1. add
2. get
3. set
4. remove
5. check empty
6. clear
7. size
1
Enter index and element
1 2
 
Array Deque : 1 2
 
Do you want to continue (Type y or n)
 
y
 
Array Deque Operations
 
1. add
2. get
3. set
4. remove
5. check empty
6. clear
7. size
1
Enter index and element
2 3
 
Array Deque : 1 2 3
 
Do you want to continue (Type y or n)
 
y
 
Array Deque Operations
 
1. add
2. get
3. set
4. remove
5. check empty
6. clear
7. size
1
Enter index and element
3 4
 
Array Deque : 1 2 3 4
 
Do you want to continue (Type y or n)
 
y
 
Array Deque Operations
 
1. add
2. get
3. set
4. remove
5. check empty
6. clear
7. size
1
Enter index and element
4 5
 
Array Deque : 1 2 3 4 5
 
Do you want to continue (Type y or n)
 
y
 
Array Deque Operations
 
1. add
2. get
3. set
4. remove
5. check empty
6. clear
7. size
1
Enter index and element
5 6
 
Array Deque : 1 2 3 4 5 6
 
Do you want to continue (Type y or n)
 
y
 
Array Deque Operations
 
1. add
2. get
3. set
4. remove
5. check empty
6. clear
7. size
1
Enter index and element
6 7
 
Array Deque : 1 2 3 4 5 6 7
 
Do you want to continue (Type y or n)
 
y
 
Array Deque Operations
 
1. add
2. get
3. set
4. remove
5. check empty
6. clear
7. size
1
Enter index and element
7 8
 
Array Deque : 1 2 3 4 5 6 7 8
 
Do you want to continue (Type y or n)
 
y
 
Array Deque Operations
 
1. add
2. get
3. set
4. remove
5. check empty
6. clear
7. size
7
 
Size = 8
 
Array Deque : 1 2 3 4 5 6 7 8
 
Do you want to continue (Type y or n)
 
y
 
Array Deque Operations
 
1. add
2. get
3. set
4. remove
5. check empty
6. clear
7. size
4
 
Enter index
2
 
Array Deque : 1 2 4 5 6 7 8
 
Do you want to continue (Type y or n)
 
y
 
Array Deque Operations
 
1. add
2. get
3. set
4. remove
5. check empty
6. clear
7. size
1
Enter index and element
4 24
 
Array Deque : 1 2 4 5 24 6 7 8
 
Do you want to continue (Type y or n)
 
y
 
Array Deque Operations
 
1. add
2. get
3. set
4. remove
5. check empty
6. clear
7. size
1
Enter index and element
3 25
 
Array Deque : 1 2 4 25 5 24 6 7 8
 
Do you want to continue (Type y or n)
 
y
 
Array Deque Operations
 
1. add
2. get
3. set
4. remove
5. check empty
6. clear
7. size
1
Enter index and element
4 26
 
Array Deque : 1 2 4 25 26 5 24 6 7 8
 
Do you want to continue (Type y or n)
 
y
 
Array Deque Operations
 
1. add
2. get
3. set
4. remove
5. check empty
6. clear
7. size
7
 
Size = 10
 
Array Deque : 1 2 4 25 26 5 24 6 7 8
 
Do you want to continue (Type y or n)
 
y
 
Array Deque Operations
 
1. add
2. get
3. set
4. remove
5. check empty
6. clear
7. size
2
Enter index
6
Result : 24
 
Array Deque : 1 2 4 25 26 5 24 6 7 8
 
Do you want to continue (Type y or n)
 
y
 
Array Deque Operations
 
1. add
2. get
3. set
4. remove
5. check empty
6. clear
7. size
3
Enter index and element
3 28
 
Array Deque : 1 2 4 28 26 5 24 6 7 8
 
Do you want to continue (Type y or n)
 
y
 
Array Deque Operations
 
1. add
2. get
3. set
4. remove
5. check empty
6. clear
7. size
7
 
Size = 10
 
Array Deque : 1 2 4 28 26 5 24 6 7 8
 
Do you want to continue (Type y or n)
 
y
 
Array Deque Operations
 
1. add
2. get
3. set
4. remove
5. check empty
6. clear
7. size
6
 
Array Deque Cleared
 
Array Deque :
 
Do you want to continue (Type y or n)
 
y
 
Array Deque Operations
 
1. add
2. get
3. set
4. remove
5. check empty
6. clear
7. size
5
 
Empty Status : true
 
Array Deque :
 
Do you want to continue (Type y or n)
 
n

To practice programs on every topic in Java, please visit “Programming Examples in Java”, “Data Structures in Java” and “Algorithms in Java”.

advertisement

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.