Implement Queue using Stacks


  • 0

    Queue is FIFO (first in - first out) data structure, in which the elements are inserted from one side - rear and removed from the other - front.
    The most intuitive way to implement it is with linked lists, but this article will introduce another approach using stacks.
    Stack is LIFO (last in - first out) data structure, in which elements are added and removed from the same end, called top.
    To satisfy FIFO property of a queue we need to keep two stacks. They serve to reverse arrival order of the elements and one of them store the queue elements in their final order.


    Click here to see the full article post


  • 0
    D

    In the 2nd approach: the variable, front would have wrong values. Suppose this scenario:

    s1 is empty and s2 has 2, 3 and 4 after popping 1. So front = 2. If we push 5 front would be 5 as s1 is empty.


  • 0

    diaa, right observation! We have to update front variable in push operation, only in case when the queue is empty. Thank you very much for getting us known this! I will correct the article


  • 0

    @diaa Thanks for pointing out the mistake. I have just published the revision of the article, thanks.


  • 0
    Y

    Why the push( ) is space O(1) in first approach ? We use two stacks, if we consider about pushing 3 times(push 1,2,3), why is it not space O(n)?


  • 0

    @yyma Yes, right space complexity should be O(n), also in the second approach. I didn't take into account the input parameters, but it is a mistake. Will check it


  • 0

    @yyma Thanks for pointing out the mistake. I have just published @elmirap 's revision of the article, please take a look.


  • 0
    J

    @1337c0d3r I think the peek() implementation is wrong for the second approach
    If you use just the "front" variable it will get updated on the push() when stack1 is empty event if there is still members on stack2.
    I would change it to:

    public int peek() {
            if (!stack2.isEmpty()) {
                return stack2.peek();
            }
            return front;
        }
    

    And would not update front on pop()

    What do you think?


  • 0

    @joaonlima Very good observation, thank you . Actually I think that peek method is absent in the second approach, will edit the article


  • 0

    @elmirap @1337c0d3r Really nice solution and analysis. Thank you for sharing!

    One question: should you check if queue is empty at top of the pop() and peek(), like "if(this.empty())"? Or, you suppose the user will check themselves whenever using the method?


  • 0
    S

    I have a simpler implementation with simpler peek and empty functions, and we don't need to maintain the front variable:

    public class MyQueue {
    Stack<Integer> enqueStack;
    Stack<Integer> dequeStack;

    /** Initialize your data structure here. */
    public MyQueue() {
        enqueStack = new Stack<>();
        dequeStack = new Stack<>();
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        if (dequeStack.empty()) dequeStack.push(x);
        else enqueStack.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if(dequeStack.size() > 1) return dequeStack.pop();
        int curr = dequeStack.pop();
        while(!enqueStack.empty()) dequeStack.push(enqueStack.pop());
        return curr;
    }
    
    /** Get the front element. */
    public int peek() {
        return dequeStack.peek();
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return dequeStack.empty();
    }
    

    }

    /**

    • Your MyQueue object will be instantiated and called as such:
    • MyQueue obj = new MyQueue();
    • obj.push(x);
    • int param_2 = obj.pop();
    • int param_3 = obj.peek();
    • boolean param_4 = obj.empty();
      */

  • 0

    Great on analyzing the amortized performance. This sounds like the kind of question that one would encounter in a real interview.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.