队列示例

# @ignore-function-tree
def sliding_window_maximum(arr: list[int], k: int, queue: Queue) -> list[int]:
    # 查找大小为k的滑动窗口中的最大元素
    result = []
    for i in range(len(arr)):
        # 移除当前窗口外的元素
        while not queue.empty() and queue.peek() < i - k + 1:
            queue.dequeue()

        # 移除较小的元素
        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

# 使用示例
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):
    """
    在字符流中找到第一个不重复的字符。
    """
    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

# 使用示例
first_non_repeating_character_stream("aabccbd")

def reverse_k_characters(s, k):
    """
    对每k个字符的块反转前k个字符。
    """
    queue = create_queue(s)

    result = []
    while not queue.empty():
        # 获取k个字符
        chunk = []
        for _ in range(k):
            if not queue.empty():
                chunk.append(queue.dequeue())
        
        # 反转前k个字符
        chunk[:k] = chunk[:k][::-1]
        result.extend(chunk)
    
    return ''.join(result)

# 使用示例
reverse_k_characters("abcdefgh", 3)

def generate_binary_numbers(n):
    """
    使用队列生成1到n的二进制数。
    """
    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

# 使用示例
generate_binary_numbers(5)

def generate_number_pattern(n):
    """
    生成模式：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

# 使用示例
generate_number_pattern(7)

def interleave_queue_elements(arr: List[int]) -> List[int]:
    """
    交错排列偶数长度队列的元素。
    """
    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

# 使用示例
interleave_queue_elements([1, 2, 3, 4, 5, 6])

def reverse_k_elements(arr: List[int], k: int) -> List[int]:
    """
    反转队列的前k个元素。
    """
    queue = Queue()
    for num in arr:
        queue.enqueue(num)
        
    temp_stack = []
    result = []
    
    # 弹出前k个元素并压入栈
    for _ in range(k):
        if not queue.empty():
            temp_stack.append(queue.dequeue())
    
    # 从栈中弹出并添加到结果
    while temp_stack:
        result.append(temp_stack.pop())
    
    # 添加剩余元素
    while not queue.empty():
        result.append(queue.dequeue())
    
    return result

# 使用示例
reverse_k_elements([1, 2, 3, 4, 5], 3)

def rotate_queue_by_k(arr: List[int], k: int, direction: str = "left") -> List[int]:
    """
    向左或向右旋转队列k个位置。
    输出：[3, 4, 5, 1, 2]
    """
    queue = Queue()
    for num in arr:
        queue.enqueue(num)
        
    k = k % queue.size
    result = []
    
    if direction == "left":
        # 将k个元素移到后面
        for _ in range(k):
            queue.enqueue(queue.dequeue())
    else:
        # 将size-k个元素移到后面
        for _ in range(queue.size - k):
            queue.enqueue(queue.dequeue())
    
    while not queue.empty():
        result.append(queue.dequeue())
    return result

# 使用示例
rotate_queue_by_k([1, 2, 3, 4, 5], 2, "left")

def rotate_queue_by_blocks(arr: List[int], block_size: int) -> List[int]:
    """
    按块旋转队列。
    """
    queue = Queue()
    for num in arr:
        queue.enqueue(num)
        
    result = []
    temp = []
    
    while not queue.empty():
        # 获取一个块
        for _ in range(block_size):
            if not queue.empty():
                temp.append(queue.dequeue())
        # 反转并添加块
        temp.reverse()
        result.extend(temp)
        temp = []
    
    return result

# 使用示例
rotate_queue_by_blocks([1, 2, 3, 4, 5, 6], 2)