PushQueue

推入队列,循环数组实现

当前为 2021-09-25 提交的版本,查看 最新版本

此脚本不应直接安装。它是供其他脚本使用的外部库,要使用该库请加入元指令 // @require https://update.gf.qytechs.cn/scripts/432936/973688/PushQueue.js

  1. /* exported PushQueue */
  2. /**
  3. * PushQueue
  4. *
  5. * 推入队列,循环数组实现。
  6. * @template T 数据类型
  7. * @version 1.0.0.20210925
  8. * @author Laster2800
  9. * @see {@link https://gitee.com/liangjiancang/userscript/tree/master/lib/PushQueue PushQueue}
  10. */
  11. class PushQueue {
  12. /** @type {number} 起始元素位置(指向起始元素后方) */
  13. index = 0
  14. /** @type {number} 队列长度 */
  15. size = 0
  16. /** @type {number} 最大长度 */
  17. maxSize = 0
  18. /** @type {number} 容量 */
  19. capacity = 0
  20. /** @type {T[]} 内部数据 */
  21. data = null
  22.  
  23. /**
  24. * @param {number} maxSize 队列的最大长度,达到此长度后继续推入数据,将舍弃末尾处的数据
  25. * @param {number} [capacity=maxSize] 容量,即循环数组的长度,不能小于 maxSize
  26. */
  27. constructor(maxSize, capacity) {
  28. this.maxSize = maxSize
  29. if (!capacity || capacity < maxSize) {
  30. capacity = maxSize
  31. }
  32. this.capacity = capacity
  33. this.data = new Array(capacity)
  34. }
  35.  
  36. /**
  37. * 设置推入队列的最大长度
  38. * @param {number} maxSize 队列的最大长度,不能大于 capacity
  39. */
  40. setMaxSize(maxSize) {
  41. if (maxSize > this.capacity) {
  42. maxSize = this.capacity
  43. }
  44. if (maxSize < this.size) {
  45. this.size = maxSize
  46. }
  47. this.maxSize = maxSize
  48. this.gc()
  49. }
  50.  
  51. /**
  52. * 重新设置推入队列的容量
  53. * @param {number} capacity 容量
  54. */
  55. setCapacity(capacity) {
  56. if (this.maxSize > capacity) {
  57. this.maxSize = capacity
  58. }
  59. if (this.size > capacity) {
  60. this.size = capacity
  61. }
  62. // no need to gc() here
  63. const data = this.toArray().reverse()
  64. this.capacity = capacity
  65. this.index = data.length
  66. data.length = capacity
  67. this.data = data
  68. }
  69.  
  70. /**
  71. * 向队列中推入数据,若队列已达到最大长度,则舍弃末尾处数据
  72. * @param {T} value 推入队列的数据
  73. */
  74. push(value) {
  75. this.data[this.index] = value
  76. this.index += 1
  77. if (this.index >= this.capacity) {
  78. this.index = 0
  79. }
  80. if (this.size < this.maxSize) {
  81. this.size += 1
  82. }
  83. if (this.maxSize < this.capacity && this.size === this.maxSize) { // maxSize 等于 capacity 时资源刚好完美利用,不必回收资源
  84. let release = this.index - this.size - 1
  85. if (release < 0) {
  86. release += this.capacity
  87. }
  88. this.data[release] = null
  89. }
  90. }
  91.  
  92. /**
  93. * 将队列末位处的数据弹出
  94. * @returns {T} 弹出的数据
  95. */
  96. pop() {
  97. if (this.size > 0) {
  98. let index = this.index - this.size
  99. if (index < 0) {
  100. index += this.capacity
  101. }
  102. this.size -= 1
  103. const result = this.data[index]
  104. this.data[index] = null
  105. return result
  106. }
  107. }
  108.  
  109. /**
  110. * 获取第 `n` 个元素(范围 `[0, size - 1]`)
  111. * @param {number} n 元素位置
  112. * @returns {T} 第 `n` 个元素
  113. */
  114. get(n) {
  115. if (this.size > 0 && n >= 0) {
  116. let index = this.index - n - 1
  117. if (index < 0) {
  118. index += this.capacity
  119. }
  120. return this.data[index]
  121. }
  122. }
  123.  
  124. /**
  125. * 设置第 `n` 个元素的值为 `value`(范围 `[0, size - 1]`,且第 `n` 个元素必须已存在)
  126. * @param {number} n 元素位置
  127. * @param {T} value 要设置的值
  128. * @returns {boolean} 是否设置成功
  129. */
  130. set(n, value) {
  131. if (n <= this.size - 1 && n >= 0) {
  132. let index = this.index - n - 1
  133. if (index < 0) {
  134. index += this.capacity
  135. }
  136. this.data[index] = value
  137. return true
  138. } else {
  139. return false
  140. }
  141. }
  142.  
  143. /**
  144. * 使用数组初始化推入队列
  145. * @param {Array<T>} array 初始化数组
  146. */
  147. fromArray(array) {
  148. if (this.maxSize < array.length) {
  149. this.data = array.slice(0, this.maxSize).reverse()
  150. } else {
  151. this.data = array.reverse()
  152. }
  153. this.index = this.data.length
  154. if (this.index >= this.capacity) {
  155. this.index = 0
  156. }
  157. this.size = this.data.length
  158. this.data.length = this.capacity
  159. }
  160.  
  161. /**
  162. * 将推入队列以数组的形式返回
  163. * @param {number} [maxLength=size] 读取的最大长度
  164. * @param {number} [offset=0] 起始点
  165. * @returns {Array<T>} 队列数据的数组形式
  166. */
  167. toArray(maxLength = this.size, offset = 0) {
  168. if (offset < 0) {
  169. offset = 0
  170. }
  171. if (offset + maxLength > this.size) {
  172. maxLength = this.size - offset
  173. }
  174. const ar = []
  175. let start = this.index - offset
  176. if (start < 0) {
  177. start += this.capacity
  178. }
  179. let end = start - maxLength
  180. for (let i = start - 1; i >= end && i >= 0; i--) {
  181. ar.push(this.data[i])
  182. }
  183. if (end < 0) {
  184. end += this.capacity
  185. for (let i = this.capacity - 1; i >= end; i--) {
  186. ar.push(this.data[i])
  187. }
  188. }
  189. return ar
  190. }
  191.  
  192. /**
  193. * 清理内部无效数据,释放内存
  194. */
  195. gc() {
  196. if (this.size > 0) {
  197. const start = this.index - 1
  198. let end = this.index - this.size
  199. if (end < 0) {
  200. end += this.capacity
  201. }
  202. if (start >= end) {
  203. for (let i = 0; i < end; i++) {
  204. this.data[i] = null
  205. }
  206. for (let i = start + 1; i < this.capacity; i++) {
  207. this.data[i] = null
  208. }
  209. } else {
  210. for (let i = start + 1; i < end; i++) {
  211. this.data[i] = null
  212. }
  213. }
  214. } else {
  215. this.data = new Array(this.capacity)
  216. }
  217. }
  218.  
  219. /**
  220. * 标准迭代器:`item`
  221. * @returns {IterableIterator<T>}
  222. */
  223. [Symbol.iterator]() {
  224. const iterator = this.entries()
  225. return {
  226. next: () => {
  227. const n = iterator.next()
  228. if (!n.done) {
  229. n.value = n.value[1]
  230. }
  231. return n
  232. },
  233. }
  234. }
  235.  
  236. /**
  237. * 迭代器:`[index, item]`
  238. * @returns {IterableIterator<[index: number, item: T]>}
  239. */
  240. entries() {
  241. let current = this.index - 1
  242. let end = this.index - this.size
  243. return {
  244. next: () => {
  245. if (current < 0 && end < 0) {
  246. current += this.capacity
  247. end += this.capacity
  248. }
  249. if (current >= end && current >= 0) {
  250. const n = { value: [current, this.data[current]], done: false }
  251. current -= 1
  252. return n
  253. } else {
  254. return { done: true }
  255. }
  256. },
  257.  
  258. [Symbol.iterator]() { return this },
  259. }
  260. }
  261. }

QingJ © 2025

镜像随时可能失效,请加Q群300939539或关注我们的公众号极客氢云获取最新地址