Array Deque/Dequeue Example Java Program


Definition

A double-ended queue is an abstract data type that generalizes a queue, for which elements can be added to or removed from either the front (head) or back (tail). It is also often called a head-tail linked list.

Array Deque/Dequeue Example Program

import java.util.Scanner;

class DequeueClass {

    private int[] array;
    private int val1, val2;

    public DequeueClass() {
        val1 = 0;
        val2 = 0;
        resize();
    }

    public boolean isEmpty() {
        return val2 == 0;
    }

    public void clear() {
        val1 = 0;
        val2 = 0;
        resize();
    }

    public int getSize() {
        return val2;
    }

    private void resize() {
        int[] num = new int[Math.max(2 * val2, 1)];
        for (int i = 0; i < val2; i++) {
            num[i] = array[(val1 + i) % array.length];
        }
        array = num;
        val1 = 0;
    }

    public int get(int index) {
        return array[(val1 + index) % array.length];
    }

    public int set(int a, int b) {
        int y = array[(val1 + a) % array.length];
        array[(val1 + a) % array.length] = b;
        return y;
    }

    public void add(int num1, int num2) {
        if (val2 + 1 > array.length) {
            resize();
        }
        if (num1 < val2 / 2) {

            val1 = (val1 == 0) ? array.length - 1 : val1 - 1;

            for (int i = 0; i <= num1 - 1; i++) {
                array[(val1 + i) % array.length] = array[(val1 + i + 1) % array.length];
            }
        } else {

            for (int i = val2; i > num1; i--) {
                array[(val1 + i) % array.length] = array[(val1 + i - 1) % array.length];
            }
        }
        array[(val1 + num1) % array.length] = num2;
        val2++;
    }

    public int remove(int position) {
        int x = array[(val1 + position) % array.length];
        if (position < val2 / 2) {

            for (int i = position; i > 0; i--) {
                array[(val1 + i) % array.length] = array[(val1 + i - 1) % array.length];
            }

            val1 = (val1 + 1) % array.length;
        } else {

            for (int i = position; i < val2 - 1; i++) {
                array[(val1 + i) % array.length] = array[(val1 + i + 1) % array.length];
            }
        }
        val2--;
        if (3 * val2 < array.length) {
            resize();
        }
        return x;
    }

    public void display() {
        int num = val1;
        for (int i = 0; i < val2; i++) {
            System.out.print(array[num % array.length] + " ");
            num++;
        }
        System.out.println();
    }
}

public class ArrayDequeueExample {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        DequeueClass dequeueClass = new DequeueClass();

        char character;

        do {
            System.out.println("\nMethods in Array Dequeue : \n");
            System.out.println("1. Size");
            System.out.println("2. Check if array is empty");
            System.out.println("3. Add Element");
            System.out.println("4. Get Element");
            System.out.println("5. Set Element");
            System.out.println("6. Remove Element");
            System.out.println("7. Clear");

            int choice = scan.nextInt();
            switch (choice) {
                case 1:
                    System.out.println("\nSize is " + dequeueClass.getSize());
                    break;
                case 2:
                    System.out.println("\nArray is Empty or Not : " + dequeueClass.isEmpty());
                    break;
                case 3:
                    System.out.println("Enter the index and element");
                    dequeueClass.add(scan.nextInt(), scan.nextInt());
                    break;
                case 4:
                    System.out.println("Enter index");
                    break;
                case 5:
                    System.out.println("Enter the index and element");
                    break;
                case 6:
                    System.out.println("\nEnter index");
                    dequeueClass.remove(scan.nextInt());
                    break;
                case 7:
                    System.out.println("\nArray cleared successfully");
                    dequeueClass.clear();
                    break;
                default:
                    System.out.println("Entry is Wrong \n ");
                    break;
            }

            dequeueClass.display();

            System.out.println("\nDo you wish to continue (Type Y or N) \n");
            character = scan.next().charAt(0);
        } while (character == 'Y' || character == 'y');
    }
}

Sample Output

Methods in Array Dequeue :

1. Size
2. Check if array is empty
3. Add Element
4. Get Element
5. Set Element
6. Remove Element
7. Clear
3
Enter the index and element
0
100
100

Do you wish to continue (Type Y or N)

Y

Methods in Array Dequeue :

1. Size
2. Check if array is empty
3. Add Element
4. Get Element
5. Set Element
6. Remove Element
7. Clear
3
Enter the index and element
1
1000
100 1000

Do you wish to continue (Type Y or N)

Y

Methods in Array Dequeue :

1. Size
2. Check if array is empty
3. Add Element
4. Get Element
5. Set Element
6. Remove Element
7. Clear
1

Size is 2
100 1000

Do you wish to continue (Type Y or N)

N