Concise 1 Queue - Java, C++, Python


  • 47

    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.


  • 0
    S

    @nmbmlyx0211, check how deque works in Python here.


Log in to reply
 

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