Queue Examples

# @ignore-function-tree
def sliding_window_maximum(arr: list[int], k: int, queue: Queue) -> list[int]:
    """Find maximum element in each sliding window of size k"""
    result = []
    for i in range(len(arr)):
        # Remove elements outside current window
        while not queue.empty() and queue.peek() < i - k + 1:
            queue.dequeue()

        # Remove smaller elements
        while not queue.empty() and arr[queue.peek()] < arr[i]:
            queue.dequeue()

        queue.enqueue(i)

        if i >= k - 1:
            result.append(arr[queue.peek()])

    return result

# Example usage
arr = [1, 3, -1, -3, 5, 3, 6, 7]
queue = Queue()
result = sliding_window_maximum(arr, 3, queue)

def first_non_repeating_character_stream(stream: str):
    """
    Find first non-repeating character in a stream of characters.
    """
    result = []
    count = {}
    queue = Queue()
    
    for char in stream:
        queue.enqueue(char)
        count[char] = count.get(char, 0) + 1
        
        while not queue.empty() and count[queue.peek()] > 1:
            queue.dequeue()
            
        result.append(queue.peek() if not queue.empty() else '#')
    
    return result

# Example usage
first_non_repeating_character_stream("aabccbd")

def reverse_k_characters(s, k):
    """
    Reverse first K characters for every chunk of K characters.
    """
    queue = create_queue(s)

    result = []
    while not queue.empty():
        # Get k characters
        chunk = []
        for _ in range(k):
            if not queue.empty():
                chunk.append(queue.dequeue())
        
        # Reverse first k characters
        chunk[:k] = chunk[:k][::-1]
        result.extend(chunk)
    
    return ''.join(result)

# Example usage

reverse_k_characters("abcdefgh", 3)

def generate_binary_numbers(n):
    """
    Generate binary numbers from 1 to n using queue.
    """
    result = []
    queue = Queue()
    queue.enqueue('1')
    
    for _ in range(n):
        current = queue.dequeue()
        result.append(current)
        queue.enqueue(current + '0')
        queue.enqueue(current + '1')
    
    return result

# Example usage
generate_binary_numbers(5)

def generate_number_pattern(n):
    """
    Generate pattern: 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, ...
    """
    result = []
    queue = Queue()
    current_num = 1
    
    while len(result) < n:
        for _ in range(current_num):
            if len(result) < n:
                queue.enqueue(current_num)
        while not queue.empty() and len(result) < n:
            result.append(queue.dequeue())
        current_num += 1
    
    return result

# Example usage

generate_number_pattern(7)

def interleave_queue_elements(arr: List[int]) -> List[int]:
    """
    Interleave elements of a queue of even length.
    """
    queue = Queue()
    for num in arr:
        queue.enqueue(num)
        
    half_size = queue.size // 2
    temp_queue = Queue()
    
    for _ in range(half_size):
        temp_queue.enqueue(queue.dequeue())
    
    result = []
    while not temp_queue.empty():
        result.append(temp_queue.dequeue())
        result.append(queue.dequeue())
    
    return result

# Example usage
interleave_queue_elements([1, 2, 3, 4, 5, 6])

def reverse_k_elements(arr: List[int], k: int) -> List[int]:
    """
    Reverse first K elements of queue.
    """
    queue = Queue()
    for num in arr:
        queue.enqueue(num)
        
    temp_stack = []
    result = []
    
    # Pop first k elements and push to stack
    for _ in range(k):
        if not queue.empty():
            temp_stack.append(queue.dequeue())
    
    # Pop from stack and add to result
    while temp_stack:
        result.append(temp_stack.pop())
    
    # Add remaining elements
    while not queue.empty():
        result.append(queue.dequeue())
    
    return result

# Example usage
reverse_k_elements([1, 2, 3, 4, 5], 3)

def rotate_queue_by_k(arr: List[int], k: int, direction: str = "left") -> List[int]:
    """
    Rotate queue by k positions left or right.
    Output: [3, 4, 5, 1, 2]
    """
    queue = Queue()
    for num in arr:
        queue.enqueue(num)
        
    k = k % queue.size
    result = []
    
    if direction == "left":
        # Move k elements to back
        for _ in range(k):
            queue.enqueue(queue.dequeue())
    else:
        # Move size-k elements to back
        for _ in range(queue.size - k):
            queue.enqueue(queue.dequeue())
    
    while not queue.empty():
        result.append(queue.dequeue())
    return result

# Example usage
rotate_queue_by_k([1, 2, 3, 4, 5], 2, "left")

def rotate_queue_by_blocks(arr: List[int], block_size: int) -> List[int]:
    """
    Rotate queue in blocks.
    """
    queue = Queue()
    for num in arr:
        queue.enqueue(num)
        
    result = []
    temp = []
    
    while not queue.empty():
        # Get a block
        for _ in range(block_size):
            if not queue.empty():
                temp.append(queue.dequeue())
        # Reverse and add block
        temp.reverse()
        result.extend(temp)
        temp = []
    
    return result

# Example usage
rotate_queue_by_blocks([1, 2, 3, 4, 5, 6], 2)