5
\$\begingroup\$

Implement data structure overflow queue. Overflow queue is a normal queue with one extra property. It never throw Stack overflow exception. So whenever queue becomes full, it replaces the oldest element present in the queue and front pointer simply shifted one step ahead. Constraint:- it should have public void enQueue(int n) and public int deQueue() methods of time complexity O(1) The implementation should be optimum and clean.

Here is my version of implementation. You review is highly appreciated.

public class OverflowQueue {
    private int[] queue;
    private int front = -1, rear = -1;

    public OverflowQueue(int size) {
        queue = new int[size];
    }

    public void enQueue(int n){
        rear = getNextIndex(rear);
        queue[rear] = n;
         if (rear == front || front == -1){
          front = getNextIndex(front);
        }

    }

    private int getNextIndex(int index){
        if (index == queue.length - 1 ){
            index = 0;
        } else {
            index ++ ;
        }
        return index;
    }

    public int deQueue(){
        if (front == -1 ){
           throw new NullPointerException("deQueue operation is called on empty queue.");
        }
        int elem = queue[front];
        if (front == rear ){
            front = -1;
            rear = -1;
        } else {
            front = getNextIndex(front);
        }
        return elem;
    }

    public static void main(String[] args) {
        OverflowQueue q = new OverflowQueue(5);
        q.enQueue(1);q.enQueue(2);q.enQueue(3);
        q.enQueue(4);q.enQueue(5);q.enQueue(6);
        System.out.println(q.deQueue());
        System.out.println(q.deQueue());
        System.out.println(q.deQueue());
        System.out.println(q.deQueue());
        System.out.println(q.deQueue());
    }
}
\$\endgroup\$
3
\$\begingroup\$

With this implementation, it would not throw a stackoverflow exception but there could be an unusual behavior. Maybe there could be some better exception message to handle this case.

OverflowQueue q = new OverflowQueue(n);

Now, let's say I want to enqueue n+1 number of elements and then dequeue the same number of elements. Here it doesn't throw any error to enqueue n+1 elements. However deQueue method will throw NullPointerException as soon as the method is executed (n+1)th times.

I would prefer to "resize the array" to avoid Stack overflow exception. There is a possibility of unused space in memory in case of resize array implementation if enqueue and dequeue are executed randomly. This can be handled by sinking the array if required.

\$\endgroup\$
  • \$\begingroup\$ well you can re size array if you want but at a time queue only can contain elements of the size passed in constructors. This is in the problem statement that u should be able to take n+1 element. However throwing exception on n+1 is something I did. What better you suggest then? \$\endgroup\$ – MohdAdnan Sep 29 '13 at 17:49
3
\$\begingroup\$

Your getNextIndex method can be simplified using the ternary operator

private int getNextIndex(int index){
    return index == queue.length - 1 ? 0 : index + 1;
}

Besides this simplification, I agree with Kinjal's answer.

As your index variable is local to only that method, there's no reason to use index++ which will modify the index variable, that's why I'm using index + 1 here instead.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.