×

学习下数组队列的一些基本知识

作者:andy0012018.08.28来源:Web前端之家浏览:22681评论:0
关键词:队列

500.jpg

闲余之时,学习下数组队列的一些基本知识。我们知道,队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(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前端之家编辑修改或补充,转载请注明出处和本文链接:
https://www.jiangweishan.com/article/js2348f0df.html

网友评论文明上网理性发言 已有0人参与

发表评论: