当前位置： 首页 > article >正文

支持分页的环形队列

article 2024/10/2 1:30:40

支持分页的环形队列

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

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

源码

-- 创建一个分页的环形队列
local PageCircularQueue = {}
PageCircularQueue.__index = PageCircularQueue

local 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_pages
	self.page_capacity = page_capacity
	self.pages = {} -- 存储每个页的数据
	for i = 1, max_pages do
		self.pages[i] = {}
	end
	self.head_page = 1
	self.tail_page = 1
	self.head = 1
	self.tail = 0
	self.max_size = self.max_pages * self.page_capacity
	self.size = 0
	return self
end

-- 向队列中添加数据
function PageCircularQueue:enqueue(value)
	if value == nil then
		INFO("PageCircularQueue enqueue value is nil")
		return false
	end

	if self.size == self.max_size then
		-- 队列已满，覆盖最旧的元素
		if self.head == self.page_capacity then
			self.head = 1
			self.head_page = (self.head_page % self.max_pages) + 1
		else
			self.head = (self.head % self.page_capacity) + 1
		end
	else
		self.size = self.size + 1
	end

	self.tail = (self.tail % self.page_capacity) + 1
	self.pages[self.tail_page][self.tail] = value
	if self.tail == self.page_capacity then
		self.tail_page = (self.tail_page % self.max_pages) + 1
	end
	
	return true
end

-- 从队列中移除数据
function PageCircularQueue:dequeue()
	if self.size == 0 then
		return nil
	end

	local value = self.pages[self.head_page][self.head]
	-- self.pages[self.head_page][self.head] = nil  -- 因为会返回raw elements做遍历重建，删除仅做游标移动，不真正删除元素，保障为数组格式

	if self.head == self.page_capacity then
		self.head = 1
		self.head_page = (self.head_page % self.max_pages) + 1
	else
		self.head = (self.head % self.page_capacity) + 1
	end

	self.size = self.size - 1
	return value
end

-- 获取头元素
function PageCircularQueue:peek()
	if self.size == 0 then
		return nil
	end

	return self.pages[self.head_page][self.head]
end

-- 获取尾元素
function PageCircularQueue:reverse_peek()
	if self.size == 0 then
		return nil
	end

	local tail_page, tail = self.tail_page, self.tail
	if self:isFull() and self.tail == self.page_capacity then
		tail_page = self.head_page
		local tail = self.head - 1
		if tail == 0 then
			tail = self.page_capacity
			tail_page = (self.head_page + self.max_pages - 1) % self.max_pages
			if tail_page == 0 then
				tail_page = self.max_pages
			end
		end
	end
	return 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 then
		return false, "page index out of bounds " .. page_index
	end

	page_index = (self.head_page + page_index - 2) % self.max_pages + 1

	local elems = {}
	local index = self.head
	for i = 1, self.page_capacity do
		local target = self.pages[page_index][index]
		if not target then break end
		
		elems[i] = target
		if index == self.page_capacity then
			index = 1
			page_index = (page_index % self.max_pages) + 1
		else
			index = (index % self.page_capacity) + 1
		end
	end

	return true, readonly(elems)
end

-- size可用于计算是否还有下一页
function PageCircularQueue:getPage(page_index)
	if page_index < 1 or page_index > self.max_pages then
		return false, "page index out of bounds " .. page_index
	end

	
	local begin_page_index = (self.head_page + page_index - 2) % self.max_pages + 1
	local end_page_index = nil
	-- 需额外多发下一页
	if self.head ~= 1 then
		end_page_index = (begin_page_index % self.page_capacity) + 1
	end

	return 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
end


return PageCircularQueue

--[[
	示例1：
	for i = 1, 115 do
		self:enqueue(i)
	end

	local res, page_elems = self:getRawPage(1)
	for k, v in ipairs(page_elems) do
		DEBUG("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 do
		queue:enqueue(i)
	end

	local res, head, page_capacity, page1, page2, size = queue:getPage(1)
	if head == 1 then
		for k, v in ipairs(page1) do
			DEBUG("k_v==> ", k, inspect(v))	
		end
	else
		for i = head, page_capacity do
			DEBUG("k_v==> ", page1[i])	
		end

		if next(page2) then
			local tail = (page_capacity + head) % page_capacity
			for i = 1, tail do
				DEBUG("k_v==> ", page2[i])	
			end
		end
	end

	local 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.kler.cn/news/328212.html

相关文章：

  • SqlSugar使用
  • JMeter 性能测试基本过程及示例
  • Spring Web MVC课后作业
  • [前端][easyui]easyui select 默认值
  • Java 编码系列：泛型详解与面试题解析
  • 探索Android折叠屏设备的分屏适配
  • 熔断降级 请求合并 请求缓存 线程池隔离 信号量隔离 openfeign整合Hystrix
  • 2024年10月CISAW课程安排
  • 预处理详解
  • 深入浅出MongoDB（三）
  • Linux gadget 模拟触控屏 支持多点触控
  • 【监控体系搭建三】Docker部署PrometeusGrafana
  • Linux网络命令：用于管理和查询系统名称解析器（DNS）的实用工具resolvectl详解
  • 【湖南步联科技身份证】 身份证读取与酒店收银系统源码整合———未来之窗行业应用跨平台架构
  • TypeScript 设计模式之【状态模式】
  • JavaScript Set基础与实战应用
  • 基于大数据的健身器材销售数据分析及可视化系统
  • Python：lambda 函数详解 以及使用
  • 如何在本地和远程删除 Git 分支
  • SQL，将多对多的关联记录按行输出
  • Qt Creator安卓环境配置【筑基篇】
  • 数据结构-4.1.特殊矩阵的压缩存储
  • 【STM32单片机_(HAL库)】4-3-2【定时器TIM】测量按键按下时间1——编程实现捕获功能
  • 在Unity编辑器中实现组件的复制与粘贴：完整指南
  • Vue3学习（六）Vue3 + ts几种写法
  • 深入工作流调度的内核
  • 等保测评：企业数字安全的坚实盾牌
  • [Docker学习笔记]利用Dockerfile创建镜像
  • 无人机之编队控制篇
  • 速盾：cdn是怎么加速视频的？