队列数据结构

date
Mar 13, 2023
slug
ja-queue-init
status
Published
tags
JavaScript数据结构与算法
Queue
JavaScript
summary
JavaScript Queue init
type
Post
class Queue{
    constructor(){
        //控制队列的大小
        this.count = 0;
        
        //追踪第一个元素
        this.lowestCount = 0;
        
        //使用对象存储元素
        this.items = {};
    }
}
  • enqueue(elements):向队列尾部添加元素
  • dequeue():移除队列的第一项，并返回被移除的元素
  • peek():返回队列中第一个元素，队列元素不变
  • isEmpty():如果队列不包含任何元素，返回 true，否则返回 false
  • size():返回队列包含的元素个数

向队列添加元素

在队列末尾添加新元素。 items 对象是键值对的集合，把 count 变量作为 items 对象中的键，对应的元素作为它的值。将元素加入队列后，将 count 变量加 1
enqueue(element){
    this.items[this.count] = element;
    this.count ++;
}

从队列移除元素

首先，检查队列是否为空。如果队列不为空就暂存队列头部的值，该元素被移除后返回。将 lowestCount 属性加 1。
​ 模拟移除元素操作：
items = {
    0:5,
    1:8
}
count = 2;
lowestCount = 0;
将键值设为 0 来获取队列头部元素（第一个添加的元素是5），删除它再返回它的值。删除第一个元素后， items 属性只会包含一个元素( 1:8 )。再次执行该方法他将会被移除，因此将 lowestCount 变量从 0 修改为 1.
dequeue(){
    if(this.isEmpty()){
        return undefined;
    }
    const result = this.items[this.lowestCount];
    delete this.items[this.lowestCount];
    this.lowestCount ++;
    return result;
}

查看队列头元素

peek(){
    if(this.isEmpty()){
        return undefined;
    }
    return this.items[this.lowestCount];
}

检查队列是否为空并获取它的长度

如果队列为空，它会返回 true，否则返回 false
isEmpty() { 
 return this.count - this.lowestCount === 0; 
}
​ 要计算队列中有多少元素，我们只需要计算 count 和 lowestCount 之间的差值即可。
假设 count 属性的值为 2，lowestCount 的值为 0。这表示在队列中有两个元素。然后， 我们从队列中移除一个元素，lowestCount 的值会变为 1，count 的值仍然是 2。现在队列中 只有一个元素了，以此类推。
所以要实现 size 方法的话，我们只需要返回这个差值即可。
size() { 
 return this.count - this.lowestCount; 
}
也可以将 isEmpty 方法写成下列形式：
isEmpty() { 
 return this.size() === 0; 
}

清空队列

将队列中的属性值重设为和构造函数中的一样
clear(){
    this.items = {};
    this.count = 0;
    this.lowestCount = 0;
}

© shallrise 2025