2018-10-18 Implement Stack by Two Queues [E]

494. Implement Stack by Two Queues
     Implement a stack by two queues. The queue is first in first out (FIFO). That means you can not directly pop the last element in a queue.

Example
push(1)
pop()
push(2)
isEmpty() // return false
top() // return 2
pop()
isEmpty() // return true

class Stack:
    def __init__(self):
        self.q1 = []
        self.q2 = [] # think this as auxiliary tool

    """
    @param: x: An integer
    @return: nothing
    """
    def push(self, x):
        self.q1.append(x)
        
    """
    @return: nothing
    """
    def pop(self):
        while len(self.q1) > 1:
            self.q2.append(self.q1.pop(0))
        result = self.q1.pop(0)
        self.q1, self.q2 = self.q2, self.q1 # keep q1 as my main queue
        return result

    """
    @return: An integer
    """
    def top(self):
        while len(self.q1) > 1:
            self.q2.append(self.q1.pop(0))
        result = self.q1.pop(0)
        self.q1, self.q2 = self.q2, self.q1 # keep q1 as my main queue
        self.q1.append(result) # only thing I need to do here
        return result
        
        # Or simply write
        # result = self.q1.pop()
        # self.q1.append(result)
        # return result

    """
    @return: True if the stack is empty
    """
    def isEmpty(self):
        return len(self.q1) == 0

• Time : O(1) for push and isEmpty O(n) for pop and top
• Capacity: O(n) for this data structure

Notes:

1. Even though I use a list to perform like a queue, I still need to know some basic python operations of Queue. For example:

import Queue
queue = Queue.Queue()
queue.get()
queue.put(x)

2. Some bugs occurred at isEmpty(), because
   1) I did not read carefully the requirement
   2) I tried to return len(self.q1), but I need to return a boolean. (use while queue only in if-statement)

3. I though it was not okay to call self.q1.pop(), given that def pop(self) has self as params. But I was wrong.