企业形象网站怎么做,青浦网站建设公司,网站图片放大特效怎么做,h5响应式网站上海队列#xff08;Queue#xff09;是一种先进先出#xff08;First In First Out, FIFO#xff09;的数据结构#xff0c;它按照元素进入的顺序来处理元素。队列的基本操作包括#xff1a;
enqueue#xff1a;在队列的末尾添加一个元素。dequeue#xff1a;移除队列的第…队列Queue是一种先进先出First In First Out, FIFO的数据结构它按照元素进入的顺序来处理元素。队列的基本操作包括
enqueue在队列的末尾添加一个元素。dequeue移除队列的第一个元素并返回被移除的元素。front 或 peek返回队列的第一个元素但不移除它。isEmpty检查队列是否为空。size返回队列中元素的数量。
数组实现队列
内存连续性数组在内存中是连续分配的这有助于利用现代处理器的缓存机制提高访问速度。动态扩容数组需要预先定义大小或动态扩容。动态扩容涉及到创建新数组并复制旧数组元素的操作这个操作的时间复杂度为O(n)。插入和删除操作在队列末尾插入元素enqueue的时间复杂度为O(1)但在队列开头删除元素dequeue时由于需要移动所有后续元素时间复杂度也为O(n)。不过如果只在数组末尾进行操作这个复杂度可以降低到O(1)。
class Queue {contructor(){this._queue [];}isEmty() {return this._queue.length 0;}enqueue(value) {this._queue.push(value);}dequeue() {if (this.isEmty()) {return undefined;}return this._queue.shift();}size() {return this._queue.length;}peek() {if (this.isEmty()) {return undefined;}return this._queue[0];}
}链表实现队列
内存分配链表节点在内存中可以分散分配不需要连续的内存空间。动态大小链表可以根据需要动态地分配节点不需要担心扩容问题。插入和删除操作在链表队列的末尾插入元素enqueue和从头部删除元素dequeue的时间复杂度都为O(1)因为只需要改变指针的指向。额外开销链表操作涉及到额外的指针操作可能会有一些性能开销尤其是在js中对象和指针的处理通常比原始数据类型慢。
class Node {constructor(value){this.value value;this.next null;}
}class Queue {contructor(){this._front nullthis._rear nullthis._size 0}isEmty() {return this._size 0;}size() {return this._size;}dequeue() {if (this.isEmty()) {return undefined;}this._size--const removeNode this._frontthis._front this._front.nextif (this.isEmty()) {this._rear null}return removeNode.value;}enqueue(value) {const newNode new Node(value)if (this.isEmty()) {this._front newNodethis._rear newNode} else {this._rear.next newNodethis._rear newNode}this._size}peek() {if (this.isEmty()) {return undefined;}return this._front.value;}
}
