佇列、堆疊和優先佇列介紹及Redis實現
前言
佇列、堆疊和優先佇列是程式設計中常見的資料結構。本文首先簡單介紹一下這幾種資料結構,然後介紹如何用Redis實現這些資料結構。
資料結構簡介
佇列
普通佇列有以下幾個特性
- 先進先出(FIFO)
- 支援PUSH/POP,PUSH從尾端增加元素,POP從前端彈出元素
- 容量不受限制
從普通佇列可以衍生出定長佇列 ,它比普通佇列多出以下特性
- 有固定的容量(最大長度)
- 向滿載的佇列PUSH會失敗
從定長佇列可以衍生出可溢位的定長佇列 ,它比定長佇列多出以下特性
- 向滿載的佇列PUSH會成功,但前端的元素會被擠出
以上三種佇列都是單向佇列 ,只能從尾端PUSH,從前端POP。它們又分別可以衍生出各自的雙向 版本。
雙向佇列/定長佇列/可溢位的定長佇列
比單向版本多處以下特性
- PUSH/POP均可以從前端/後端進行
- 對於可溢位的雙向佇列,滿載時從一端PUSH,會從另一端將元素擠出
堆疊
普通堆疊有以下特性
- 後進先出 (LIFO)
- 支援PUSH/POP,從尾端追加/彈出元素
- 容量不受限制
衍生出的定長堆疊 多處以下特性
- 容量固定
- 向滿載的堆疊PUSH會失敗
定長堆疊沒有可溢位版本,因為堆疊只能從尾端PUSH/POP。
優先佇列
和普通佇列相比,優先佇列中的元素都有一個優先順序,佇列中的元素按優先順序排序,優先順序高的元素先被彈出。類似佇列,優先佇列有三種版本,他們的特性也類似佇列。
- 普通優先佇列
- 定長優先佇列
- 可溢位的定長優先佇列
其中可溢位的優先佇列,滿載時的PUSH操作會將優先順序低的元素擠出。
Redis實現
思路
佇列和堆疊都可以用Redis的list資料型別實現,因為list支援以下操作
- lpush/rpush,從左側/右側追加元素
- lpop/rpop,從左側/右側彈出元素
- llen,獲取佇列的長度
- lindex,獲取某個位置的元素
定長和可溢位版本,Redis原生的list型別無法實現,需要寫一點程式碼實現它們。Redis支援Lua指令碼程式設計,我們就用它來實現這些版本。
優先佇列可以用Redis的ZSET(SORTED SET)資料型別實現,ZSET為有序集合,集合中的元素都有一個分值,分值越低優先順序越高。我們同樣用Lua指令碼實現定長和可溢位版本。ZSET支援以下操作
- zadd,向集合增加元素
- zrange,按優先順序範圍獲取元素
- zrem,從集合中刪除元素
實現細節
佇列
rpush + lpop即可實現一個普通佇列。
對於定長佇列,push前需檢查佇列長度,如果滿載則返回錯誤碼,否則追加元素。
對於可溢位的定長佇列,push後檢查佇列長度,如果長度超出容量,則從前端將元素彈出。
堆疊和雙向佇列 的實現細節與之類似。
優先佇列
- PUSH操作用zadd實現
- POP操作用zrange + zrem實現
增強特性
為了充分利用Redis的強大之處,我們還可以增加一些有趣的特性
- 佇列批量PUSH:list的push命令原生支援批量追加元素,而且時間複雜度為O(1)
- 佇列批量POP:list的pop命令不支援批量彈出,需要我們用迴圈實現批量POP
- 優先佇列批量PUSH:zset的zadd命令支援批量追加元素
- 優先佇列批量POP:zrange批量獲取 + zrem迴圈刪除
- 檢查元素是否在佇列中:lindex獲取某個位置的元素,迴圈檢查即可得到結果
- 檢查元素是否在優先佇列中:zrank獲取某個元素的優先順序順序,即可得到結果
程式碼例項
我們看一下如何用Lua指令碼實現可溢位的定長佇列
PUSH
local cap=tonumber(ARGV[1]) for i,k in ipairs(ARGV) do if i > 1 then redis.call('rpush',KEYS[1],k) end end local len=redis.call('llen',KEYS[1]) local o={} while len > cap do o[#o + 1]=redis.call('lpop',KEYS[1]) len=len - 1 end return { len,o }
POP
local o={} for i=1,tonumber(ARGV[1]) do o[#o + 1]=redis.call('lpop',KEYS[1]) end return o
程式碼已開源至github
PHP版本