【在厨房想30天的演算法】Day 09 资料结构:伫列 Queue

Aloha!又是我少女人妻 Uerica!自从写了铁人赛文章後,因为我跟老公都太忙,我家狗狗对我发出各种抗议,拍滑鼠、抓手手、躲在角落哭哭,早上 8 点准时用粗糙肉垫狂殴我,而且都只攻击我 Q_Q。三十天後我家狗狗可能会精通十八般武艺了~


伫列 (Queue)

伫列与昨天的堆叠有点类似,但堆叠是优先处理最新资料,只由一个方向推入与取出,但伫则是优先处理旧有的资料,也就是新增、删除为不同端操作。

伫列的定义与特性

伫列简单来说有点像排队,先排的人可以先取得服务,像这种资料的存取方式又称为「先进先出」 (FIFO, First-In-First-Out) ,除了平常排队外,还有点餐、任务排程、银行办事抽号码牌等。若为双向都可操作的伫列称为双伫列。

  • 优点
    • 可按顺序处理资料元素
    • 新增与取出资料快速
  • 缺点
    • 插入或删除某指定资料元素不易
    • 要取出最新的资料元素,须先移除前面所有资料

pNZnaxS

常见的基本操作

enqueue: 将新资料元素加入伫列

dequeue: 将最先放入的资料移出伫列

front: 回传伫列最前方、第一笔加入的资料元素

rear: 回传伫列最後方、最後一笔加入的资料元素

size: 取得伫列大小

UNXO9cJ

来!实作

要建立伫列,我们要将资料储存在记忆体的连续空间,并指出第一笔加入的资料元素(front),以及最後一笔新增的资料元素(rear),所以在此也用 javaScript 提供的阵列来实作。

//建构一个 Queue 类别,并将其储存的资料 elements 的型态宣告为阵列。
class Queue {

    constructor() {
    this.elements = [];
    }

    //用 push() 来新增一笔元素在所有资料最後方 
    enqueue(element) {
    this.elements.push(element);
    }

    //用 shift() 来移出第一笔资料元素 
    dequeue() {
    return this.elements.shift();
    }

    //用阵列索引的特性找出第一笔资料元素
    front() {
    return this.elements[0];
    }

    //用 阵列索引与 length 的特性找出最後一笔新增的资料元素
    rear() {
    return this.elements[this.elements.length - 1];
    }

    //回传有几笔资料元素在伫列中
    size() {
    return this.elements.length;
    }
}

来建立实体

const queue = new Queue();

//增加些资料元素在伫列中
queue.enqueue("a");
queue.enqueue("b");
queue.enqueue("c");
queue.enqueue("d");
queue.enqueue("e");

//取出一笔资料元素
console.log(queue.dequeue()); //a
//回传目前在最前方的资料元素
console.log(queue.front()); //b
//回传目前在最後方的资料元素
console.log(queue.rear()); //e
//回传伫列中所有资料元素还有几笔
console.log(queue.size()); //4

参考资料:

JavaScript # 17 — 伫列(Queue)
JavaScript 学演算法(六)- 堆叠 & 伫列
【资料结构 – 重构】伫列与回圈伫列


感谢各位阅读!我去遛狗啦!明天见掰掰!


<<:  Day 11:批次修改!!

>>:  Day 20 - 研习计画之网站上线以及功能延伸开发篇

Day22. 当苹果掉到牛顿头上,牛顿被敲醒了 - Gravity

一开始到现在,虽然我们没有特别提到,物体就那麽自然的向下掉,就像苹果掉到牛顿头上的自然,这背後的理所...

How to convert RAW to NTFS file system without losing data?

What should you do if the partition on your extern...

[Tableau Public] day 5:尝试制作不同种类的报表-2

第五天,星期日放假日,好像已经习惯了每日发一文章的习惯了~ 参考的资料来源一样是 day 4 的「O...

Day-12 认识Excel枢纽分析表

今日练习档 ԅ( ¯་། ¯ԅ) 你是不是听到枢纽分析表就会腿软!你是不是听到枢纽分析表就想放弃!今...

Day 10 - Algebraic structure

yo, what's up 本章要来介绍 FP 的重要观念,Algebraic structure!...