AC python solution using two queue


  • 0
    C

    Use two queues, only appendleft() and pop() function is used.

    Polar means which queue contains valid data.
    After any operation, q[polar] contains valid data, the other one is always empty.

    After pop from key, check whether it is empty. If empty, then the most recent pop item from queue is the one for a stack.pop().

    from collections import deque
    class Stack:
        
        # initialize your data structure here.
        def __init__(self):
            self.q  = [deque(),deque()]
            self.polar = 0               #which queue contains data
            
        # @param x, an integer
        # @return nothing
        def push(self, x):
            self.q[self.polar].appendleft(x)
    
        # @return nothing
        def pop(self):
            while self.q[self.polar]:
                temp = self.q[self.polar].pop()
                if self.q[self.polar]: self.q[1-self.polar].appendleft(temp)
            self.polar = 1-self.polar
    
        # @return an integer
        def top(self):
            temp = None
            while self.q[self.polar]:
                temp = self.q[self.polar].pop()
                self.q[1-self.polar].appendleft(temp)
            self.polar = 1-self.polar
            return temp
    
        # @return an boolean
        def empty(self):
            return not self.q[self.polar]

Log in to reply
 

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