线性数据结构-队列
队列（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;}
}