Python All O(1) Recursive Queue Solution.


  • 0
    A
    The Idea is very simple. Stack is a data structure widely used for simulating recursion, therefore we could create a recursive queue to simulate it. 
    
    One way to do that is 
    1. A queue with only two element. 
    2. The first element is the statck.top()
    3. The second element is another queue. What's in the queue? Please goto 1. 
    
    So when we pushed 1,2,3,4,5 into the queue. The queue ends up looks like this,
    (5, (4, (3, (2, (1)))))
    
    
    from collections import deque
    
    class Stack:
        # initialize your data structure here.
        def __init__(self):
            self.queue = None
    
        # @param x, an integer
        # @return nothing
        def push(self, x):
            if self.queue == None:
                self.queue = deque([x])
            else:
                self.queue = deque([x, self.queue])
    
        # @return nothing
        def pop(self):
            if self.queue != None:
                self.queue.popleft()
                try:
                    self.queue = self.queue.popleft()
                except:
                    self.queue = None
    
        # @return an integer
        def top(self):
            return self.queue[0]
            
    
        # @return an boolean
        def empty(self):
            return self.queue == None

Log in to reply
 

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