# Time: O(1), amortized # Space: O(n) # # Implement the following operations of a queue using stacks. # # push(x) -- Push element x to the back of queue. # pop() -- Removes the element from in front of queue. # peek() -- Get the front element. # empty() -- Return whether the queue is empty. # # Notes: # You must use only standard operations of a stack # -- which means only push to top, peek/pop from top, size, and is empty operations are valid. # Depending on your language, stack may not be supported natively. # You may simulate a stack by using a list or deque (double-ended queue), # as long as you use only standard operations of a stack. # You may assume that all operations are valid # (for example, no pop or peek operations will be called on an empty queue). # class Queue: # initialize your data structure here. def __init__(self): self.A, self.B = [], [] # @param x, an integer # @return nothing def push(self, x): self.A.append(x) # @return nothing def pop(self): self.peek() self.B.pop() # @return an integer def peek(self): if not self.B: while self.A: self.B.append(self.A.pop()) return self.B[-1] # @return an boolean def empty(self): return not self.A and not self.B