Question

Use the TestCorrectness.java/TestCorrectness.cpp to compile, fix, and run your code. QueueUsingStack.java is also provided, but you will need to complete some codes.

public class TestCorrectness {

   public static void main(String[] args) throws Exception {
       int queueSize = 7;
       QueueUsingStack qViaStack = new QueueUsingStack(queueSize);
       Queue queue = new Queue(queueSize);
       System.out.println("**** Enqueue Test ****");
       System.out.println();
       for (int i = 1; i <= 4; i++) {
           int x = i * 5;
           qViaStack.enqueue(x);
           queue.enqueue(x);
           System.out.println("Enqueue " + x);
           System.out.println("Stack implementation: " + qViaStack.toString());
           System.out.println("Standard implementation: " + queue.toString());
           System.out.println();
       }
       System.out.println("**** Dequeue Test ****");
       System.out.println();
       for (int i = 1; i <= 2; i++) {
           System.out.println("Stack implementation: (Dequeued " + qViaStack.dequeue() + ") " + qViaStack.toString());
           System.out.println("Standard implementation: (Dequeued " + queue.dequeue() + ") " + queue.toString());
           System.out.println();
       }
       System.out.println("**** Enqueue Test ****");
       System.out.println();
       for (int i = 1; i <= 5; i++) {
           int x = i * 7;
           qViaStack.enqueue(x);
           queue.enqueue(x);
           System.out.println("Enqueue " + x);
           System.out.println("Stack implementation: " + qViaStack.toString());
           System.out.println("Standard implementation: " + queue.toString());
           System.out.println();
       }
       System.out.println("**** Dequeue Test ****");
       System.out.println();
       for (int i = 1; i <= 7; i++) {
           System.out.println("Stack implementation: (Dequeued " + qViaStack.dequeue() + ") " + qViaStack.toString());
           System.out.println("Standard implementation: (Dequeued " + queue.dequeue() + ") " + queue.toString());
           System.out.println();
       }
   }
}

public class QueueUsingStack {
  
Stack mainStack;
int maxQueueSize;
  
public QueueUsingStack(int maxQueueSize) {
this.maxQueueSize = maxQueueSize;
mainStack = new Stack(maxQueueSize);
}
  
public void enqueue(int val) { // complete this function
}
  
public int dequeue() { // complete this function
}
  
public int getSize() { // complete this function
}
  
public String toString() {
if (getSize() == 0) {
return "[]";
} else {
String output = "[";
int n = getSize();
for (int i = 0; i < n - 1; i++) {
int x = dequeue();
output += x + ", ";
enqueue(x);
}
int x = dequeue();
output += x + "]";
enqueue(x);
return output;
}
}
}

You should get the following output.
**** Enqueue Test ****
Enqueue 5
Stack implementation: [5]
Standard implementation: [5]
Enqueue 10
Stack implementation: [5, 10]
Standard implementation: [5, 10]
Enqueue 15
Stack implementation: [5, 10, 15]
Standard implementation: [5, 10, 15]
Enqueue 20
Stack implementation: [5, 10, 15, 20]
Standard implementation: [5, 10, 15, 20]
**** Dequeue Test ****
Stack implementation: (Dequeued 5) [10, 15, 20]
Standard implementation: (Dequeued 5) [10, 15, 20]
Stack implementation: (Dequeued 10) [15, 20]
Standard implementation: (Dequeued 10) [15, 20]
**** Enqueue Test ****
Enqueue 7
Stack implementation: [15, 20, 7]
Standard implementation: [15, 20, 7]
Enqueue 14
Stack implementation: [15, 20, 7, 14]
Standard implementation: [15, 20, 7, 14]
Enqueue 21
Stack implementation: [15, 20, 7, 14, 21]
Standard implementation: [15, 20, 7, 14, 21]
Enqueue 28
Stack implementation: [15, 20, 7, 14, 21, 28]
Standard implementation: [15, 20, 7, 14, 21, 28]
2
Enqueue 35
Stack implementation: [15, 20, 7, 14, 21, 28, 35]
Standard implementation: [15, 20, 7, 14, 21, 28, 35]
**** Dequeue Test ****
Stack implementation: (Dequeued 15) [20, 7, 14, 21, 28, 35]
Standard implementation: (Dequeued 15) [20, 7, 14, 21, 28, 35]
Stack implementation: (Dequeued 20) [7, 14, 21, 28, 35]
Standard implementation: (Dequeued 20) [7, 14, 21, 28, 35]
Stack implementation: (Dequeued 7) [14, 21, 28, 35]
Standard implementation: (Dequeued 7) [14, 21, 28, 35]
Stack implementation: (Dequeued 14) [21, 28, 35]
Standard implementation: (Dequeued 14) [21, 28, 35]
Stack implementation: (Dequeued 21) [28, 35]
Standard implementation: (Dequeued 21) [28, 35]
Stack implementation: (Dequeued 28) [35]
Standard implementation: (Dequeued 28) [35]
Stack implementation: (Dequeued 35) []
Standard implementation: (Dequeued 35) []

Answer 1

//------------- TestCorrectness.java -------------
//there are some modifications in your code
//Since Queue is abstract class you can't instantiate it.
//so initialize queue with type LinkedList
//there are no enqueue and dequeue functions , add and remove are replaced them.
//and finally output is same for two implementations.
import java.util.*;
public class TestCorrectness
{
public static void main(String[] args) throws Exception
{
int queueSize = 7;
QueueUsingStack qViaStack = new QueueUsingStack(queueSize);
Queue queue = new LinkedList();
System.out.println("**** Enqueue Test ****");
System.out.println();
for (int i = 1; i <= 4; i++) {
int x = i * 5;
qViaStack.enqueue(x);
queue.add(x);
System.out.println("Enqueue " + x);
System.out.println("Stack implementation: " + qViaStack.toString());
System.out.println("Standard implementation: " + queue.toString());
System.out.println();
}
System.out.println("**** Dequeue Test ****");
System.out.println();
for (int i = 1; i <= 2; i++) {
System.out.println("Stack implementation: (Dequeued " + qViaStack.dequeue() + ") " + qViaStack.toString());
System.out.println("Standard implementation: (Dequeued " + queue.remove() + ") " + queue.toString());
System.out.println();
}
System.out.println("**** Enqueue Test ****");
System.out.println();
for (int i = 1; i <= 5; i++) {
int x = i * 7;
qViaStack.enqueue(x);
queue.add(x);
System.out.println("Enqueue " + x);
System.out.println("Stack implementation: " + qViaStack.toString());
System.out.println("Standard implementation: " + queue.toString());
System.out.println();
}
System.out.println("**** Dequeue Test ****");
System.out.println();
for (int i = 1; i <= 7; i++) {
System.out.println("Stack implementation: (Dequeued " + qViaStack.dequeue() + ") " + qViaStack.toString());
System.out.println("Standard implementation: (Dequeued " + queue.remove() + ") " + queue.toString());
System.out.println();
}
}
}

import java.util.*;
public class QueueUsingStack
{
  
   Stack mainStack;
   int maxQueueSize;
  
   public QueueUsingStack(int maxQueueSize) {
       this.maxQueueSize = maxQueueSize;
       //there is no constructor for Stack that takes size
       //controlling elements insertion more than the specified size
       //is taken care of enqueue method.
       mainStack = new Stack();
   }
   //enqueue(val) method
   public void enqueue(int val)
   {
       //get size of the queue
       //if there is space in queue insert.
       if(getSize()< maxQueueSize)
       {
           //first pop each value in main stack into temperory stack.
           Stack temp = new Stack();
           while(!mainStack.isEmpty())
           {
               temp.push(mainStack.pop());
           }
           //after mainStack is empty push the val passed.
           mainStack.push(val);
           //now push all the values in temp Stack to the mainStack.
           while(!temp.isEmpty())
           {
               mainStack.push(temp.pop());
           }
       }
      
   }
  
   public int dequeue()
   {
       //if mainStack is empty return 0;
       if(mainStack.isEmpty())
       {
           return 0;
       }
       //get the top value from mainStack
       int val = (int)mainStack.peek();
       //pop the value.
       mainStack.pop();
       return val;
   }
  
   public int getSize()
   {
       //use clone() method to copy values in mainStack to temp Stack
       Stack temp = (Stack)mainStack.clone();
       //count the values in temp stack by poopping each element
       int count = 0;
       while(!temp.isEmpty())
       {
           temp.pop();
           count++;
       }
       return count;
   }
  
   public String toString()
   {
       if (getSize() == 0)
       {
           return "[]";
       }
       else
       {
           String output = "[";
           int n = getSize();
           for (int i = 0; i < n - 1; i++)
           {
               int x = dequeue();
               output += x + ", ";
               enqueue(x);
           }
           int x = dequeue();
           output += x + "]";
           enqueue(x);
           return output;
       }
   }
}
/*

------------ OUTPUT ----------------

**** Enqueue Test ****

Enqueue 5
Stack implementation: [5]
Standard implementation: [5]

Enqueue 10
Stack implementation: [5, 10]
Standard implementation: [5, 10]

Enqueue 15
Stack implementation: [5, 10, 15]
Standard implementation: [5, 10, 15]

Enqueue 20
Stack implementation: [5, 10, 15, 20]
Standard implementation: [5, 10, 15, 20]

**** Dequeue Test ****

Stack implementation: (Dequeued 5) [10, 15, 20]
Standard implementation: (Dequeued 5) [10, 15, 20]

Stack implementation: (Dequeued 10) [15, 20]
Standard implementation: (Dequeued 10) [15, 20]

**** Enqueue Test ****

Enqueue 7
Stack implementation: [15, 20, 7]
Standard implementation: [15, 20, 7]

Enqueue 14
Stack implementation: [15, 20, 7, 14]
Standard implementation: [15, 20, 7, 14]

Enqueue 21
Stack implementation: [15, 20, 7, 14, 21]
Standard implementation: [15, 20, 7, 14, 21]

Enqueue 28
Stack implementation: [15, 20, 7, 14, 21, 28]
Standard implementation: [15, 20, 7, 14, 21, 28]

Enqueue 35
Stack implementation: [15, 20, 7, 14, 21, 28, 35]
Standard implementation: [15, 20, 7, 14, 21, 28, 35]

**** Dequeue Test ****

Stack implementation: (Dequeued 15) [20, 7, 14, 21, 28, 35]
Standard implementation: (Dequeued 15) [20, 7, 14, 21, 28, 35]

Stack implementation: (Dequeued 20) [7, 14, 21, 28, 35]
Standard implementation: (Dequeued 20) [7, 14, 21, 28, 35]

Stack implementation: (Dequeued 7) [14, 21, 28, 35]
Standard implementation: (Dequeued 7) [14, 21, 28, 35]

Stack implementation: (Dequeued 14) [21, 28, 35]
Standard implementation: (Dequeued 14) [21, 28, 35]

Stack implementation: (Dequeued 21) [28, 35]
Standard implementation: (Dequeued 21) [28, 35]

Stack implementation: (Dequeued 28) [35]
Standard implementation: (Dequeued 28) [35]

Stack implementation: (Dequeued 35) []
Standard implementation: (Dequeued 35) []

------------------
(program exited with code: 0)

Press any key to continue . . .

*/