Simple and fast Java Solution with explanation


  • 0
    G

    The key here is to use 2 stacks: The first one is our "back-stack", where we push all the incoming elements on. The second one is our "reverse-stack". Whenever pop or peek is called, we have to make sure that the reverse-stack is not empty. If it is empty, we push all elements from our back-stack into the reverse-stack - we have it in the right order then.

    As you can see, we really only do this if it is necessary, to avoid expensive pop and peek operations. So most of the time, peek() and pop() will operate in O(1). In the worst case - when our reverse stack is empty, the operation will take O(n), where n is the number of elements in our back-stack.

    
        Stack<Integer> backStack = new Stack<>();
        Stack<Integer> reverseStack = new Stack<>();
        
        public MyQueue() {
            
        }
        
        /** Push element x to the back of queue. */
        public void push(int x) {
            backStack.push(x);
        }
        
        /** Removes the element from in front of queue and returns that element. */
        public int pop() {
            if (empty()) {
                return -1;
            }
            
            if (reverseStack.empty()) {
                toggleStacks();
            }
            
            return reverseStack.pop();
        }
        
        /** Get the front element. */
        public int peek() {
            if (empty()) {
                return -1;
            }
            
            if (reverseStack.empty()) {
                toggleStacks();
            }
            
            return reverseStack.peek();
        }
        
        /** Returns whether the queue is empty. */
        public boolean empty() {
            return reverseStack.empty() && backStack.empty();
        }
        
        private void toggleStacks() {
            while (!backStack.empty()) {
                reverseStack.push(backStack.pop());
            }
        }
    
    

Log in to reply
 

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