学习下数组队列的一些基本知识 - Web前端

闲余之时，学习下数组队列的一些基本知识。我们知道，队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

队列具有那些属性和方法呢？

• 头部指针：存储头部元素的下标，初始化时为0

• 尾部指针：存储尾部元素的下一个位置的下标，初始化时为0

• 长度：存储队列的长度

• 初始化空队列

• 入队操作enqueue()

• 出队操作dequeue()

• 读队头元素peek()

• 判断队列是否为空iSEMpty()

例子

初始化一个空的队列：

class Queue {
    constructor () {
        this.head = 0 // 指向头部的下标
        this.tAIl = 0 // 指向尾部的下标加一
        this.data = [null] // 第一个位置不做存储位
        this.length = 0 // 数据的长度
    }
}

初始化的时候，head和tail都指向0。

入队操作

当队列为空的时候，head指向第一个队列元素的下标（不是data里面的Null，而是它的下一个元素），tail指向第一个队列元素的下一个位置的下标。
当队列不为空的时候，head不变，tail往后移动一位。
代码如下：

class Queue {
    constructor () {
        this.head = 0 // 指向头部的下标
        this.tail = 0 // 指向尾部的下标加一
        this.data = [null] // 第一个位置不做存储位
        this.length = 0 // 数据的长度
    }

    enqueue (key) { // 入队
        if (this.head === 0) { // 队列为空
            this.head = 1
            this.tail = 2
        } else {
            this.tail ++
        }
        this.length ++
        this.data.push(key)
    }
}

我们创建一个新的队列，并添加三个元素。

const queue = new Queue()
queue.enqueue('聪明的狗')
queue.enqueue('二狗')
queue.enqueue('傻狗')
console.log(queue)

下面是打印出来的结果：队列长度为3，head为1，tail为4

出队操作
如果队列长度为0，直接返回；如果队列长度为1，head和tail重置为0；队列长度大于1的时候，head指针往后移，即加一。tail指针不变。最后返回出队的那只狗。
我们来实现一下：

class Queue {
    constructor () {
        this.head = 0 // 指向头部的下标
        this.tail = 0 // 指向尾部的下标加一
        this.data = [null] // 第一个位置不做存储位
        this.length = 0 // 数据的长度
    }

    dequeue () { // 出队操作
        if (this.length === 0) return false // 空队列直接返回
        let head = this.data[this.head] // 获取头部元素

        if (this.length === 1) { // 队列只有一个元素
            this.head = 0
            this.tail = 0
            this.data = [null]
        } else {
            this.data[this.head] = null
            this.head ++
        }
        this.length --

        return head
    }
}

我们在之前的队列基础上进行出队操作：

const queue = new Queue()
queue.enqueue('聪明的狗')
queue.enqueue('二狗')
queue.enqueue('傻狗')
queue.dequeue()
console.log(queue)

下面是打印的结果：

可以看见，早排队的狗儿有饭吃。‘聪明的狗’出队了，head加1，tail不变
我们再执行两次 dequeue()操作。

队列为空了 其它操作
还有一些其它方法比如isempty(),读者感兴趣可以自己试试。

标签：队列数组基本知识Web