支持分页的环形队列

news/2024/12/21 22:43:05/

支持分页的环形队列

  • 源码
  • 解析
    • PageCircularQueue 类
    • readonly 函数
    • PageCircularQueue.new 函数
    • PageCircularQueue:enqueue 函数
    • PageCircularQueue:dequeue 函数
    • PageCircularQueue:peek 函数
    • PageCircularQueue:reverse_peek 函数
    • PageCircularQueue:isFull 函数
    • PageCircularQueue:isEmpty 函数
    • PageCircularQueue:getSize 函数
    • PageCircularQueue:getRawPage 函数
    • PageCircularQueue:getPage 函数

最近我因工作需要使用环形队列,并在常规环形队列上拓展为支持分页环形队列,用于高效地管理大量数据,支持高效的元素添加、删除及分页数据的访问。通过分页的方式,它可以有效地管理大规模的数据集合

源码

lua">-- 创建一个分页的环形队列
local PageCircularQueue = {}
PageCircularQueue.__index = PageCircularQueuelocal function readonly(t)local mt = {__index = t,__newindex = function (t, k, v) error("Attempt to modify read-only table", 2) end,__pairs = function () return pairs(t) end,__ipairs = function () return ipairs(t) end,__len = function () return #t end,__metatable = false}return setmetatable({}, mt)
end--tips: head指向的当前队列中最早入队的元素,tail指向的为最新入队的元素---创建新的环形队列对象
---@param max_pages number @最大页
---@param page_capacity number @每页最大数量
---@field head_page number @最新页
---@field tail_page number @最尾页
---@field head number @头元素所在页的位置
---@field tail number @尾元素所在页的位置
---@field max_size number @队列容量
---@field size number @队列长度
---@field pages table @页数据
function PageCircularQueue.new(max_pages, page_capacity)assert(max_pages > 0, "invalid max pages")assert(page_capacity > 0, "invalid page capacity")local self = setmetatable({}, PageCircularQueue)self.max_pages = max_pagesself.page_capacity = page_capacityself.pages = {} -- 存储每个页的数据for i = 1, max_pages doself.pages[i] = {}endself.head_page = 1self.tail_page = 1self.head = 1self.tail = 0self.max_size = self.max_pages * self.page_capacityself.size = 0return self
end-- 向队列中添加数据
function PageCircularQueue:enqueue(value)if value == nil thenINFO("PageCircularQueue enqueue value is nil")return falseendif self.size == self.max_size then-- 队列已满,覆盖最旧的元素if self.head == self.page_capacity thenself.head = 1self.head_page = (self.head_page % self.max_pages) + 1elseself.head = (self.head % self.page_capacity) + 1endelseself.size = self.size + 1endself.tail = (self.tail % self.page_capacity) + 1self.pages[self.tail_page][self.tail] = valueif self.tail == self.page_capacity thenself.tail_page = (self.tail_page % self.max_pages) + 1endreturn true
end-- 从队列中移除数据
function PageCircularQueue:dequeue()if self.size == 0 thenreturn nilendlocal value = self.pages[self.head_page][self.head]-- self.pages[self.head_page][self.head] = nil  -- 因为会返回raw elements做遍历重建,删除仅做游标移动,不真正删除元素,保障为数组格式if self.head == self.page_capacity thenself.head = 1self.head_page = (self.head_page % self.max_pages) + 1elseself.head = (self.head % self.page_capacity) + 1endself.size = self.size - 1return value
end-- 获取头元素
function PageCircularQueue:peek()if self.size == 0 thenreturn nilendreturn self.pages[self.head_page][self.head]
end-- 获取尾元素
function PageCircularQueue:reverse_peek()if self.size == 0 thenreturn nilendlocal tail_page, tail = self.tail_page, self.tailif self:isFull() and self.tail == self.page_capacity thentail_page = self.head_pagelocal tail = self.head - 1if tail == 0 thentail = self.page_capacitytail_page = (self.head_page + self.max_pages - 1) % self.max_pagesif tail_page == 0 thentail_page = self.max_pagesendendendreturn self.pages[tail_page][tail]
end-- 检查队列是否已满
function PageCircularQueue:isFull()return self.size >= self.max_size
end-- 检查队列是否为空
function PageCircularQueue:isEmpty()return self.size == 0
end-- 获取队列的大小
function PageCircularQueue:getSize()return self.size
end-- 获取指定页的详细数据
function PageCircularQueue:getRawPage(page_index)if page_index < 1 or page_index > self.max_pages thenreturn false, "page index out of bounds " .. page_indexendpage_index = (self.head_page + page_index - 2) % self.max_pages + 1local elems = {}local index = self.headfor i = 1, self.page_capacity dolocal target = self.pages[page_index][index]if not target then break endelems[i] = targetif index == self.page_capacity thenindex = 1page_index = (page_index % self.max_pages) + 1elseindex = (index % self.page_capacity) + 1endendreturn true, readonly(elems)
end-- size可用于计算是否还有下一页
function PageCircularQueue:getPage(page_index)if page_index < 1 or page_index > self.max_pages thenreturn false, "page index out of bounds " .. page_indexendlocal begin_page_index = (self.head_page + page_index - 2) % self.max_pages + 1local end_page_index = nil-- 需额外多发下一页if self.head ~= 1 thenend_page_index = (begin_page_index % self.page_capacity) + 1endreturn true, self.head, self.page_capacity, readonly(self.pages[begin_page_index] or {}), end_page_index and readonly(self.pages[end_page_index] or {}) or {}, self.size
endreturn PageCircularQueue--[[示例1:for i = 1, 115 doself:enqueue(i)endlocal res, page_elems = self:getRawPage(1)for k, v in ipairs(page_elems) doDEBUG("res==> ", k, inspect(v))	end只需通过getPage()将页数据同步到客户端,由客户端根据head page_capacity按需获取队列元素例:head为1,则只需变量self.pages[begin_page_index]中数据即可里:head为5,则1~6遍历self.pages[begin_page_index],7~10遍历self.pages[end_page_index]中数据示例2:local page_circular_queue = require "page_circular_queue"local queue = page_circular_queue.new(10, 10)for i = 1, 300 doqueue:enqueue(i)endlocal res, head, page_capacity, page1, page2, size = queue:getPage(1)if head == 1 thenfor k, v in ipairs(page1) doDEBUG("k_v==> ", k, inspect(v))	endelsefor i = head, page_capacity doDEBUG("k_v==> ", page1[i])	endif next(page2) thenlocal tail = (page_capacity + head) % page_capacityfor i = 1, tail doDEBUG("k_v==> ", page2[i])	endendendlocal peek = queue:peek()local reverse_peek = queue:reverse_peek()DEBUG("peek==> ", inspect(peek), inspect(reverse_peek))
]]--

解析

PageCircularQueue 类

  • PageCircularQueue 是一个表,用于表示环形队列的数据结构
  • PageCircularQueue.__index = PageCircularQueue 设置元表,允许 PageCircularQueue 的实例通过 __index 查找方法和属性

readonly 函数

  • readonly(t) 返回一个只读表,任何对表 t 的修改操作都会引发错误。这个表可以安全地暴露给外部使用者,用于限制外部修改其内容

PageCircularQueue.new 函数

这个函数用于创建一个新的 PageCircularQueue 实例

  • max_pages:最大页数,即队列的页数
  • page_capacity:每页的最大容量
  • self.pages:一个表,用于存储每页的数据。初始化时,每页都是一个空表
  • self.head_page 和 self.tail_page:分别指示队列的头页和尾页
  • self.head 和 self.tail:指示当前页内头元素和尾元素的位置
  • self.max_size:队列的总容量
  • self.size:当前队列中的元素数量

PageCircularQueue:enqueue 函数

这个方法用于向队列中添加元素

  • 如果队列已满(self.size == self.max_size),它会覆盖最旧的元素,即 head 指向的元素
  • 如果 self.head 达到当前页的最大容量(self.page_capacity),则需要将 self.head 重置为1,并且 self.head_page 移动到下一页
  • 更新 self.tail 和 self.tail_page 以插入新元素
  • self.size 增加1

PageCircularQueue:dequeue 函数

这个方法用于从队列中移除元素

  • 如果队列为空(self.size == 0),返回 nil
  • 移除 self.head_page 页中的 self.head 位置的元素
  • 更新 self.head 和 self.head_page,使其指向下一个元素
  • self.size 减少1

PageCircularQueue:peek 函数

这个方法用于查看队列的头元素

  • 如果队列为空,返回 nil
  • 否则,返回 self.pages[self.head_page][self.head]

PageCircularQueue:reverse_peek 函数

这个方法用于查看队列的尾元素

  • 如果队列为空,返回 nil
  • 否则,返回 尾元素

PageCircularQueue:isFull 函数

这个方法用于检查队列是否已满

  • 如果 self.size 大于或等于 self.max_size,返回 true,否则返回 false

PageCircularQueue:isEmpty 函数

这个方法用于检查队列是否为空

  • 如果 self.size 等于0,返回 true,否则返回 false

PageCircularQueue:getSize 函数

这个方法返回队列的当前大小,即 self.size

PageCircularQueue:getRawPage 函数

这个方法用于获取指定页的所有数据

  • page_index 需要在有效范围内(1 到 self.max_pages)
  • 计算页的实际索引 page_index,从 self.head_page 开始,读取该页的数据并返回
  • 使用 readonly 包装返回的数据,确保外部无法修改

PageCircularQueue:getPage 函数

这个方法用于获取指定页的数据及其前后的页数据

  • page_index 需要在有效范围内(1 到 self.max_pages)
  • 计算起始页的实际索引,并且如果需要,还会获取下一页的数据
  • 返回的数据被包装为 readonly 表,确保数据的安全性

http://www.ppmy.cn/news/1533368.html

相关文章

微服务jvisualvm解析部署使用全流程

1、介绍 VisualVM 是Netbeans的profile 2、启动 进入正在使用的jdk下bin目录&#xff0c;运行jvisualvm.exe。 3、选中要监控的线程 4、安装gc插件 5、插件安装报错 VisualVM: Plugins Centers 访问这个地址&#xff0c;找到对应版本再配置 https://visualvm.github.io/uc/…

Scrapy入门

Scrapy是一个用Python实现的快速、高层次的屏幕抓取和web抓取框架&#xff0c;主要用于抓取web站点并从页面中提取结构化的数据。 安装 pip install scrapy 创建Scrapy项目 使用scrapy startproject命令创建一个新的Scrapy项目。例如&#xff0c;创建一个名为myproject的项…

测试用例的进阶二

1. 按开发阶段划分 1.1 测试金字塔 从上到下&#xff0c;对于测试人员代码就是要求越来越低&#xff1b; 从下到上&#xff0c;越来越靠近用户&#xff1b; 从下到上&#xff0c;定位问题的成本越来越高&#xff1b; 1.2 单元测试(Unit Testing) 单元测试是对软件组成单元进…

开发微信小程序 基础02

WX模板 1.对比 ①标签名称不同 ②属性节点不同 ③提供类似vue的模板语法 2.模板语法 2.1数据动态绑定 2.1.1在data种定义数据 在页面对应的.js文件中&#xff0c;把数据定义到data对象中即可 例---data &#xff1a; { info : init data , msList : [{msg : hello}, { ms…

Git的相关使用(工作常用)

一、撤销的相关命令&#xff08;重要&#xff01;&#xff01;&#xff01;&#xff09; 1. 使用 git reset &#xff08;a&#xff09;软重置 如果你想撤销最近的提交&#xff0c;但保留文件的更改&#xff08;即将它们放回暂存区&#xff09;&#xff0c;可以使用&#xff1a…

第十章 MySQL主从复制搭建Docker版

目录 1.新建主服务器容器示例3307 2. 进入/mydata/mysql-master/conf目录下创建my.cnf配置 3.修改完配置后重启master实例 4.进入mysql-master容器 5.master容器实例内创建数据同步的用户 6.新建从服务器容器实例3308 7.进入/mydata/mysql-slave/conf目录下新建my.c…

C#核心(2)类和对象

前言 在上一节中&#xff0c;我们已经了解了面向对象开发的概念和原则&#xff0c;那今天&#xff0c;我们就来讲讲c#中的类。 c#中的类是我们面向对象开发使用最频繁的东西。 在未来我们要学习的unity开发中也是必不可少的。 所以希望屏幕前的你务必把这一块的知识学得扎实…

在线相亲系统:新时代的婚恋观与传统习俗的碰撞

随着互联网技术的发展&#xff0c;相亲交友平台已成为年轻人寻找伴侣的新方式。这些平台不仅改变了人们的社交习惯&#xff0c;也反映了当代婚恋观与传统习俗之间的碰撞与融合。开发h17711347205本文将探讨在线相亲系统是如何在尊重传统的基础上&#xff0c;为现代年轻人提供更…