个性化阅读
专注于IT技术分析

JavaScript基本数据结构:队列基本原理和实现

和栈一样,队列也是线性结构,它有特定的操作和执行顺序,其基本特征是:先进先出(FIFO),一个生活中的例子是:去餐厅排队点餐,在前面的客户优先下单或首先得到服务。其中删除操作和栈不同,栈是先删除最近添加的数据,而队列则是删除最先添加如队列中的数据。

JavaScript队列的基本原理和实现

队列的主要操作

队列的主要操作如下:

Enqueuer:添加一个数据到队列的队尾,如果队列已满,则不再进行操作,提示添加数据溢出。

Dequeue:从队列的队头移除数据,如果队列为空,则返回null。

Front/head:获取最早添加到队头的数据。

Rear/tail:获取最新添加到队尾的数据。

JavaScript队列基本原理和实现

队列有哪些应用?

当有任务不需要立即处理的时候,我们可以使用一个队列保存这些任务,以后处理这些任务的顺序为先进先出,其中最明显地需要队列的是BFS广度优先遍历,下面是两个使用队列的例子:

  1. 当资源在多个使用者之间共享时,例如CPU调度、磁盘调度。
  2. 当数据在两个进程之间异步传输时(数据不一定以与发送相同的速率接收),例子包括IO缓冲区、管道、文件IO等。

使用数组实现队列

为了实现队列,我们需要跟踪两个索引:front和rear,往队尾添加新数据,从队头将数据出队。如果只是简单增加这两个索引,可能会有问题,front可能会达到数组的末端,解决办法是使用循环的方式,例如当添加新数据的时候,rear递增,如果rear超过数组长度,而数组又未满,让rear跳到数组的前面,如果让rear跳到前面呢?使用取模rear%capacity即可。

下面实现的队列的各个操作的时间复杂度为O(1)。

下面是使用数组实现队列的源码:

// 使用数组实现队列

// 队列声明
function ArrayQueue(capacity){
    if(capacity < 3){
        console.log("capacity is too small.");
        return null;
    }
    this.capacity = capacity;
    this.size = 0;
    this.front = 0;
    this.rear = capacity - 1;
    this.array = new Array(capacity);
}

// 检查队列是否已满
ArrayQueue.prototype.isFull = function(){
    return this.size == this.capacity;
}

// 检查队列是否为空
ArrayQueue.prototype.isEmpty = function(){
    return this.size == 0;
}

// 入队enqueue操作
ArrayQueue.prototype.enqueue = function(value){
    if(this.isFull()){
        console.log("overflow: could not enqueue value.");
        return;
    }
    this.rear = ++this.rear % this.capacity;
    this.array[this.rear] = value;
    this.size++;
}

// 出队dequeue操作
ArrayQueue.prototype.dequeue = function(){
    if(this.isEmpty())
        return null;
    var value = this.array[this.front];
    this.front = ++this.front % this.capacity;
    this.size--;
    return value;
}

// front查看队头的数据
ArrayQueue.prototype.head = function(){
    if(this.isEmpty())
        return null;
    return this.array[this.front];
}

// rear查看最新添加的数据
ArrayQueue.prototype.tail = function(){
    if(this.isEmpty())
        return null;
    return this.array[this.rear];
}

// 调用实例
var queue = new ArrayQueue(10);
for(var i = 0;i < 10;i++)
    queue.enqueue(i * i * i + 9);
console.log(queue.head());
console.log(queue.tail());
var str = "";
while(!queue.isEmpty()){
    str += queue.dequeue() + " ";
}
console.log(str);

使用链表实现队列

上面使用数组实现队列的难点是font和rear位置的设置和变化处理,和使用数组的方式不同,使用链表则不用考虑太多,相对简单很多,也没有容量限制,只需要实现基本的队列的FIFO即可,其中下面实现的各个操作的时间复杂度也是O(1),下面是使用链表实现队列的完整源码:

// 使用链表实现队列

// 结点
function Node(value){
    this.value = value;
    this.next = null;
}

// 队列声明
function LinkedQueue(){
    this.size = 0;
    this.head = this.tail = null;
}

// 检查队列是否为空
LinkedQueue.prototype.isEmpty = function(){
    return this.size == 0;
}

// 入队操作
LinkedQueue.prototype.enqueue = function(value){
    var node = new Node(value);
    if(this.size == 0){
        this.head = this.tail = node;
        this.size++;
    }
    else{
        this.tail.next = node;
        this.tail = node;
        this.size++;
    }
}

// 出队操作
LinkedQueue.prototype.dequeue = function(){
    if(this.isEmpty())
        return null;
    var head = this.head;
    var value = head.value;
    this.head = head.next;
    head = null;
    this.size--;
    return value;
}

// 获取队头元素
LinkedQueue.prototype.front = function(){
    if(this.isEmpty())
        return null;
    return this.head.value;
}

// 获取队尾元素
LinkedQueue.prototype.rear = function(){
    if(this.isEmpty())
        return null;
    return this.tail.value;
}


// 调用实例
var queue = new LinkedQueue(10);
for(var i = 0;i < 10;i++)
    queue.enqueue(i * i * i + 9);
console.log(queue.front());
console.log(queue.rear());
var str = "";
while(!queue.isEmpty()){
    str += queue.dequeue() + " ";
}
console.log(str);
赞(0)
未经允许不得转载:srcmini » JavaScript基本数据结构:队列基本原理和实现

评论 抢沙发

评论前必须登录!