Question

Create a Deque class based on the following description of deque (double-ended queues). A dequeue is a double-ended queue. You can insert items at either end and delete them from either end. Therefore, the deque offers two insert operations and two remove operations: insertLeft() and insertRight() removeLeft() and removeRight(). Deques may also have "peek" methods ( peekLeft() and peekRight() )that let you see the left or right item in the deque without remove the item from the deque. For this problem, your Deque class should contain the following methods: insertLeft(), insertRight(), removeLeft(), removeRight(), peekRight(), peekLeft(), isEmpty(), and isFull(). It will need to support wraparound at the end of the array, as the Queue class in the provided code does. You are asked to use an array to define the Deque class. Write a driver class to test class Deque.

Answer 1

Following is the java Program:

Dequeue.java

import java.util.NoSuchElementException;
import java.util.Random;

public class Deque {

    private final int arr[];
    private int head;
    private int size;

    public Deque(int capacity) {
        arr = new int[capacity];
    }

    public void insertLast(int element) {
        checkCapacity();
        arr[(head + size++) % arr.length] = element;
    }

    public void insertFirst(int element) {
        checkCapacity();

        if (head == 0) {
            arr[(head = arr.length - 1)] = element;
        } else {
            arr[(--head) % arr.length] = element;
        }

        size++;
    }

    public int removeFirst() {
        checkNotEmpty();

        int ret = arr[head];
        head = (head + 1) % arr.length;
        size--;
        return ret;
    }

    public int removeLast() {
        checkNotEmpty();

        int ret = arr[(head + size - 1) % arr.length];
        size--;
        return ret;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");

        for (int i = 0; i < size; ++i) {
            sb.append(arr[(head + i) % arr.length]);

            if (i < size - 1) {
                sb.append(", ");
            }
        }

        return sb.append("]").toString();
    }

    public int size() {
        return size;
    }

    private void checkCapacity() {
        if (arr.length == size) {
            throw new IllegalStateException("No more space is available.");
        }
    }

    private void checkNotEmpty() {
        if (size == 0) {
            throw new NoSuchElementException("Trying to pop an empty deque.");
        }
    }

    public static void main(String args[]) {
        Deque deque = new Deque(10);
        Random random = new Random();

        for (int op = 0; op < 30; ++op) {
            if (deque.size() == 0) {
                int num = random.nextInt(100);
                System.out.print("Adding " + num + " to front: ");
                deque.insertLast(num);
                System.out.println(deque);
            } else {
                boolean add = random.nextBoolean();

                if (add) {
                    boolean front = random.nextBoolean();
                    int num = random.nextInt(100);

                    if (front) {
                        System.out.print("Adding " + num + " to front: ");
                        deque.insertFirst(num);
                        System.out.println(deque);
                    } else {
                        System.out.print("Adding " + num + " to back:  ");
                        deque.insertLast(num);
                        System.out.println(deque);
                    }
                } else {
                    boolean front = random.nextBoolean();

                    if (front) {
                        System.out.print("Removing from front: ");
                        deque.removeFirst();
                        System.out.println(deque);
                    } else {
                        System.out.print("Removing from back:  ");
                        deque.removeLast();
                        System.out.println(deque);
                    }
                }
            }
        }
    }
}

DequeApp.java

import java.util.Scanner;

public class Deque {
    public static void main(String[] args) {
        Deque t= new Deque(10);

        //for stack
        t.insertFirst(2);
        t.insertFirst(3);
        t.removeLast();

        //for queue
        t.insertFirst(4);
        t.insertFirst(5);
        t.removeFirst();

        //dequeue
        t.insertFirst(5);
        t.insertLast(6);
        t.removeFirst();
        t.removeLast();
    }
}