Short O(1) amortized, C++ / Java / Ruby


  • 240

    I have one input stack, onto which I push the incoming elements, and one output stack, from which I peek/pop. I move elements from input stack to output stack when needed, i.e., when I need to peek/pop but the output stack is empty. When that happens, I move all elements from input to output stack, thereby reversing the order so it's the correct order for peek/pop.

    The loop in peek does the moving from input to output stack. Each element only ever gets moved like that once, though, and only after we already spent time pushing it, so the overall amortized cost for each operation is O(1).

    Ruby

    class Queue
        def initialize
            @in, @out = [], []
        end
    
        def push(x)
            @in << x
        end
    
        def pop
            peek
            @out.pop
        end
    
        def peek
            @out << @in.pop until @in.empty? if @out.empty?
            @out.last
        end
    
        def empty
            @in.empty? && @out.empty?
        end
    end
    

    Java

    class MyQueue {
    
        Stack<Integer> input = new Stack();
        Stack<Integer> output = new Stack();
        
        public void push(int x) {
            input.push(x);
        }
    
        public void pop() {
            peek();
            output.pop();
        }
    
        public int peek() {
            if (output.empty())
                while (!input.empty())
                    output.push(input.pop());
            return output.peek();
        }
    
        public boolean empty() {
            return input.empty() && output.empty();
        }
    }
    

    C++

    class Queue {
        stack<int> input, output;
    public:
    
        void push(int x) {
            input.push(x);
        }
    
        void pop(void) {
            peek();
            output.pop();
        }
    
        int peek(void) {
            if (output.empty())
                while (input.size())
                    output.push(input.top()), input.pop();
            return output.top();
        }
    
        bool empty(void) {
            return input.empty() && output.empty();
        }
    };

  • 0
    D

    I like your smart and neat solution, as always. Very nice


  • -2
    This post is deleted!

  • 0

    Very nice analysis of the amoritzed cost :-) Also very clever to use peek() inside pop() to remove duplicate codes.


  • 0

    Hmm, if it's the same idea and not a better implementation, then what value does it add to the discussion?


  • 0

    Hi, StefanPochmann. Yeah, maybe little value. I will pay attention to that. BTW, I feel that I have lost in our discussion about Power of 2.


  • 0
    T

    Hi Stefan, awesome code as always! You didn't use python this time, I guess because all the self. is too annoying?


  • 0

    @totolipton Yes, your guess is correct :-) I still would've used Python if it could make up for it with advantages, but here it just doesn't have any.


  • 0

    I have added a Ruby version now. Ruby is amazing.


  • 0
    H

    Intelligent solution


  • 0

    Awesome! Your code is very easy to understand!


  • 3
    J

    Hi, just have a question. Why do you peek() in pop()? I don't quite get it.


  • 0

    Hi, James_Illusion, Stefan does that because both peek and pop has an identical sub-process to move elements from one stack to the other. In order to prevent duplicate codes, Stefan just call peek in pop to do the sub-process.


  • 1
    K

    so you can call a function with return value without assigning to a variable? as peek() in the code


  • 0
    V

    Pure beauty. Thanks


  • 0
    G

    this is definitely cool design! thank you for share


  • 13
    Z

    Do you want to marry me ? I love you so much


  • 0
    V

    Hi @StefanPochmann, your solution is very intuitive and clear. I have a small doubt though, what happens if we performed some push operations, then a pop operation(now the input stack is empty and the output stack is filled with data) and then we perform the push operation again. We are not moving the data back to the input stack as per the code above(I am following the JAVA version). Wouldn't that cause a problem?

    Below is an example to illustrate the test case I am concerned about:

    Say we push 1, 2 and 3 initially,

    INPUT STACK - 1,2,3 (bottom to top)

    OUTPUT STACK - null

    Now we peek,

    INPUT STACK - null

    OUTPUT STACK - 3,2,1 (bottom to top)

    RESULT of peek - 1

    Now we push 4,

    INPUT STACK - 4

    OUTPUT STACK - 3,2,1 (bottom to top)

    Now we pop,

    INPUT STACK - 1,2,3 (bottom to top)

    OUTPUT STACK - null

    RESULT of pop - removed 4 (instead of 1)


  • 2

    Your last step is wrong. No idea why you think the 1,2,3 already on the output stack would go back to the input stack. The pop just pops and returns the 1 from the output stack, nothing else changes.


  • 0
    V

    Oh ok now I get it!! So once we have popped everything that is present in the OUTPUT STACK, the data from the INPUT STACK will be moved to the OUTPUT STACK again.
    Actually I was trying to get 4 in the sequence in a single stack but now I see where I was wrong.


Log in to reply
 

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