Python 36ms


  • 0
    H

    My solution only uses one queue. The idea for the pop() is that: for example, there are 4 items in the queue x1, x2, x3, x4, dequeue the first three and enqueue them, so it becomes x4, x1, x2, x3. Then we can pop x4. In this implementation, push() is O(1), while pop() and top() are O(n).

    class MyStack(object):
    
        def __init__(self):
            """
            Initialize your data structure here.
            """
            self.q = Queue()
    
        def push(self, x):
            """
            Push element x onto stack.
            :type x: int
            :rtype: void
            """
            self.q.push(x)
            
    
        def pop(self):
            """
            Removes the element on top of the stack and returns that element.
            :rtype: int
            """
            count = self.q.size()
            while (count > 1):
                self.q.push(self.q.pop())
                count -= 1
            return self.q.pop()
            
    
        def top(self):
            """
            Get the top element.
            :rtype: int
            """
            temp = self.pop()
            self.q.push(temp)
            return temp
     
    
        def empty(self):
            """
            Returns whether the stack is empty.
            :rtype: bool
            """
            return self.q.size() == 0
    

    I implemented the class Queue using list.

    class Queue:
        def __init__(self):
            self.items = []
        def push(self, data):
            self.items.append(data)
        def pop(self):
            return self.items.pop(0)
        def isEmpty(self):
            return items == []
        def peek(self):
            return self.items[0]
        def size(self):
            return len(self.items)
    

Log in to reply
 

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