1. 队列是什么?
队列是一种特殊的线性表, 特殊之处在于它只允许在表的前端 (front) 进行删除操作, 而在表的后端 (rear) 进行插入操作, 和栈一样, 队列是一种操作受限制的线性表. 进行插入操作的端称为队尾, 进行删除操作的端称为队头. 队列中没有元素时, 称为空队列.
2. 队列经常出现在我们的生活中
上面就是一个排队吃饭的队列, 遵循先进先打饭 (先进先出), 后到没饭(后进后出) 的原则. 那只吃饭最积极的黑狗就是队列的头部(head), 最后面那只叼着黑碗的傻狗就是尾部(tail), 队列的长度是 6.
3. 队列具有那些属性和方法呢?
头部指针: 存储头部元素的下标, 初始化时为 0
尾部指针: 存储尾部元素的下一个位置的下标, 初始化时为 0
长度: 存储队列的长度
初始化空队列
入队操作 enqueue()
出队操作 dequeue()
读队头元素 peek()
判断队列是否为空 isEmpty()
4. 我们来实现一下
初始化一个空的队列
- 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(), 读者感兴趣可以自己试试.
good night!
来源: http://www.qdfuns.com/article/50934/e989906e92561c87985818dd9d43bf55.html