Queue Pattern

class MyQueue:
    """FIFO queue using two LIFO stacks"""
    
    def __init__(self):
        self.inbox = []   # For push
        self.outbox = []  # For pop/peek
    
    def push(self, x):
        self.inbox.append(x)
    
    def pop(self):
        self._transfer()
        return self.outbox.pop()
    
    def peek(self):
        self._transfer()
        return self.outbox[-1]
    
    def empty(self):
        return not self.inbox and not self.outbox
    
    def _transfer(self):
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())

from collections import deque

class MovingAverage:
    """Calculate moving average of last n elements"""
    
    def __init__(self, size):
        self.size = size
        self.queue = deque()
        self.total = 0
    
    def next(self, val):
        self.queue.append(val)
        self.total += val
        
        if len(self.queue) > self.size:
            self.total -= self.queue.popleft()
        
        return self.total / len(self.queue)

from collections import deque

def max_sliding_window(nums, k):
    """Maximum in each window of size k"""
    result = []
    dq = deque()  # Store indices, values in decreasing order
    
    for i in range(len(nums)):
        # Remove indices out of window
        while dq and dq[0] <= i - k:
            dq.popleft()
        
        # Remove smaller elements
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()
        
        dq.append(i)
        
        # Add to result once window is formed
        if i >= k - 1:
            result.append(nums[dq[0]])
    
    return result

from collections import deque

def level_order(root):
    """Binary tree level order traversal"""
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level = []
        level_size = len(queue)
        
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(level)
    
    return result