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

    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

    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

    @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

    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.

  • 0

    Hi, I'm kind of a beginner. But for Approach #2, why do we need a front variable if we can simply do s2.peek(). And if s2 is empty, we cannot peek the top anyway, why would we then need to look at front. Would someone please clarify this for me? I would appreciate that.

  • 0

    @lliang9838 - It will be helpful when peek operation is called before the first pop operation because in that case everything will be in S1 and if we keep track of first element i.e. front, then we don't need to empty S1 to S2 just for the peek operation.

  • 0
    This post is deleted!

  • 0

    Algo #2: I'm not seeing how this case will work if you push immediately after you pop().

  • 0

    As for time complexity analysis of approach 2, why is it O(2n/2n) ?
    I think it might be O(4n/2n), though the final result is also O(1).

  • 0

    can you give a python solution?

  • 0

    Python solution:

    from Queue import LifoQueue

    class MyQueue(object):

    def __init__(self):
        Initialize your data structure here.
        self.q1 =  LifoQueue() #intermediate stack
        self.q2 =  LifoQueue() # results get saved here
    def push(self, x):
        Push element x to the back of queue.
        :type x: int
        :rtype: void
        while(not self.q2.empty()):
            item = self.q2.get(block = False)
            self.q1.put(item, block = False)
        self.q2.put(x, block=False)
        while(not self.q1.empty()):
            item = self.q1.get(block=False)
            self.q2.put(item, block=False)
    def pop(self):
        Removes the element from in front of queue and returns that element.
        :rtype: int
        return self.q2.get(block=False)
    def peek(self):
        Get the front element.
        :rtype: int
        item = self.q2.get(block=False)
        self.q2.put(item, block=False)
        return item
    def empty(self):
        Returns whether the queue is empty.
        :rtype: bool
        return self.q2.empty()

    Your MyQueue object will be instantiated and called as such:

    obj = MyQueue()


    param_2 = obj.pop()

    param_3 = obj.peek()

    param_4 = obj.empty()

Log in to reply

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