数据结构与算法 (队列实现篇)

数据结构与算法 (队列实现篇)

在数据结构与算法中,队列(queue)是一种受限的线性储存结构,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。遵循先进先出(FIFO)的规则。

队列结构示意图
queue.png
队列结构使用

生活中很多地方使用到队列,例如医院门诊看病就是按挂号的号数来排队就诊;公司里面的打印机是按文件发送的顺序进行打印。

3.jpg

在编程中,队列常用作消息发送。例如消息发送队列。待发送的消息依次入队列,待一个消息出队列发送完毕,才会进行下一个消息出队列进行发送。

实现普通队列结构的功能
  • push(element):push是入队列操作,其中element是需要进队列的元素,返回操作成功与否布尔值。
  • shift():shift移除队列front元素操作,返回移除的移除元素。
  • size():获取栈中的队列元素数量,返回一个数字。
  • isEmpty():判断队列是否为空,返回一个布尔值。
  • peek():返回队头元素,但不移除栈顶元素。
  • bottom():返回队尾元素。
  • clear():清除所有队列元素,返回操作成功与否布尔值。
进队列与出队列流程
flow.png
ES6 队列结构代码
class Queue{
    constructor(){
        this.lists = [];
    }
    size(){
        return this.lists.length;
    }
    isEmpty(){
        return this.lists.length === 0;
    }
    peek(){
        return this.list[0];
    }
    bottom(){
        const topIndex = this.size() -1;
        return this.lists[topIndex];
    }
    push(element){
        this.lists.push(element);
        return true;
    }
    shift(){
        return this.lists.shift();
    }
    clear(){
        this.lists = [];
        return true;
    }
    toString(){
        let result = "";
        this.lists.forEach(value=>{
            result = result + ""+value;
        });
        return result;
    }
}
ES5 队列结构代码

通过ES5把功能函数可以绑定在对象的实例上,也可以把功能函数加在函数的原型链上

function Queue(){
    this.lists = [];
}
Queue.prototype.push = function(element){
    this.lists.push(element);
    return true;
}
Queue.prototype.shift = function(){
    return this.lists.shift();
}
Queue.prototype.clear = function(){
    this.lists = [];
    return true;
}
// 返回队头元素
Queue.prototype.peek = function(){
    return this.lists[0];
}
Queue.prototype.size = function(){
    return this.lists.length;
}
Queue.prototype.isEmpty = function(){
    return this.lists.length === 0;
}
Queue.prototype.bottom = function(){
    var topIndex = this.size() -1;
    return this.lists[topIndex];
}
Queue.prototype.toString = function(){
    var result = "";
    for(var i=0;i<this.lists.length;i++){
        result = result + '' +this.lists[i];
    }
    return result;
}
实现优先队列结构的功能

上面实现的是普通队列情况,在日常生活中总遇到需要紧急处理的情况,例如银行VIP客户,急诊室危急病人,紧急文件。这时候需要优先处理这种情况。

优先队列和普通队列的不同主要在优先队列的每一个元素都具有一个权值,代表该元素的优先权大小。还有就是根据权值大小插入队列之中。

prority.png
ES6 最大优先队列结构代码
class Node{
    constructor(element,prority){
        this.element = element;
        this.prority = prority;
    }
}
class Queue{
    constructor(){
        this.lists = [];
    }
    size(){
        return this.lists.length;
    }
    isEmpty(){
        return this.lists.length === 0;
    }
    peek(){
        return this.list[0];
    }
    bottom(){
        const topIndex = this.size() -1;
        return this.lists[topIndex];
    }
    //插入队列
    append(node){
        //当队列为空时
        if(this.lists.length == 0){
            this.lists.push(node);
            return true;
        }else{
            this.lists.forEach((val,index)=>{
                          if(node.prority > val["prority"]){
                              this.lists.splice(index,0,node);
                            return true;
                          }
                          if(index == this.lists.length){
                              this.lists.push(node);
                              return true;
                          }
                      });
        }
    }
    shift(){
        return this.lists.shift();
    }
    clear(){
        this.lists = [];
        return true;
    }
    toString(){
        let result = "";
        this.lists.forEach(value=>{
            result = result + ""+value;
        });
        return result;
    }
}
ES5 最大优先队列结构代码

通过ES5把功能函数可以绑定在对象的实例上,也可以把功能函数加在函数的原型链上

function Node(element,prority){
    this.element = element;
    this.prority = prority;
}
function Queue(){
    this.lists = [];
}
Queue.prototype.append = function(node){
    //当队列为空时
    if(this.lists.length == 0){
        this.lists.push(node);
        return true;
    }
    
    for(var i=0;i<this.lists.length;i++){
        if(node.prority > this.lists[i]["prority"]){
          this.lists.splice(i,0,node);
          return true;
        }
        if(i == this.lists.length){
            this.lists.push(node);
            return true;
        }
    }
    
}
Queue.prototype.shift = function(){
    return this.lists.shift();
}
Queue.prototype.clear = function(){
    this.lists = [];
    return true;
}
// 返回队头元素
Queue.prototype.peek = function(){
    return this.lists[0];
}
Queue.prototype.size = function(){
    return this.lists.length;
}
Queue.prototype.isEmpty = function(){
    return this.lists.length === 0;
}
Queue.prototype.bottom = function(){
    var topIndex = this.size() -1;
    return this.lists[topIndex];
}
Queue.prototype.toString = function(){
    var result = "";
    for(var i=0;i<this.lists.length;i++){
        result = result + '' +this.lists[i];
    }
    return result;
}
循环队列结构图

循环队列就是把队头元素出队列后,再入队列。击鼓传花就是用到了循环队列的原理

image.png
image.png
循环队列代码

循环队列主要实现代码如下

 class SqQueue {
    constructor(length) {
        this.queue = new Array(length + 1)
        // 队头
        this.first = 0
        // 队尾
        this.last = 0
        // 当前队列大小
        this.size = 0
    }
    enQueue(item) {
        // 判断队尾 + 1 是否为队头
        // 如果是就代表需要扩容数组
        // % this.queue.length 是为了防止数组越界
        if (this.first === (this.last + 1) % this.queue.length) {
            this.resize(this.getLength() * 2 + 1)
        }
        this.queue[this.last] = item
        this.size++
        this.last = (this.last + 1) % this.queue.length
    }
    deQueue() {
        if (this.isEmpty()) {
            throw Error('Queue is empty')
        }
        let r = this.queue[this.first]
        this.queue[this.first] = null
        this.first = (this.first + 1) % this.queue.length
        this.size--
        // 判断当前队列大小是否过小
        // 为了保证不浪费空间,在队列空间等于总长度四分之一时
        // 且不为 2 时缩小总长度为当前的一半
        if (this.size === this.getLength() / 4 && this.getLength() / 2 !== 0) {
            this.resize(this.getLength() / 2)
        }
        return r
    }
    getHeader() {
        if (this.isEmpty()) {
            throw Error('Queue is empty')
        }
        return this.queue[this.first]
    }
    getLength() {
        return this.queue.length - 1
    }
    isEmpty() {
        return this.first === this.last
    }
    resize(length) {
        let q = new Array(length)
        for (let i = 0; i < length; i++) {
            q[i] = this.queue[(i + this.first) % this.queue.length]
        }
        this.queue = q
        this.first = 0
        this.last = this.size
    }
}

完成数据结构与算法队列篇。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 219,188评论 6 508
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 93,464评论 3 395
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 165,562评论 0 356
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,893评论 1 295
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,917评论 6 392
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,708评论 1 305
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 40,430评论 3 420
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 39,342评论 0 276
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,801评论 1 317
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,976评论 3 337
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 40,115评论 1 351
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,804评论 5 346
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 41,458评论 3 331
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 32,008评论 0 22
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,135评论 1 272
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 48,365评论 3 373
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 45,055评论 2 355

推荐阅读更多精彩内容