JS版数据结构第二篇(队列)

本片博客参考到银国徽老师的《Js版数据结构与算法》

队列

队列的定义

相信通过上篇博客大家对栈有了一个大概的认识,今天我们开始对队列的学习。

我们还是先看一下百度百科上对 队列 的定义:

说白了就是队列是一种受限的线性表,''受限''体现在只能从表的前端(队头)进行删除,只能从表的后端(队尾)进行插入。接下来我还是用一个比喻更形象的说明一下我对队列的理解。

队列的理解

相信大家平时都会路过一些网红店如‘喜茶’,‘一点点’,‘BONUS’(雇人排队的行为不值得提倡:grinning:)，每次路过时都是门庭若市,我家楼下的也有一家烤肠店,每到周末都会排起很长的队伍。

图 1

这个时候排队的大家就形成了一个 队列

图片中最前面的蓝色衣服的大叔就是 队头

在最后面拍照片的我呢就是 队尾 了

这时候当大叔交完钱拿到自己的烤肠后就可以离开我们的'队列'(称为 出队 ,只能从队头离开)

如果隔壁家的小孩被馋哭了的话他也只能去我的后面开始排队(称为 入队 ,只能从队尾入队)

注意: 大叔是先去排队的,所以他也是先拿到自己的烤肠离开的,小朋友是后来的,所以他也会后拿到自己的烤肠,这也就是我们常说的' 先进先出 '。

对比栈的 后进先出 ,是不是还挺有趣的?

js实现一个简单的顺序队列

首先我们要清楚的是队列分为 顺序队列 和循环队列,上边的例子我们排队买烤肠就是顺序队列,至于循环队列我会在接下来的例题中进行说明,我们先实现一个简单的顺序队列。

图 2

队列有两个指针，分别为队头指针front和队尾指针rear，

front指向队头元素,rear指向下一个入队元素的存储位置。(如图2)

下方的ArrayQuene函数就实现一个简单功能的顺序队列:

function ArrayQueue(){  
    var arr = [];  
        //入队操作  
    this.push = function(element){  
        arr.push(element);  
        return true;  
    }  
        //出队操作  
    this.pop = function(){  
        return arr.shift();  
    }  
        //获取队首  
    this.getFront = function(){  
        return arr[0];  
    }  
        //获取队尾  
    this.getRear = function(){  
        return arr[arr.length - 1]  
    }  
        //清空队列  
    this.clear = function(){  
        arr = [];  
    }  
        //获取队长  
    this.size = function(){  
        return length;  
    }  
}  复制代码

例题:设计循环队列

循环队列理解

在实际使用队列时，为了使队列空间能重复使用，往往对队列的使用方法稍加改进：无论插入或删除，一旦rear指针增1或front指针增1时超出了所分配的队列空间，就让它指向这片连续空间的起始位置。

这实际上是把队列空间想象成一个环形空间，环形空间中的存储单元循环使用，用这种方法管理的队列也就称为循环队列。除了一些简单应用之外，真正实用的队列是循环队列。

在上文中提到过顺序队列中有两个指针,front指向队头元素,rear指针指向下一个入队的元素的存储位置。结合下面这张图我们分析一下循环队列在不同情况下front指针和rear指针的指向。

 图 3

• (a)在初始空队时,front和rear指针同时指向队头初始的位置(即0的位置,队列长度为6)
• (b)a,b,c三个元素入队时,rear指针会随着添加元素的个数移动到相应的位置(三个元素,向前移动1位,此时rear由0移动到3)
• (c)a出队,front指针也会随着删除元素的个数移动到相应的位置(删除1个元素,向前移动1位,此时front由0移动到1)
• (d)d,e,f,g入队,rear向前移动4位,由3移动到1,此时队列空间全部占满,rear和front同时指向1
• (e)g出队(由于g处于队头的位置,所以可以出队),front向前移动1位,由0移动到1

相信大家对循环队列有了一个初步的认识,话不多说,我们直接上例题

例题

原题地址(LeetCode 622题)

MyCircularQueue(k)
Front
Rear
enQueue(value)
deQueue()
isEmpty()
isFull()

题目不是很难,我们简单的分析一下题目里面需要我们实现的操作:

• 建立一个长度为k的数组arr,并声明front和rear指针,初始值都设置为0,当插入或删除元素时我们需要手动操作指针的位置。
• 队首元素直接返回arr[front]即可。
• 如果rear不指向0时,队尾元素是arr[rear-1],如果rear指向0的时候队尾元素就是arr[k-1]。
• 插入元素,直接将插入元素赋值给arr[rear],注意要先判断下队列是否是满的状态。
• 删除元素,将元素arr[front]赋值为空,注意要先判断一下队列是否是空的状态。
• 检查队列是否为空,当front和rear的指向相同且队首元素也为空时,队列为空。
• 检查队列是否已满,当front和rear的指向相同且队首元素有值时,队列已满。

代码如下:

class MyCircularQueue{
        // 构造器
        constructor (k) {
            // 建立长度为k的循环队列
            this.arr= Array(k)
            // 声明队首指针front
            this.front = 0
            // 声明队尾指针rear
            this.rear = 0     
        }
        // 获取队首元素
        Front () {
            // 如果队列为空,返回-1 否则直接返回front指向的值
            return this.isEmpty()? -1 : this.arr[this.front]
        }
        // 获取队尾元素
        Rear () {
            // 如果此时rear指针指向0的位置,返回队列最后一位,否则返回下一位
            let rearItem = rear -1 
            return this.arr[rearItem < 0 ? k-1 : rearItem]
        }
        // 插入元素
        enQuene (value) {
            // 先判断队列是否是已满状态
            if(this.isFull()){
                return false
            }else{
                // 插入元素
                this.arr[this.rear] = value
                // 移动rear指针位置,考虑到循环队列指针的变动,用取模的方式
                this.rear = (this.rear+1) % k
                return true
            }
        }
        // 删除元素
        deQuene () {
            // 先判断队列是否为空
            if(this.isEmpty()){
                return false
            }else{
                let deleteItem = this.arr[this.front]
                this.arr[this.front] = ''
                this.front = (this.front+1) % k
                return deleteItem
            }
        }    
        // 判断队列是否为空
        isEmpty () {
            // 头尾指针指向同一个地址并且队首元素为空
            retutn this.rear === this.front && !this.arr[this.front]
        }
        // 判断队列是否已满
        isFull () {
            // 头尾指针指向同一个地址并且队首元素不为空
            return this.rear === this.front && !!this.arr[this.front]
        }
    }复制代码

总结

栈和队列是相对简单的数据结构,相信通过两篇博客大家对这两种数据结构都有了简单的认识,接下来我将介绍相对复杂一些的数据结构。