闲余之时,学习下数组队列的一些基本知识。我们知道,队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(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(),读者感兴趣可以自己试试。
网友评论文明上网理性发言 已有0人参与
发表评论: