Java Clean Code


  • 0
    C
    class MyQueue {
        
        private Stack<Integer> stack;
        
        public MyQueue() {
            this.stack = new Stack<>();
        }
        
        // Push element x to the back of queue.
        public void push(int x) {
            stack.push(x);
        }
    
        // Removes the element from in front of queue.
        public void pop() {
            Stack<Integer> tempStack = new Stack<Integer>();
            moveStack(stack, tempStack);
            tempStack.pop();
            moveStack(tempStack, stack);
        }
    
        // Get the front element.
        public int peek() {
            Stack<Integer> tempStack = new Stack<Integer>();
            moveStack(stack, tempStack);
            int value = tempStack.peek();
            moveStack(tempStack, stack);
            return value;
        }
    
        // Return whether the queue is empty.
        public boolean empty() {
            return stack.empty();
        }
        
        private void moveStack(Stack<Integer> from, Stack<Integer> to) {
            int size = from.size();
            for (int i = 0; i < size; i++) {
                int value = from.pop();
                to.push(value);
            }
        }
    }

  • 0
    F

    It looks like complexity of pop() and peek() methods is O(n). You could decrease it down to O(1) amortized, if you use 2 stacks.


  • 0
    C

    @ffbit Currently the second stack is created on demand as you can see in the pop() and peek().. Are you talking about a different algorithm?


  • 0
    F

    Exactly. There is another approach to solve this problem using two stacks with O(1) complexity for those 2 methods.


  • 0
    T

    In the worst case, it is still O(n), since you still have to move element between two stacks


  • 0
    F

    I mentioned O(1) amortized, which means that sometimes copying happens.


Log in to reply
 

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