队列、堆栈和优先队列介绍及Redis实现

php基础

浏览数:39

2019-9-9

前言

队列、堆栈和优先队列是编程中常见的数据结构。本文首先简单介绍一下这几种数据结构,然后介绍如何用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版本

PHP版本

作者:solohunter