Question: solve this java program public class O_QUEUE { //A queue of Objects implemeted as circular queue with exponential //resizing up and down. //Average time of
solve this java program
public class O_QUEUE {
//A queue of Objects implemeted as circular queue with exponential
//resizing up and down.
//Average time of resizing per enqueue/dequeue is O(1).
//instance variables here (there is no class variables)
private QueueNode front; // reference to the front item of the queue
private QueueNode rear; // reference to the rear item of the queue
private int count; //actual number of elements
private int capacity; //maximum number of elements
private int resizeFactor; //resizing factor - must be integer in this variant
private Object[] itemArray; //"circular" array
private int in; //index for next insertion, incremented %capacity
private int out; //index for next deletion, incremented %capacity
//in == out iff count == 0 (queue empty) or count == capacity (queue full)
/** Creates a new instance of PriorityQueue */
public O_QUEUE()
//Empty queue with initial capacity 10, resizing factor 2
{
count=0; //empty
capacity=10; //initial capacity
resizeFactor=2; //must be integer >= 2 in this variant
itemArray=new Object[capacity];
out = 0; //cound be any index
in = 0; //because out == 0 here
}
public void insertRear(Object newItem)
//Inserts new element at the "end" of this queue
{
System.out.println("adding at rear: "+ newItem);
QueueNode nd = new QueueNode();
nd.setValue(newItem);
nd.setPrev(rear);
if(rear != null) rear.setNext(nd);
if(rear == null) front = nd;
rear = nd;
if(count==capacity) //no more space, "resize" the array up
//in == out
{
int newcapacity=capacity*resizeFactor;
Object[] tempArray = new Object[newcapacity];
if (out == 0) //in == out == 0; this queue is in one piece
{
//copy this queue in one piece
for (int i = 0; i < capacity; i++)
{
tempArray[i] = itemArray[i];
in = count; //because out == 0 here
}
}
else //in == out != 0; this queue is split onto 2 pieces
{
//copy the "left" part of this queue
for (int i = 0; i < in; i++)
{
tempArray[i] = itemArray[i];
}
//copy the "right" part of this queue
for (int i = out; i < capacity; i++)
{
tempArray[i + newcapacity - capacity] = itemArray[i];
}
//out needs to be "moved" to the right by the size of the strech
out += newcapacity - capacity;
}
capacity = newcapacity; //sterch done
itemArray = tempArray; //updaing reference
}
//at this point there is room for insertion
itemArray[in] = newItem;
in = (in + 1)%capacity; //% because array is "circular"
count++; //insertion complete
}
public void insertFront(Object newItem)
//Inserts new element at the "front" of this queue
{
System.out.println("adding at front: "+ newItem);
QueueNode nd = new QueueNode();
nd.setValue(newItem);
nd.setNext(front);
if(front != null) front.setPrev(nd);
if(front == null) rear = nd;
front = nd;
if(count==capacity) //no more space, "resize" the array up
//in == out
{
int newcapacity=capacity*resizeFactor;
Object[] tempArray = new Object[newcapacity];
if (out == 0) //in == out == 0; this queue is in one piece
{
//copy this queue in one piece
for (int i = 0; i < capacity; i++)
{
tempArray[i] = itemArray[i];
in = count; //because out == 0 here
}
}
else //in == out != 0; this queue is split onto 2 pieces
{
//copy the "left" part of this queue
for (int i = 0; i < in; i++)
{
tempArray[i] = itemArray[i];
}
//copy the "right" part of this queue
for (int i = out; i < capacity; i++)
{
tempArray[i + newcapacity - capacity] = itemArray[i];
}
//out needs to be "moved" to the right by the size of the strech
out += newcapacity - capacity;
}
capacity = newcapacity; //sterch done
itemArray = tempArray; //updaing reference
}
//at this point there is room for insertion
itemArray[in] = newItem;
in = (in + 1)%capacity; //% because array is "circular"
count++; //insertion complete
}
public Object removeFront()
{
Object itemToReturn;
if (count==0) return null; //this queue was empty
count--; //will remove one element
itemToReturn=itemArray[out];
if(front == null){
System.out.println("Deque underflow!! unable to remove.");
return front;
}
//remove an item from the beginning of the queue
QueueNode tmpFront = front.getNext();
if(tmpFront != null) tmpFront.setPrev(null);
if(tmpFront == null) rear = null;
System.out.println("removed from front: " + front.getValue());
front = tmpFront;
if (count != 0)
{
out = (out + 1) % capacity; //because array is "circular"
}
else //this queue is empty here
{
in = 0;
out = 0;
}
if ((count <= capacity / (resizeFactor*resizeFactor)) &&
//resFact squared to avoid instability of resizing
(10 <= capacity / (resizeFactor*resizeFactor)))
//space wasted, "resize" the array down
//count != 0 here because it was conunt = capacity
//before this dequeue()
//So, in != out
{
int newcapacity = capacity / resizeFactor;
Object[] tempArray = new Object[newcapacity];
if (in < out) //this queue is split on two parts
{
//copying the "left" part
for (int i = 0; i < in; i++)
{
tempArray[i] = itemArray[i];
}
//copying the "right" part"
for (int i = out; i < capacity; i++)
{
tempArray[i - capacity + newcapacity] = itemArray[i];
}
out -= capacity - newcapacity; //out was moved to the left
}
else if (out < in) //this que is in one piece
{
//copy to the begining of the array
for (int i = out; i < in; i++)
{
tempArray[i - out] = itemArray[i];
}
out = 0;
in = count; //since out == 0 but count < capacity here
} //in == out can't happen because that would mean
//that queue before shrinking was either full or empty
itemArray = tempArray; //updating reference
capacity = newcapacity; //shrinking done
}
return itemToReturn;
}
public Object removeRear()
{
Object itemToReturn;
if (count==0) return null; //this queue was empty
count--; //will remove one element
itemToReturn=itemArray[out];
if(rear == null){
System.out.println("Deque underflow!! unable to remove.");
return rear;
}
//remove an item from the beginning of the queue
QueueNode tmpRear = rear.getPrev();
if(tmpRear != null) tmpRear.setNext(null);
if(tmpRear == null) front = null;
System.out.println("removed from rear: " + rear.getValue());
rear = tmpRear;
if (count != 0)
{
out = (out + 1) % capacity; //because array is "circular"
}
else //this queue is empty here
{
in = 0;
out = 0;
}
if ((count <= capacity / (resizeFactor*resizeFactor)) &&
//resFact squared to avoid instability of resizing
(10 <= capacity / (resizeFactor*resizeFactor)))
//space wasted, "resize" the array down
//count != 0 here because it was conunt = capacity
//before this dequeue()
//So, in != out
{
int newcapacity = capacity / resizeFactor;
Object[] tempArray = new Object[newcapacity];
if (in < out) //this queue is split on two parts
{
//copying the "left" part
for (int i = 0; i < in; i++)
{
tempArray[i] = itemArray[i];
}
//copying the "right" part"
for (int i = out; i < capacity; i++)
{
tempArray[i - capacity + newcapacity] = itemArray[i];
}
out -= capacity - newcapacity; //out was moved to the left
}
else if (out < in) //this que is in one piece
{
//copy to the begining of the array
for (int i = out; i < in; i++)
{
tempArray[i - out] = itemArray[i];
}
out = 0;
in = count; //since out == 0 but count < capacity here
} //in == out can't happen because that would mean
//that queue before shrinking was either full or empty
itemArray = tempArray; //updating reference
capacity = newcapacity; //shrinking done
}
return itemToReturn;
}
public int size()
//returns the actual number of elements in this queue
{
return count;
}
public boolean isEmpty()
//returns true is this queue is empty, returns false otherwise
{
return count==0;
}
public int Length()
//returns the size ot the array that implements this queue
{
return itemArray.length;
}
}
class QueueNode{
private QueueNode prev;
private QueueNode next;
private T value;
public QueueNode getPrev() {
return prev;
}
public void setPrev(QueueNode prev) {
this.prev = prev;
}
public QueueNode getNext() {
return next;
}
public void setNext(QueueNode next) {
this.next = next;
}
public T getValue() {
return value;
}
public void setValue(T value) {
this.value = value;
}
}
modify my Java code below to implement a Doubly-Linked Queue. I renamed my enqueue() and dequeue() methods to insertRear() and insertFront() to insert elements to the front and back of the queue, as well as, removeRear() and removeFront() to remove an element from both sides of the queue. I'm not sure if I did my methods right. Please help with any suggestions to make my queue class a Doubly-Linked Queue class.
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help