Array-based deque in Java

Question

Are the conditions which I have included for insertion and deletion from front and rear sufficient and necessary? Have I missed some condition check? Or have I included some redundant condition?

import java.io.*;
class Dequeue
{
int arr[];
int lim;
int front;
int rear;
public Dequeue(int l)
{
    lim=l;
    front=rear=0;
    arr=new int[(l+1)];
}
void addrear(int val)
{
   if(front==0 && rear ==0)
   {
    front=1;
    rear=1;
    arr[1]=val;
   }
   else if(rear==lim)
   {
   System.out.println("Overflow");
   }
   else 
   {
   arr[++rear]=val;
   } 
}
void addfront(int val)
{
    if(front==0 && rear ==0)
    {
    front=1;
    rear=1;
    arr[1]=val;
    }
    else if(front==1)
    {
        System.out.println("Overflow");
    }
    else
    {
    arr[--front]=val;
    }
}
void poprear()
{
    if(front==rear)
    {
        System.out.println(arr[front]);
        front=0;
        rear=0;

    }
    else if(front==0 && rear==0)
    {
       System.out.println("Underflow");
    }
    else
    {
        System.out.println(arr[rear]);
        rear--;

    }

}
void popfront()
{
    if(front==rear)
    {
        System.out.println(arr[front]);
        front=0;
        rear=0;

    }
    else if(front==0 && rear==0)
    {
       System.out.println("Underflow");
    }
    else
    {
        System.out.println(arr[front]);
        front++;

         }
      }
void display()
{
if(front!=0 || rear!=0)
{
    for(int i=front;i<=rear;i++)
   {
        System.out.print(arr[i]);
   }
   System.out.println();
}

else
System.out.println("Empty");
}
public static void main(String args[])throws IOException
{
int flag=0;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter size of array");
Dequeue obj=new Dequeue(Integer.parseInt(br.readLine()));
while(flag==0)
{
System.out.println("1 for addrear");
System.out.println("2 for addfront");
System.out.println("3 for poprear");
System.out.println("4 for popfront");
System.out.println("5 for exit");
int ch=Integer.parseInt(br.readLine());
switch(ch)
{
    case 1:
           System.out.println("Enter element");
           obj.addrear(Integer.parseInt(br.readLine()));
           obj.display();
           break;
    case 2:System.out.println("Enter element");
           obj.addfront(Integer.parseInt(br.readLine()));
           obj.display();
           break;
    case 3:obj.poprear();
           obj.display();
           break;
    case 4:obj.popfront();
           obj.display();
           break;
    case 5:flag=1;
           break;

}
}

}
}

Answer 1

Formatting:

First of all, indent your code properly; each level of identation should include four spaces. So instead of

class Dequeue
{
int arr[];
...

Rewrite it as

class Dequeue
{
    int arr[];
    ...

What comes to braces, according to Java coding conventions, you should have the opening curly brace on the same line with the token it belongs to; also, you should have one space between the relevant token and the opening brace:

class Dequeue {
    int arr[];
    ...

Naming:

Dequeue is not what you think it is called; it's Deque (double-ended queue). And in a FIFO queue data structure, the operation popping the first element is actually (and conventionally) called dequeue; don't mix the terminology.

What comes to method names, please stick to camel-case. For example,

addRear instead of addrear

Visibility:

Declare your fields (arr, lim, front, rear) private:

class Dequeue {
    private final int arr[];
    private int lim;
    ...

You can make arr final, since you do not reassign to it.

Also, you might consider declaring your class both public and final:

public final class Deque {
    private final int[] arr;
    ...

lim:

You don't need this field, as you can always rely on arr.length.

Algorithm:

Consider removing rear and replace it by a field, say, size. That way you always know the size of your deque, and you don't have to allocate additional array component in order handle the logic gracefully.

Proposal:

After working a bit on your code, I got this implementation. Hope that helps.

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 addLast(int element) {
        checkCapacity();
        arr[(head + size++) % arr.length] = element;
    }

    public void addFirst(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.addLast(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.addFirst(num);
                        System.out.println(deque);
                    } else {
                        System.out.print("Adding " + num + " to back:  ");
                        deque.addLast(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);
                    }
                }
            }
        }
    }
}

Answer 2

Array should be circular

Right now, you use your backing array as a fixed array without the possibility of wrapping around either end. This causes a big problem because you can't use all of the queue without running into one end or the other. For example, you can't even push two entries onto the front:

addfront(1);
addfront(2); // Will print overflow here

You should rethink your whole array usage with a circular array in mind. This means that the front and rear indices should be able to wrap around the ends of the array.