I was stuck up in this problem and am unable to actually
start it. If anyone could help me and solve this problem, i would be
grateful.
Please reply with the code as soon as possible.
THE PROBLEM.
A Queue class built upon an array in circular fashion with overflow
and underflow exceptions.
A way of bending is to use the integer % operator to bend the array
so that its two ends meet. We can do this by incrementing the array
index thus:
i=(i+1)%a.length;
where a is an array and i is being used as an index into that array.
Example: suppose that a.length = 4. Consider the following table:
i i+1 (i+1)%4
--------------------------
0 1 1
1 2 2
2 3 3
3 4 0
4 5 1
5 6 2
6 7 3
7 8 0
8 9 1
So the result of assigning (i+1)%a.length would be an index
that "wraps around" to the beginning of the array once it reaches the
higher order end of the array. In the above example, the index
3 "increments" to the index 0.
It is easy to implement a queue with this idea using a front and rear
index. To insert, write the item into the array element whose index
is rear and then "increment" rear. To remove, return the value of the
array element whose index is front and "increment" front. The queue
is empty when front==rear. The queue is full when all the cells
contain data that has been enqueued.
In this problem, you are to write a circular integer Queue class
which is based on an the integer array as its principal state-holding
element.
Name your class CirQueue.java.
enqueue integers at the rear of the queue and dequeue integers from
the front of the queue.
Include the following (non-static) constructors and methods in your
class:
1) public CirQueue(int length); // size sets the length of the
underlying array. The queue size is initialized to zero.
2) public CirQueue(); //the default constructor --sets the length of
the underlying array to 5. The queue size is initialized to zero.
3) public boolean full(); // true if the queue occupies the whole
array, false otherwise.
4) public boolean empty(); // true if the queue is empty, false
otherwise.
5) public void enqueue(int x) throws OverflowException; // if the
queue is full, it throws an OverflowEception, otherwise it inserts x
at the rear of the queue.
6) public int dequeue() throws UnderflowException; // if it is empty,
it throws an UnderflowEception, otherwise it removes the element at
the front of the queue and returns its value.
7) public String toString(); // returns the state of the queue in
this exact form: f>0,1,2,3,4<r where the ints 1,2,3,4 have been
enqueued in that order. The letter f indicated the front of the
queue, the letter r indicates its rear. The empty queue must be
represented as f><r. (To get experience with recursion, you could
make this a recursive method -- but that is NOT a requirement).
8) public int size(); // returns the number of elements currently in
the queue.
Write in only your CirQueue.java file. The Underflow and Overflow
exception classes for testing will be provided. You will, of course,
have to create these 2 exceptions in order for you to be able to
compile, run and test your design. (In case you have read ahead and
are tempted to do so -- do NOT include the exceptions as inner
classes).
Each of the methods should be tested separately under full, empty and
non-full and non-empty states. You should test your queue with the
following class which should give the indicated output:
public class UseCirQueue{
public static void main(String[] args){
CirQueue q = new CirQueue();
try{
for(int i = 0; i< 5;i++){
q.enqueue(i);
System.out.println(q+" size = "+q.size());
}//for
}//try
catch(OverflowException e){System.out.println(e);}
try{
while(!q.empty()){
System.out.println("dequeue = "+ q.dequeue());
System.out.println(q+" size = "+q.size());
}//while
}//try
catch(UnderflowException e){System.out.println(e);}
try{
for(int i = 0; i< 25;i++){
q.enqueue(i);
System.out.print(q +"--");
System.out.println(q.dequeue());
}//for
}//try
catch(OverflowException e){System.out.println(e);}
catch(UnderflowException e){System.out.println(e);}
}//main()
}//UseCirQueue
/*
OUTPUT:
f>0<r size = 1
f>0,1<r size = 2
f>0,1,2<r size = 3
f>0,1,2,3<r size = 4
f>0,1,2,3,4<r size = 5
dequeue = 0
f>1,2,3,4<r size = 4
dequeue = 1
f>2,3,4<r size = 3
dequeue = 2
f>3,4<r size = 2
dequeue = 3
f>4<r size = 1
dequeue = 4
f><r size = 0
f>0<r--0
f>1<r--1
f>2<r--2
f>3<r--3
f>4<r--4
f>5<r--5
f>6<r--6
f>7<r--7
f>8<r--8
f>9<r--9
f>10<r--10
f>11<r--11
f>12<r--12
f>13<r--13
f>14<r--14
f>15<r--15
f>16<r--16
f>17<r--17
f>18<r--18
f>19<r--19
f>20<r--20
f>21<r--21
f>22<r--22
f>23<r--23
f>24<r--24
*/
A suggested development procedure (do not write and execute the whole
class at once): follow the same procedure that we suggested for the
Queue class.
You may find it easier to include a variable that keeps track of the
size of the queue rather than calculating the size.
Finally test your class with the given UseCirQueue class.