Only push is O(n), others are O(1). Using one queue. Combination of two shared solutions


  • 85
    Y
    class MyStack 
    {
        Queue<Integer> queue;
        
        public MyStack()
        {
            this.queue=new LinkedList<Integer>();
        }
        
        // Push element x onto stack.
        public void push(int x) 
        {
           queue.add(x);
           for(int i=0;i<queue.size()-1;i++)
           {
               queue.add(queue.poll());
           }
        }
    
        // Removes the element on top of the stack.
        public void pop() 
        {
            queue.poll();
        }
    
        // Get the top element.
        public int top() 
        {
            return queue.peek();
        }
    
        // Return whether the stack is empty.
        public boolean empty() 
        {
            return queue.isEmpty();
        }
    }

  • 0
    Y
    This post is deleted!

  • 1
    Y

    And I have a question: if using addAll() in Push(), is it O(1)?

     public void push(int x) 
        {
           Queue<Integer> temp = new LinkedList<Integer>();
           
           temp.add(x);
           temp.addAll(queue);
           queue=temp;
        }

  • 0
    J

    I think it is the same, as the function also push the elements of the queue one by one


  • 0
    A

    I like the idea of this solution as it is quite creative. But the push operation will become a very expansive when the queue grows large. In other words, this method has no clearly advantage in terms of efficiency.


  • 0
    D

    The idea is simple and great, but time consuming!


  • 3
    Y

    There are two solutions cost O(n) and O(1) for different operations:

    1. push: O(n), pop/top: O(1)
    2. push: O(1), pop/top: O(n)

    Time efficiency depends on operation frequency of push, pop, top:
    if push>pop+top, second solution is better.
    if push<pop+top, first solution is better.

    And I feel, in most cases, push<pop+top.

    This is same idea in C++:
    https://leetcode.com/discuss/46975/a-simple-c-solution


  • 1

    why is Only push is O(n), others are O(1). Using one queue?


  • 0
    S

    private Queue<Integer> q1 = new LinkedList<>();
    anyone could explain how to understand this code from solution?
    I mean why is it necessary to call Linkedlist<>()?
    thank you!


  • 2
    P

    Nice solution. I just want to mention one thing, queue.poll() will return E(element) so I think method pop() should be public Integer pop(). Thanks.


  • 0
    M

    @YYZ90 My solution was similar, but I used a LinkedList instead :

    public class StackWithQueues {
    
        private LinkedList<Integer> q;
    
        /**
         * Initialize your data structure here.
         */
        public StackWithQueues() {
            q = new LinkedList<>();
        }
    
        /**
         * Push element x onto stack.
         */
        public void push(int x) {
            q.add(x);
        }
    
        /**
         * Removes the element on top of the stack and returns that element.
         */
        public int pop() {
            return q.pollLast();
        }
    
        /**
         * Get the top element.
         */
        public int top() {
            return q.peekLast();
        }
    
        /**
         * Returns whether the stack is empty.
         */
        public boolean empty() {
            return (q.isEmpty());
        }
    
    }
    

  • 0
    J

    @sixgod Queue is an interface in Java, and the LinkedList class implement Deque which is an interface extend Queue.

    You can see the java document for the detail.


  • 0
    J
    This post is deleted!

Log in to reply
 

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