Implement data structure overflow queue

Question 1

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());    }}

Question 2

SeeEvictingQueue.

Question 3

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. HoweverdeQueue 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.

Question 4

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?

Question 5

YourgetNextIndex method can be simplified using theternary operator

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

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

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

Kinjal 1,1082 gold badges11 silver badges23 bronze badges · Answer 1 · 2013-09-29 17:40:21Z

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. HoweverdeQueue 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.

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?

Simon Forsberg 59.7k9 gold badges160 silver badges312 bronze badges · Answer 2 · 2014-05-22 12:48:43Z

YourgetNextIndex method can be simplified using theternary operator

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

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

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

Movatterモバイル変換

Stack Exchange Network

Implement data structure overflow queue

2 Answers2

You mustlog in to answer this question.

Related

Hot Network Questions

Subscribe to RSS