前言
队列, 堆栈和优先队列是编程中常见的数据结构. 本文首先简单介绍一下这几种数据结构, 然后介绍如何用 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
Python 版本 https://github.com/limen/fastrq
PHP 版本 https://github.com/limen/fastrq-php
来源: http://www.jianshu.com/p/7450c4836de5