Question

Use the TestTime.java/TestTime.cpp le to compare the two queue implementations. Note that enqueue function when implemented using an array has O(1) complexity, and when using two arrays has O(n) complexity, where n is the current size of the queue. So, the two stack implementation should take more time, which is substantiated by the experiment (time output).

public class TestTime {

   public static void main(String[] args) throws Exception {
       for (int maxSize = 10000; maxSize <= 50000; maxSize += 10000) {

           QueueUsingStack qViaStack = new QueueUsingStack(maxSize);
           long startTime = System.currentTimeMillis();
           for (int i = 0; i < maxSize; i++) {
               qViaStack.enqueue(i);
           }
           for (int i = 0; i < maxSize; i++) {
               qViaStack.dequeue();
           }
           long endTime = System.currentTimeMillis();
           System.out.printf("Time taken for %d enqueue/dequeue operations, when using a stack implementation: %d\n",
                   2 * maxSize, (endTime - startTime));
       }
       System.out.println();

       for (int maxSize = 1000000; maxSize <= 5000000; maxSize += 1000000) {

           Queue queue = new Queue(maxSize);
           long startTime = System.currentTimeMillis();
           for (int i = 0; i < maxSize; i++) {
               queue.enqueue(i);
           }
           for (int i = 0; i < maxSize; i++) {
               queue.dequeue();
           }
           long endTime = System.currentTimeMillis();
           System.out.printf("Time taken for %d enqueue/dequeue operations, when using an array implementation: %d\n",
                   2 * maxSize, (endTime - startTime));
       }
   }
}

YOU SHOULD GET THE FOLLOWING OUTPUTS:

Time taken for 20000 enqueue/dequeue operations, when using a stack implementation: 221
Time taken for 40000 enqueue/dequeue operations, when using a stack implementation: 690
Time taken for 60000 enqueue/dequeue operations, when using a stack implementation: 1160
Time taken for 80000 enqueue/dequeue operations, when using a stack implementation: 1845
Time taken for 100000 enqueue/dequeue operations, when using a stack implementation: 2881
Time taken for 2000000 enqueue/dequeue operations, when using an array implementation: 11
Time taken for 4000000 enqueue/dequeue operations, when using an array implementation: 20
Time taken for 6000000 enqueue/dequeue operations, when using an array implementation: 12
Time taken for 8000000 enqueue/dequeue operations, when using an array implementation: 13
Time taken for 10000000 enqueue/dequeue operations, when using an array implementation: 16

Answer 1

// Queue.java : Java program to implement queue using a single array

public class Queue {

      

       private int front;

       private int rear;

       private int queue[];

      

       // create an empty queue of maximum size maxSize

       public Queue(int maxSize)

       {

             queue = new int[maxSize];

             rear = -1;

             front = -1;

       }

      

       // method to insert an element at the end of the queue

       public void enqueue(int val)

       {

             // check if queue is not full, then insert the element at the end of the queue

             if(rear < (queue.length-1))

             {

                    rear++; // increment rear

                    queue[rear] = val; // insert val as last element of queue

                    // if queue was empty set front to rear

                    if(front == -1)

                           front = rear;

             }

       }

      

       // method to delete the front element from queue

       public void dequeue()

       {

             if(front <= rear) // check if queue is not empty

             {

                   

                    front++; // increment front

                    // if queue is empty, set front and rear to -1

                    if(front > rear)

                    {

                           front = -1;

                           rear = -1;

                    }

                   

              }

            

       }

      

}

//end of Queue.java

// QueueUsingStack.java : Java program to implement Queue operations using 2 stacks(arrays)

public class QueueUsingStack {

       private int top;

       private int stack1[];

       private int stack2[];

       // create an empty stack of maximum size maxSize

       public QueueUsingStack(int maxSize)

       {

             stack1= new int[maxSize];

             top = -1;

       }

      

       // method to insert an element at the end of queue

       public void enqueue(int val)

       {

             if(top < (stack1.length-1)) // check if stack is not full, insert the element as the top element

             {

                    top++; // increment the top

                    stack1[top] = val; // insert the element

                    //System.out.println("Top = "+top);

             }

       }

      

       // method to delete the front element from queue

       public void dequeue()

       {

             if(top != -1) // if stack is not empty

             {

                    // create stack2 of size top+1

                    stack2 = new int[top+1];

                    // insert elements from top to end from stack 1 to stack 2

                    for(int i=top,j=0;i>=0;i--,j++)

                    {

                           stack2[j] = stack1[i];

                    }

                   

                    top--; // remove the front element

                   

                    // insert the elements back from stack2 to stack2 , removing the front element

                    for(int i=top,j=0;i>=0;i--,j++)

                    {

                           stack1[j] = stack2[i];

                    }

                   

             }

            

       }

      

}

//end of QueueUsingStack.java

//TestTime.java

public class TestTime {

      

       public static void main(String[] args) throws Exception {

              for (int maxSize = 10000; maxSize <= 50000; maxSize += 10000) {

                  QueueUsingStack qViaStack = new QueueUsingStack(maxSize);

                  long startTime = System.currentTimeMillis();

                  for (int i = 0; i < maxSize; i++) {

                      qViaStack.enqueue(i);

                  }

                  for (int i = 0; i < maxSize; i++) {

                      qViaStack.dequeue();

                  }

                  long endTime = System.currentTimeMillis();

                  System.out.printf("Time taken for %d enqueue/dequeue operations, when using a stack implementation: %d\n",

                          2 * maxSize, (endTime - startTime));

              }

              System.out.println();

              for (int maxSize = 1000000; maxSize <= 5000000; maxSize += 1000000) {

                  Queue queue = new Queue(maxSize);

                  long startTime = System.currentTimeMillis();

                  for (int i = 0; i < maxSize; i++) {

                      queue.enqueue(i);

                  }

                  for (int i = 0; i < maxSize; i++) {

                      queue.dequeue();

                  }

                  long endTime = System.currentTimeMillis();

                  System.out.printf("Time taken for %d enqueue/dequeue operations, when using an array implementation: %d\n",

                          2 * maxSize, (endTime - startTime));

              }

          }

}

//end of TestTime.java

Output: