Python雙端隊列deque的實現
前言
雙端隊列deque支持從任意一端增加和刪除元素。其中,棧和隊列就是雙端隊列的退化形式,它們的輸入輸出被限制在某一端。
基本用法
首先,我們來看看容器collections.deque()函數的基本用法。具體代碼如下所示:
import collections c = collections.deque('abcdefg') print("輸出雙端隊列:", c) print("雙端隊列的長度:", len(c)) print("前端值:", c[0]) print("末端值:", c[-1])
運行之後,效果如下:
填充
因為它是雙端隊列,所以該隊列支持從任意一端添加或刪除元素。下面,我們來分別實現兩端的添加和刪除操作,具體代碼如下所示:
import collections c = collections.deque() #不使用構造函數初始化 c.extend("abcdefg") #右端(末端)添加 c.append('h') print(c) #左端添加(前端)添加 c.extendleft('i') print(c) #末尾刪除 c.pop() print(c) #前端刪除 c.popleft() print(c) #隨便刪除 c.remove('c') print(c)
運行之後,效果如下:
和使用list數組一樣,通過append進行添加,默認append從右端(末端)開始添加。如果想從前端開始添加,可以使用extendleft()函數。而刪除可以使用pop()函數從右端(末尾)開始刪除,popleft()從左端開始刪除。至於隨意刪除,可以直接使用remove()。
線程安全
雙端隊列是線程安全的,在實際應用中,我們可以在不同線程中同時從兩端消費隊列的內容。具體代碼如下所示:
import collections import threading import time def getItem(lor, method): while True: try: next = method() except IndexError: break else: print("{0}:{1}".format(lor, next)) time.sleep(0.1) print('{0}:None'.format(lor)) return c = collections.deque("abcdefg") t1 = threading.Thread(target=getItem, args=('Left', c.popleft)) t2 = threading.Thread(target=getItem, args=('Right', c.popleft)) t1.start() t2.start() t1.join() t2.join()
運行之後,效果如下:
上面代碼中,兩個線程交替刪除元素,直至雙端隊列deque為空。可以看到,沒有重復的元素被刪除。
旋轉
雙端隊列deque的另一個很有用的方面是可以按任意一個方向旋轉,從而跳過一些元素。
比如將deque雙端隊列向右旋轉(使用一個正旋轉值)會從右端取元素,並把它們移動到左端。同理,向左旋轉(負值)則從左端將元素移值右端。
我們來看一端代碼就非常明白瞭:
import collections a = collections.deque("abcdefg") b = collections.deque("abcdefg") c = collections.deque("abcdefg") print(a) b.rotate(2) print(b) c.rotate(-2) print(c)
運行之後,效果如下:
可以看到,b的前兩個字母被移動到前面。c的前兩個字母被移動到後面。
限制雙端隊列大小
在實際的雙端隊列操作中,我們可以設置雙端隊列deque實例的最大長度,使它不會超過這個大小。這種操作在查找長度不確定的流中最後n個元素非常有用。
我們先來看一段代碼:
import collections import random c1 = collections.deque(maxlen=5) c2 = collections.deque(maxlen=3) for i in range(8): r = random.randint(1, 100) print(r) c1.append(r) c2.append(r) print(c1) print(c2)
運行之後,效果如下:
從上面代碼我們認識到,設置瞭雙端隊列deque最大長度,那麼不管你添加多少數據,長度永遠不變。同時,多餘添加的數據會依次按先後順序頂替掉最前面(左端)的值。
到此這篇關於Python雙端隊列deque的實現的文章就介紹到這瞭,更多相關Python雙端隊列deque內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!
推薦閱讀:
- 深入瞭解Python的多線程基礎
- Python threading和Thread模塊及線程的實現
- python threading模塊的使用指南
- Python多線程即相關理念詳解
- python基礎之並發編程(一)