Day7: [资料结构]Stack —堆叠和Queue— 伫列

Stack

Stack是一种资料结构，遵循着後进先出的原则，最晚放入堆叠的资料会被最先取出(LIFO Last-In-First-Out)，最早放入堆叠的资料会被最後取出(FILO First-In-Last-Out)，就像堆叠的盘子一样，如果要添加盘子一定是从最上面开始放，如果要取出盘子也是从最上面开始拿，堆叠会有两种操作，pop - 从上面移除和push - 从上面新增。

用js实作Stack

class Stack {
    constructor(arr) {
        this.stack = arr;
    }
    push(item) {
        this.stack.push(item);
    }
    pop() {
        return this.stack.pop();
    }
    peek() {
        return this.stack[this.stack.length - 1];
    }
    size() {
        return this.stack.length;
    }
    print() {
        return this.stack;
    }
}

const stack = new Stack([2, 4, 9, 5, 8]);
stack.pop(); //8
stack.peek(); //5

stack.push(7);
stack.print(); //[2, 4, 9, 5, 7]

stack.size(); //5

Queue

伫列可以把想像是一个排队的队伍，排在第一顺位的客人买到了车票所以离开了队伍，而队伍的後方陆续有新的排队人潮加入，和堆叠不同的是，伫列是先进先出(FIFO First-In-First-Out)，跟堆叠的後进先出(LIFO Last-In-First-Out)是不一样的，伫列有两种操作，push - 从後面新增和shift - 从前面移除。

伫列跟array不同是没有index

左边为queue，右边为stack

用js实作Queue

class Queue {
    constructor(arr) {
        this.queue = arr;
    }
    push(item) {
        this.queue.push(item);
    }
    shift() {
        return this.queue.shift();
    }
    size() {
        return this.queue.length;
    }
    print() {
        return this.queue;
    }
}

const queue = new Queue([3, 6, 9, 1, 7]);
queue.shift(); //3

queue.push(2);
queue.print(); //[6, 9, 1, 7, 3]

queue.size(); //5

这时候眼尖的你应该发现，不管是Stack或是Queue，其实都可以用js的array方法， pop() 、push()、 shift()来实作。

理解了Stack和Queue之後，相信就会更清楚Event Loop的流程啦!相信大家都知道JavaScript是单线程的程序语言，一次只能做一件事情，所以Stack会把里面的任务(由上而下)依序处理，每处理完一个片段就pop掉，直到Stack清空，这时queue如果还有排队等候的任务就会加入到stack里面，这个过程就是Event Loop。

图片来源:https://medium.com/@Rahulx1/understanding-event-loop-call-stack-event-job-queue-in-javascript-63dcd2c71ecd