How can you implement a Queue using two stacks?

Let s1 and s2 be the two Stacks to be used in the implementation of the Queue. All we have to so is to define the enQueue and deQueue operations for the Queue. The enQueue algorithm is very simple, Just push the value on stack s1. The time complexity of enQueue operation is O(1).

deQueue Algorithm

  • If the stack s2 is not empty then pop from s2 and return the element.
  • If stack s2 is empty , then transfer all elements from s1 to s2. And return the popped element from s2. We can optimize the code a little by transferring only (n-1) elements from stack s1 to stack s2 and pop the nth element from stack s1 return and the poped element. 
  • If stack s1 is also empty then throw an error.

Time complexity of this algorithm , if the stack s2 is not empty then the complexity is O(1). But if the stack s2 is empty, then we need to transfer all the elements from s1 to s2. But if we carefully observe , the number of transferred elements and the number of popped elements from s2 are equal. Due to this average complexity of pop operation in this case is O(1). The amortized complexity of pop operation is O(1). Following figure is the example of these algorithm.

 

package algorithm.stack;

import java.util.Stack;

public class QueueUsingStack {

 private Stack < Object > enQueueStack = new Stack < > ();
 private Stack < Object > deQueueStack = new Stack < > ();

 public void enQueue(Object data) {
  enQueueStack.push(data);
 }

 public Object deQueue() {
  Object item = null;
  if (!deQueueStack.isEmpty()) {
   item = deQueueStack.pop();
  } else {
   while (!enQueueStack.isEmpty()) {
    deQueueStack.push(enQueueStack.pop());
   }
   item = deQueueStack.pop();
  }
  return item;
 }

 public static void main(String[] args) {
  QueueUsingStack queueUsingStack = new QueueUsingStack();

  queueUsingStack.enQueue("ARPAN");
  queueUsingStack.enQueue("DAS");
  queueUsingStack.enQueue("JAVA");

  System.out.println(queueUsingStack.deQueue());
  System.out.println(queueUsingStack.deQueue());
  System.out.println(queueUsingStack.deQueue());
 }
}

 

CORE JAVA ALGORITHM