Two possible solutions


  • 0
    J

    This is trivial problem and can be easly solved using either one or two queues.


    First the two queue solutions:


    class MyStack {
        
        private Queue<Integer> full = new LinkedList<>();
        private Queue<Integer> empty = new LinkedList<>();
    
        // Push element x onto stack.
        public void push(int x) {
    
            full.offer(x);
        }
    
        // Removes the element on top of the stack.
        public void pop() {
    
            copyAllButOne();
            full.remove();
            swap();
        }
    
        // Get the top element.
        public int top() {
    
            copyAllButOne();
            final int result = full.remove();
            empty.offer(result);
            swap();
            return result;
        }
    
        // Return whether the stack is empty.
        public boolean empty() {
    
            return full.isEmpty();
        }
    
        private void copyAllButOne() {
            while(full.size() > 1) {
                empty.offer(full.remove());
            }
        }
    
        private void swap() {
            Queue<Integer> tmp = full;
            full = empty;
            empty = tmp;
        }
    }
    

    Secondly the single queue solution, as long as your queue implementation provides size() method you can easly implement it.


    class MyStack {
        private final Queue<Integer> queue = new LinkedList<>();
    
        // Push element x onto stack.
        public void push(int x) {
    
            queue.offer(x);
        }
    
        // Removes the element on top of the stack.
        public void pop() {
    
            moveAllButOne();
            queue.remove();
        }
    
        // Get the top element.
        public int top() {
    
            moveAllButOne();
            final int result = queue.remove();
            queue.offer(result);
            return result;
        }
    
        // Return whether the stack is empty.
        public boolean empty() {
    
            return queue.isEmpty();
        }
    
        private void moveAllButOne() {
            for(int count = queue.size(); count > 1; count--) {
                queue.offer(queue.remove());
            }
        }
    }
    

    In terms of performence and memory usage both solutions are (almost) the same.

    With running time of the methods as fallows:

    empty() - O(1)
    push() - O(1)
    pop() - O(N)
    top() - O(N)

    And memory usage of O(N) for both solutions.


Log in to reply
 

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