solve this java program public class O_QUEUE { //A queue of Objects implemeted a
ID: 3858145 • Letter: S
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 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.
Explanation / Answer
message:
Your given code is combined with both the linked and the array implementations of the circularly doubled ended queue.
I have removed the part of the array implementation of the circularly doubled ended queue.
I modified the remaining code as the error free program.
I included toString() method in the O_QUEUE.java program to return a string representation of the items in the queue.
I also provide a Sample Output and a test program named Test_O_QUEUE.java to test you program named O_QUEUE.java.
Now, this code represents a generic type of the circularly double ended queue.
Sample Output:
adding at rear: 40
adding at rear: 50
adding at rear: 60
adding at front: 30
adding at front: 20
adding at front: 10
The deque is empty.(T/F): false
The size of the deque: 6
The elements in the deque are: 10 20 30 40 50 60
removed from rear: 60
The removed element at the rear: 60
removed from front: 10
The removed element at the front: 10
The current elements in the deque are: 20 30 40 50
File: O_QUEUE.java
public class O_QUEUE<T>
{
private QueueNode<T> front;
private QueueNode<T> rear;
private int count;
public O_QUEUE()
{
front = null;
rear = null;
count = 0;
}
public void insertRear(T newItem)
{
System.out.println("adding at rear: " + newItem);
QueueNode<T> nd = new QueueNode<T>();
nd.setValue(newItem);
nd.setPrev(rear);
if(rear != null)
rear.setNext(nd);
if(rear == null)
front = nd;
rear = nd;
count++;
}
public void insertFront(T newItem)
{
System.out.println("adding at front: " + newItem);
QueueNode<T> nd = new QueueNode<T>();
nd.setValue(newItem);
nd.setNext(front);
if(front != null)
front.setPrev(nd);
if(front == null)
rear = nd;
front = nd;
count++;
}
public T removeFront()
{
T itemToReturn;
if(count == 0)
return null;
itemToReturn = front.getValue();
QueueNode<T> tmpFront = front.getNext();
if(tmpFront != null)
tmpFront.setPrev(null);
if(tmpFront == null)
rear = null;
System.out.println("removed from front: " + itemToReturn);
front = tmpFront;
count--;
return itemToReturn;
}
public T removeRear()
{
T itemToReturn;
if(count == 0)
return null;
itemToReturn = rear.getValue();
QueueNode<T> tmpRear = rear.getPrev();
if(tmpRear != null)
tmpRear.setNext(null);
if(tmpRear == null)
front = null;
System.out.println("removed from rear: " + itemToReturn);
rear = tmpRear;
count--;
return itemToReturn;
}
public int size()
{
return count;
}
public boolean isEmpty()
{
return count == 0;
}
public String toString()
{
String queueElements = "";
QueueNode<T> curr = front;
while(curr != null)
{
queueElements = queueElements + (curr.getValue()) + " ";
curr = curr.getNext();
}
return queueElements;
}
}
class QueueNode<T>
{
private QueueNode<T> prev;
private QueueNode<T> next;
private T value;
public QueueNode<T> getPrev()
{
return prev;
}
public void setPrev(QueueNode<T> prev)
{
this.prev = prev;
}
public QueueNode<T> getNext()
{
return next;
}
public void setNext(QueueNode<T> next)
{
this.next = next;
}
public T getValue()
{
return value;
}
public void setValue(T value)
{
this.value = value;
}
}
File: Test_O_QUEUE.java
public class Test_O_QUEUE
{
public static void main(String[] args)
{
O_QUEUE<Integer> oq = new O_QUEUE<Integer>();
oq.insertRear(40);
oq.insertRear(50);
oq.insertRear(60);
oq.insertFront(30);
oq.insertFront(20);
oq.insertFront(10);
System.out.println();
System.out.println("The deque is empty.(T/F): " + oq.isEmpty());
System.out.println("The size of the deque: " + oq.size());
System.out.println("The elements in the deque are: " + oq.toString());
System.out.println();
System.out.println("The removed element at the rear: " + oq.removeRear());
System.out.println();
System.out.println("The removed element at the front: " + oq.removeFront());
System.out.println();
System.out.println("The current elements in the deque are: " + oq);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.