Question

The class pictured below is designed to implement an integer queue using two stacks. Assume the stack methods all work as desired (though their implementations are not shown).

.(a) Trace what happens in the following situation, showing intermediate steps (values of variables, what is in the stacks, and what is in the queue at various points in the methods, not just the results of the methods).

• Start with an empty queue. Enqueue 5, then 16, then 7. Dequeue twice. Enqueue 3. Dequeue once. .(b) Much of the code is uncommented. Add comments to explain the key steps in these methods.

.(c) Explain in your own words/images why this dequeue() method works.

(d) What situations are not considered in the methods written here that should be?

Screen Shot 2020-10-02 at 1... Open with Preview class myQueue { //implementing a queue using two stacks private MyStack stack1; private MyStack stack2; // constructor for the class public myQueue (int max) { // set the max size of the two stacks stack1 = new MyStack(max); stack2 = new MyStack(max); } public void enqueue(int val) { stack1.push(val); } public int dequeue() { if (stack2.isEmpty()) { while (!stack1.isEmpty()) { int moveVal = stack1.pop(); stack2.push(moveVal); } } return stack2.pop(); } }

Answer 1

• Part a:
  1. Enqueue 5 : It will push element in stack1. Now stack1 will have [ 5 ] and top of stack will point to 5
  2. Enqueue 16 : It will push element in stack1. Now stack1 will have [ 5, 17] and top of stack will point to 17
  3. Enqueue 7 : It will push element in stack1. Now stack1 will have [ 5, 17, 7 ] and top of stack will point to 7.
  4. Dequeue : As stack2 is empty so dequeue function will pop out all the elements of stack1 and will push them in stack2. Now stack2 will have [ 7, 17, 5 ] and top of stack will point to 5 and stack1 will be empty.After pushing all the elemts in stack2 the function will return stack.pop () means the element that top pointer points to i.e. 5 in this case and now stack2 will have [ 7, 17 ] and top of stack will point to 17.
  5. Dequeue : As stack2 is not empty so function will return stack.pop () means the element that top pointer points to i.e. 17 in this case and now stack2 will have [ 7 ] and top of stack will point to 7.
  6. Enqueue 3 :It will pust element in stack1. Now stack1 will have [ 3 ] and top of stack will point to 3.
  
  After all of the above operations :
  stack1 will have [ 3 ] and top of stack will point to 3 and stack2 will have [ 7 ] and top of stack will point to 7.

  Part b:
  class myQueue {
  private MyStack stack1;
  private MyStack stack2;
  
  public MyQueue(int max) { // Constructor that will initialize both stack with size as max
  stack1=new MyStack(max);
  stack2=new MyStack(max);
  }

  public void enqueue (int val) { // Whenever we want to perform enqueue operation in queue it will puch that element in stack1
  stack1.push(val);
  }
  
  public int dequeue ( ) {
  if (stack2.isEmpty() ) { // If stack2 is empty then it will push all the elements of stack1 in stack2 so that element comes in the order in which they should be pop out from queue ( i.e. reverse of stack order i.e. reverse of LIFO i.e. in FIFO order) But if the stack2 was not empty then it will directly pop out top element of stack2 without pushing element of stack 1 into stack2.
  while (! stack1.isEmpty() ) { // pushing elements of stack1 into stack2
  int moveval=stack1.pop();
  stack2.push(moveval);
  }
  }
  return stack2.pop (); //it will return the top element of stack2 i.e. first element of queue.
  }
  }
  
  Part c :
  This method will work because when the stack2 is empty then we are pushing all elements of stack1 into stack2. This means the element in stack2 will come in reverse order of elements that they were in stack1.(i.e. reverse of LIFO as elements in stack1 were in LIFO order so reverse of LIFO is FIFO this is what we wants in queue). Now whenever the dequeue operation will be there then we will pop out element from stack2. But when stack2 agains become empty then we will again push all the elements of stack1 into stack2 and will perform the same procedure.
  So, by doing so we are popping out element from stack2 as we do from queue.
  
  Part d:   
  If we will perform dequeue operation without performing any enqueue operation then in that case above code will give ur some error.
  public int dequeue ( ) {
  if (stack2.isEmpty() ) { //As stack2 is empty so it will go in while loop
  while (! stack1.isEmpty() ) { //As stack1 is also empty so it will come out of while loop
  int moveval=stack1.pop();
  stack2.push(moveval);
  }
  }
  return stack2.pop (); //As stack2 is empty but it is performing stack2.pop() so it will give us error.
  }
  }

  So in order to handle it before doing stack2.pop() we can check whether stack2 is empty or not and then can perform operation accordingly.