萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> 程式語言綜合

Python 列表模擬佇列 (Queue) 互動式實作

Python 列表 append + pop(0) 可模擬佇列 (FIFO),但 pop(0) 為 O(n)。本文先示範教學版列表實作,再介紹 collections.deque 真正的 O(1) 雙端佇列。

教學版:列表實作 (含互動選單)


#!/usr/bin/env python
queue = []

def enQ():
    queue.append(input('Enter new string: ').strip())

def deQ():
    if not queue:
        print('Cannot pop from an empty queue!')
    else:
        print('Removed [', queue.pop(0), ']')

def viewQ():
    print(queue)

CMDs = {'e': enQ, 'd': deQ, 'v': viewQ}

def showmenu():
    prompt = """
(E)nqueue
(D)equeue
(V)iew
(Q)uit
Enter choice: """
    while True:
        while True:
            try:
                choice = input(prompt).strip()[0].lower()
            except (EOFError, KeyboardInterrupt, IndexError):
                choice = 'q'
            print(f'\nYou picked: [{choice}]')
            if choice not in 'devq':
                print('Invalid option, try again')
            else:
                break
        if choice == 'q':
            break
        CMDs[choice]()

if __name__ == '__main__':
    showmenu()

效能陷阱:pop(0) 為 O(n)

列表底層為動態陣列,pop(0) 需將所有元素前移。資料量大時嚴重拖慢效能。

生產級:collections.deque


from collections import deque

q = deque(maxlen=100)  # 可選最大長度,自動丟棄舊資料
q.append('a')          # 右側加入 (enqueue)
q.appendleft('b')      # 左側加入
q.pop()                # 右側彈出
q.popleft()            # 左側彈出 (dequeue) - O(1)
q.extend(['x','y'])    # 批次加入
q.rotate(3)            # 循環旋轉

適用場景對比

實作enqueuedequeue記憶體適用場景
list + pop(0)O(1)O(n)低教學、極小資料量
collections.dequeO(1)O(1)中生產環境、高頻佇列
queue.QueueO(1)O(1)中多執行緒安全、阻塞操作
asyncio.QueueO(1)O(1)中非同步協程

多執行緒安全佇列範例


import queue, threading, time

q = queue.Queue(maxsize=10)

def producer():
    for i in range(20):
        q.put(f'item-{i}')
        time.sleep(0.1)
    q.put(None)  # 停止信號

def consumer():
    while True:
        item = q.get()
        if item is None:
            break
        print(f'Consumed {item}')
        q.task_done()

threading.Thread(target=producer).start()
threading.Thread(target=consumer).start()
copyright © 萬盛學電腦網 all rights reserved