Concise 1 Queue - Java, C++, Python


  • 46

    Explanation:

    Just use a queue where you "push to front" by pushing to back and then rotating the queue until the new element is at the front (i.e., size-1 times move the front element to the back).


    C++: 0 ms

    class Stack {
        queue<int> q;
    public:
        void push(int x) {
            q.push(x);
            for (int i=1; i<q.size(); i++) {
                q.push(q.front());
                q.pop();
            }
        }
    
        void pop() {
            q.pop();
        }
    
        int top() {
            return q.front();
        }
    
        bool empty() {
            return q.empty();
        }
    };
    

    Java: 140 ms

    class MyStack {
    
        private Queue<Integer> queue = new LinkedList<>();
    
        public void push(int x) {
            queue.add(x);
            for (int i=1; i<queue.size(); i++)
                queue.add(queue.remove());
        }
    
        public void pop() {
            queue.remove();
        }
    
        public int top() {
            return queue.peek();
        }
    
        public boolean empty() {
            return queue.isEmpty();
        }
    }
    

    Python: 36 ms

    class Stack:
    
        def __init__(self):
            self._queue = collections.deque()
    
        def push(self, x):
            q = self._queue
            q.append(x)
            for _ in range(len(q) - 1):
                q.append(q.popleft())
            
        def pop(self):
            return self._queue.popleft()
    
        def top(self):
            return self._queue[0]
        
        def empty(self):
            return not len(self._queue)

  • 2

    Rotating idea is great. No need to create a new queue. Thanks.


  • 0
    Y

    Good idea. You can use rotate(1) to implement the rotation part.


  • 1

    I am wondering the runtime among each language. Really big difference!


  • 0
    M
    This post is deleted!

  • 1
    L

    @StefanPochmann Just wondering why you need to set q=self._queue when you could've just used self.queue.


  • 1

    @livelearn I am using the original queue.

    Not sure why I created the extra variable, probably a mix of (1) shorter name for better readability and (2) faster access.


  • 0
    X
    This post is deleted!

  • 0
    J

    @StefanPochmann For Python, I think you can use extendleft() to add elements to the left of queue directly instead of rotating it.


  • 0

    @jiaqi13 Please read the first note of the problem specification.


  • -1
    N

    @StefanPochmann
    For python solution, could you please explain why should use popleft() instead of pop(), since it says" Removes the element on top of the stack". Thank you very much.


Log in to reply
 

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