队列、堆栈和优先队列介绍及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)
redis支持的数据结构队列批量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

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。