Python solution with detailed explanation


  • 0
    G

    Solution

    Implement Stack using Queues https://leetcode.com/problems/implement-stack-using-queues/?tab=Description

    1. Use 2 queues and make push() O(1) and pop() O(N). For push, always push to q1. For pop(), dequeue all but last element from q1 and enqueue in q2. Then swap q1 and q2. This ensures that push always happens to q1.
    2. We can make push() as O(N) and pop as O(1).
    from Queue import Queue
    class MyStack(object):
        def __init__(self):
            """
            initialize your data structure here.
            """
            self.q1, self.q2 = Queue(), Queue()
            return
    
        def push(self, x):
            """
            :type x: int
            :rtype: nothing
            """
            self.q1.put(x)
            return
    
        def pop(self):
            """
            :rtype: nothing
            """
            while self.q1.qsize() > 1:
                x = self.q1.get()
                self.q2.put(x)
            if self.q1.qsize() == 1:
                result = self.q1.get()
                self.q1, self.q2 = self.q2, self.q1
                return result
            
    
        def top(self):
            """
            :rtype: int
            """
            while self.q1.qsize() > 1:
                x = self.q1.get()
                self.q2.put(x)
            if self.q1.qsize() == 1:
                result = self.q1.get()
                self.q2.put(result)
                self.q1, self.q2 = self.q2, self.q1
                return result        
    
        def empty(self):
            """
            :rtype: bool
            """
            return not bool(self.q1.qsize() + self.q2.qsize())
    

Log in to reply
 

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