Accepted python, using one queue


  • 0
    H

    See my previous post with two queues,https://leetcode.com/discuss/40085/accepted-python-using-two-queues. I then noticed that size can be used and here is the one queue solution.

    class Stack:
        # initialize your data structure here.
        def __init__(self):
            self.q1=[]
    
        # @param x, an integer
        # @return nothing
        def push(self, x):
            self.q1.append(x)
    
        # @return nothing
        def pop(self):
            lens=len(self.q1)
            for i in range(lens-1):
                tmp=self.q1.pop(0)
                self.q1.append(tmp)
            self.q1.pop(0)
    
    
        # @return an integer
        def top(self):
            lens=len(self.q1)
            for i in range(lens):
                tmp=self.q1.pop(0)
                self.q1.append(tmp)
            return tmp
    
        # @return an boolean
        def empty(self):
            if self.q1:
                return False
            return True

  • -5
    R

    Why so complex?

    class Stack:
    # initialize your data structure here.
    def __init__(self):
        self.q = []
    
    # @param x, an integer
    # @return nothing
    def push(self, x):
        self.q.append(x)
    
    # @return nothing
    def pop(self):
        return self.q.pop()
    
    # @return an integer
    def top(self):
        return self.q[-1]
    
    # @return an boolean
    def empty(self):
        return not self.q

  • 0
    H

    this is not right, you cannot use pop() from back, you can just pop from front mimicking a queue.


  • 0
    R

    There is something called double-ended queue
    https://en.wikipedia.org/wiki/Double-ended_queue


  • 0
    H

    thx, I learned about that, however, the problem says 'You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid', only front pop is allowed here


  • 0
    Z

    Can the author or anyone explain why there is down vote? Any violation in this solution?

    Because my solution is the same as this one, only more concise...

    And yes I know deque is better. Learning about it now.


  • 0
    H

    Seems the one answered the question made a mistaken vote. I'd like to see your more succinct code : )


  • 2
    Z

    I just up vote to compensate that :P. As I said, we are the same algorithm:

    class Stack(object):
    
        def __init__(self):
            """
            initialize your data structure here.
            """
            self.list = []
    
        def push(self, x):
            """
            :type x: int
            :rtype: nothing
            """
            self.list.append(x)
    
        def pop(self):
            """
            :rtype: nothing
            """
            if len(self.list) > 0:          # careful about popping from []
                for _ in range(len(self.list)-1):
                    self.list.append(self.list.pop(0))
                return self.list.pop(0)
            else: return []
    
        def top(self):
            """
            :rtype: int
            """
            for _ in range(len(self.list)):
                a = self.list.pop(0)
                self.list.append(a)
            return a
    
        def empty(self):
            """
            :rtype: bool
            """
            return len(self.list) == 0

Log in to reply
 

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