队列
2023-09-11 14:15:02 时间
在计算机科学中, 一个 队列(queue) 是一种特殊类型的抽象数据类型或集合。集合中的实体按顺序保存。
队列基本操作有两种: 向队列的后端位置添加实体,称为入队,并从队列的前端位置移除实体,称为出队。
队列中元素先进先出 FIFO (first in, first out)的示意
复杂度
时间复杂度
获取:O(n)
查询:O(n)
插入:O(1)
删除:O(1)
空间复杂度
O(n)
代码实现
Queue.js
import LinkedList from '../linked-list/LinkedList'; export default class Queue {//队列类,队列其实就是一端添加,一端删除的链表 constructor() { // We're going to implement Queue based on LinkedList since the two // structures are quite similar. Namely, they both operate mostly on // the elements at the beginning and the end. Compare enqueue/dequeue // operations of Queue with append/deleteHead operations of LinkedList. this.linkedList = new LinkedList();//linkedList属性是一个链表对象 } /** * @return {boolean} */ isEmpty() {//返回真假值,队列是否是空的 return !this.linkedList.head; } /** * Read the element at the front of the queue without removing it. * @return {*} */ peek() {//读取队列的头节点 if (!this.linkedList.head) { return null; } return this.linkedList.head.value; } /** * Add a new element to the end of the queue (the tail of the linked list). * This element will be processed after all elements ahead of it. * @param {*} value */ enqueue(value) {//入队,在队列的结尾加入新值 this.linkedList.append(value); } /** * Remove the element at the front of the queue (the head of the linked list). * If the queue is empty, return null. * @return {*} */ dequeue() {//出队,在队列的开头删除值,返回出队的值 const removedHead = this.linkedList.deleteHead(); return removedHead ? removedHead.value : null; } /** * @param [callback] * @return {string} */ toString(callback) {//返回队列的字符串值的数组的字符串 // Return string representation of the queue's linked list. return this.linkedList.toString(callback); } }