Interview Questions

  • View all algorithm tutorials
  • blank
  • Implement a queue using two stacks

    Want more content about improving your career, algorithms, and interview practice? Check out our newsletter!

    In another interview question we explained what a queue is and how to implement one using a linked list. Now we'll provide a solution to a common interview question, which is how to implement a queue using two stacks. A stack is a data structure where items can be added to a collection and removed from it just like in a queue, except the difference is the order in which they are removed. In a stack, the last item added will be the first item removed (last in, first out). Stacks usually have two basic methods, push, which adds an item into the stack, and pop, which "pops off" the top item from the stack. You can think of a stack like a physical stack of books: to add a new book to the stack you simply place the book on top, and then when you want to make the stack smaller you start removing books from the top of the stack.

    Example of stack operations

    Algorithm for queue using two stacks

    For example: Suppose we push "a", "b, "c" to a stack. If we are trying to implement a queue and we call the dequeue method 3 times, we actually want the elements to come out in the order: "a", "b, "c", which is in the opposite order they would come out if we popped from the stack. So, basically, we need to access the elements in the reverse order that they exist in the stack. The following algorithm will implement a queue using two stacks.
    (1) When calling the enqueue method, simply push the elements into the stack 1. (2) If the dequeue method is called, push all the elements from stack 1 into stack 2, which reverses the order of the elements. Now pop from stack 2.

    Code

    // implement stacks using plain arrays with push and pop functions
    var Stack1 = [];
    var Stack2 = [];
    
    // implement enqueue method by using only stacks
    // and the push and pop functions
    function Enqueue(element) {
      Stack1.push(element);
    }
    
    // implement dequeue method by pushing all elements
    // from stack 1 into stack 2, which reverses the order
    // and then popping from stack 2
    function Dequeue() {
      if (Stack2.length === 0) {
        if (Stack1.length === 0) { return 'Cannot dequeue because queue is empty'; }
        while (Stack1.length > 0) {
          var p = Stack1.pop();
          Stack2.push(p);
        }
      }
      return Stack2.pop();
    }
    
    Enqueue('a');
    Enqueue('b');
    Enqueue('c');
    Dequeue(); 
    
    # implement stacks using plain lists with push and pop functions
    Stack1 = []
    Stack2 = []
    
    # implement enqueue method by using only stacks
    # and the append and pop functions
    def Enqueue(element):
      Stack1.append(element)
      
    # implement dequeue method by pushing all elements
    # from stack 1 into stack 2, which reverses the order
    # and then popping from stack 2
    def Dequeue():
      if len(Stack2) == 0:
        if len(Stack1) == 0:
          return 'Cannot dequeue because queue is empty'
        while len(Stack1) > 0:
          p = Stack1.pop()
          Stack2.append(p)
      return Stack2.pop()
    
    Enqueue('a')
    Enqueue('b')
    Enqueue('c')
    print Dequeue()
    
    Run Code
    Run Code

    Running time

    The worst case running time for implementing these operations using stacks is O(n) because you need to transfer n elements from stack 1 to stack 2 when a dequeue method is called. Pushing to stack 1 is simply O(1).

    Sources

    https://www.glassdoor.com/Interview/How-to-implement-a-queue-simply-using-two-stacks-and-how-to-implement-a-highly-efficient... http://www.careercup.com/question?id=4399683
    mrdaniel published this on 11/24/15 | linked list, queue, stack, Google, Facebook
    Comments
  • +
  • 1
  • -
  • The following code supports multiple enqueue and dequeue operations in any order, the result will always work like a queue
    var stack1 = [];
    var stack2 = [];
    function enqueue(ele){
    //if dequeue was called before, all the elements would be in stack2, so to maintain the order
    //push elements into stack1 before performing the actual enqueue operation
    	if(stack2.length>0){ 
    		var len = stack2.length;
    		for(var i=0;i<len ; i++){
    			var p= stack2.pop()
    			stack1.push(p);
    		}
        }
    	stack1.push(ele);
    }
    function dequeue(ele){
          // if dequeue was called consecutively, all the elements would be in stack2
    	if(stack2.length>0){
    		stack2.pop();
            }
           // if enqueue was called right before this dequeue, stack2 is empty
    	else if(stack2.length===0){
    		if(stack1.length===0){ // if the first operation is dequeue itself
    			return "Queue is empty";
    		}
    		else if(stack1.length===1){ // if a single operation as enqueue was performed
    			return stack1.pop();
    		}
                 // if enqueue was called before this operation, all the elements are in stack1,
                 // so pop them and push the elements into stack2,  then pop()
    		else if(stack1.length>0){
    			var len = stack1.length
    			for(var i=0;i< len ; i++){
    				var p= stack1.pop()
    				stack2.push(p);
    			}
    			return stack2.pop();
    		}
    	}
    }
    
    
  • +
  • 0
  • -
  • In Java could be done similar to this.
    public static void main(String[] args){
      Stack<Object> stack1 = new Stack<>();
      Stack<Object> stack2 = new Stack<>();
      stack1.push('a');
      stack1.push('b');
      stack1.push('c');
    
     if(stack1.size() == 0){
       if(stack2.size() == 0){
           System.out.println("Empty");
    }}
    while(stack1.size() > 0){
      Object p = stack1.pop();
      stack2.push(p);
    }
    System.out.println(stack2);
    }
    
    Log in to submit a comment.