算法基础篇-栈与队列

在我们的日常工作中，前端不可避免的要与算法打交道，可能很多人都会有疑问，那就是我们真的用到了算法了吗？其实仔细相信，我们给数组排序以及从数组中找到需要的元素等等操作，是不是就是所谓的算法的一种呢？在今天这章里，我们一起探讨下算法的基础知识中的栈和队列

栈

栈是一种遵从先进后出（First in last out）原则的有序集合，新添加的以及待删除的元素都保存在栈的同一端，我们把他称作栈顶。相反另一端我们称之为栈底。在日常生活中我们可以拿堆盘子举例，如图：

1648385615(1).jpg

就跟我们去堆盘子一样，我们只能从最上面放，同时也从最上面拿，如果从下面拿那就可能直接让整个盘子堆直接掉下来。
那么我们就可以思考下，如果我们自己要实现栈，我们需要有那些方法呢？从我的角度来看，至少需要以下几个方法

方法名	描述
push(item)	添加一个元素到队列中
pop()	移除栈顶元素并返回
peek()	移除栈顶元素不返回
isEmpty()	返回队列是否为空
clear()	清除队列
size()	返回队列大小

是不是感觉挺熟悉的？没错，大多数都是我们数组本身有的方法，那么我们需要怎么实现一个自己的栈呢？首先肯定是数组，毕竟栈是一种集合。同时我们其实在前面数组中说到了，数组可以说是一种特殊的对象，所以我们也可以通过对象来实现。下面我们依次来看具体的实现。

数组实现栈

export default class Stack {
    public items: Array<any>;
    constructor() {
        this.items = [];
    }
    /**
     * @name: 添加
     * @param {any} item
     * @return {*}
     */
    public push(item: any) {
        this.items.push(item);
    }

    /**
     *
     * @private 移除栈顶元素
     * @returns 
     * @memberof Stack
     */
    public pop() {
        return this.items.pop();
    }
    /**
     *
     *
     * @private 返回栈顶的值
     * @returns
     * @memberof Stack
     */
     public peek() {
        return this.items[this.size() - 1];
    }
    /**
     *
     *
     * @private 返回是否是空的
     * @returns {boolean}
     * @memberof Stack
     */
     public isEmpty():boolean {
        return this.size() === 0
    }
    /**
     * @private
     * @memberof Stack
     */
     public clear() {
        this.items = [];
    }
    /**
     *
     *
     * @private 返回数组size
     * @returns
     * @memberof Stack
     */
     public size() {
        return this.items.length;
    }
}

对象实现栈

export default class StackObject {
    private count: number;
    private items: any;
    constructor() {
        this.count = 0;
        this.items = {};
    }
    /**
     * 添加
     * @param {*} item
     * @memberof StackObject
     */
    public push(item: any) {
        this.items[this.count] = item;
        this.count++;
    }
    /**
     * 移除栈顶元素
     * @returns
     * @memberof StackObject
     */
    public pop() {
        if (!this.isEmpty()) {
            this.count--;
            let result = this.items[this.count];
            delete this.items[this.count];
            return result;
        } else {
            return undefined;
        }
    }
    /**
     * 返回栈顶
     *
     * @returns
     * @memberof StackObject
     */
    public peek() {
        if (!this.isEmpty()) {
            return this.items[this.count - 1];
        } else {
            return undefined;
        }
    }
    /**
     * 判读是否为空
     * @returns {boolean}
     * @memberof StackObject
     */
    public isEmpty(): boolean {
        return this.count === 0;
    }
    /**
     * 返回size
     *
     * @returns
     * @memberof StackObject
     */
    public size() {
        return this.count;
    }
    /**
     * 清空
     *
     * @memberof StackObject
     */
    public clear() {
        this.items = {};
        this.count = 0;
    }
    /**
     * 从任意位置移除
     *
     * @param {*} item
     * @memberof StackObject
     */
    public remove(item: any): any {
        let index = this.findIndex(item);
        if (index === this.size() - 1) {
            this.pop();
        } else {
            let result = this.items[index];
            delete this.items[index];
            this.count--;
            return result;
        }
    }
    /**
     * 判断两个对象是否相同
     *
     * @param {*} firstObj
     * @param {*} secondObj
     * @returns
     * @memberof StackObject
     */
    public judgeObjectSame(firstObj: any, secondObj: any) {
        const aProps = Object.getOwnPropertyNames(JSON.parse(JSON.stringify(firstObj)));
        const bProps = Object.getOwnPropertyNames(JSON.parse(JSON.stringify(secondObj)));
        if (aProps.length !== bProps.length) {
            return false;
        }
        for (let i = 0; i < aProps.length; i++) {
            const propName = aProps[i]

            const propA = firstObj[propName]
            const propB = secondObj[propName]
            if ((typeof (propA) === 'object') && propA !== null) {
                if (this.judgeObjectSame(propA, propB)) {
                } else {
                    return false;
                }
            } else if (propA !== propB) {
                return false;
            } else { }
        }
        return true;
    }
    /**
     * 获取所在位置
     *
     * @param {*} item
     * @returns
     * @memberof StackObject
     */
    public findIndex(item: any | Function) {
        let index: number | string = -1;
        try {
            for (const key in this.items) {
                if (Object.prototype.hasOwnProperty.call(this.items, key)) {
                    let currentItem = this.items[key];
                    if (typeof item === 'function' ? item(currentItem) : this.judgeObjectSame(item, currentItem)) {
                        index = key;
                        throw new Error();
                    }
                }
            }
        } catch (error) {

        }
        return index;
    }
    /**
     * 获取当前item
     *
     * @param {(any | Function)} item
     * @returns
     * @memberof StackObject
     */
    public findItem(item: any | Function) {
        let result = undefined;
        try {
            for (const key in this.items) {
                if (Object.prototype.hasOwnProperty.call(this.items, key)) {
                    let currentItem = this.items[key];
                    if (typeof item === 'function' ? item(currentItem) : item === currentItem) {
                        return currentItem;
                    }
                }
            }
        } catch (error) {

        }
    }
}

上面是两种实现栈的方法，下面我们来看下队列

队列

队列是一种遵从先进先出（First in First out）原则的有序项，队列在尾部添加新元素，并且从顶部移除元素，最新添加的元素必须排到队列的末尾。同样的在日常生活中我们也常遇到队列的例子，例如排队

image.png

我们只能从队伍的最后进入，从队伍的前面退出。如果非要反着来，我想应该会被后面的人打死吧。同栈一样，要实现队列，具体需要哪些方法呢？

方法名	描述
enQueue(item)	添加一个元素到队列中
deQueue：any，	从队列顶部移除元素，并返回
peek()：	返回队列顶元素，不移除
isEmpty()：Boolean	返回队列是否为空
remove：	从队列尾部移除
size()	返回队列大小
clear()	清空队列
findItem(item)	返回查找的元素
findIndex(item)：any	返回的查找元素所在的位置

是不是也很熟悉，没错，数组中同样有类似的方法，那么我们就通过数组来实现一个自己的队列

export default class Queue {
    private count: number;
    private topCount: number;
    public items: any;
    constructor() {
        this.count = 0;
        this.topCount = 0;
        this.items = {};
    }
    /**
     * 从队列尾部添加
     *
     * @param {*} item
     * @memberof Queue
     */
    public enQueue(item: any) {
        this.items[this.count] = item;
        this.count++;
    }
    /**
     *
     * 从队列头部移除
     * @returns
     * @memberof Queue
     */
    public deQueue() {
        if (!this.isEmpty()) {
            let result = this.items[this.topCount];
            delete this.items[this.topCount];
            this.topCount++;
            return result;
        } else {
            return undefined;
        }
    }
    /**
     * 返回队列头部数据 
     *
     * @returns
     * @memberof Queue
     */
    public peek() {
        if (this.isEmpty()) {
            return undefined;
        } else {
            return this.items[this.topCount];
        }
    }
    /**
     * 返回队列的数量
     *
     * @returns {number}
     * @memberof Queue
     */
    public size(): number {
        return this.count - this.topCount;
    }
    /**
     * 从队列任何一个地方移除
     *
     * @param {*} item
     * @returns {*}
     * @memberof Queue
     */
    public remove(item: any): any {
        let index = this.findIndex(item);
        if (index === this.topCount) {
            this.deQueue();
        } else {
            let result = this.items[index];
            delete this.items[index];
            this.count--;
            return result;
        }
    }
    /**
     * 判断是否是空
     *
     * @returns
     * @memberof Queue
     */
    public isEmpty() {
        return this.size() === 0
    }
    /**
     * 清空队列
     *
     * @memberof Queue
     */
    public clear() {
        this.count = 0;
        this.topCount = 0;
        this.items = {};
    }
    /**
     * 判断两个对象是否相同
     *
     * @param {*} firstObj
     * @param {*} secondObj
     * @returns
     * @memberof StackObject
     */
    public judgeObjectSame(firstObj: any, secondObj: any) {
        const aProps = Object.getOwnPropertyNames(JSON.parse(JSON.stringify(firstObj)));
        const bProps = Object.getOwnPropertyNames(JSON.parse(JSON.stringify(secondObj)));
        if (aProps.length !== bProps.length) {
            return false;
        }
        for (let i = 0; i < aProps.length; i++) {
            const propName = aProps[i]

            const propA = firstObj[propName]
            const propB = secondObj[propName]
            if ((typeof (propA) === 'object') && propA !== null) {
                if (this.judgeObjectSame(propA, propB)) {
                } else {
                    return false;
                }
            } else if (propA !== propB) {
                return false;
            } else { }
        }
        return true;
    }
    /**
     * 获取所在位置
     *
     * @param {*} item
     * @returns
     * @memberof StackObject
     */
    public findIndex(item: any | Function) {
        let index: number | string = -1;
        try {
            for (const key in this.items) {
                if (Object.prototype.hasOwnProperty.call(this.items, key)) {
                    let currentItem = this.items[key];
                    if (typeof item === 'function' ? item(currentItem) : this.judgeObjectSame(item, currentItem)) {
                        index = key;
                        throw new Error();
                    }
                }
            }
        } catch (error) {

        }
        return index;
    }
    public findItem(item: any | Function) {
        let result = undefined;
        try {
            for (const key in this.items) {
                if (Object.prototype.hasOwnProperty.call(this.items, key)) {
                    let currentItem = this.items[key];
                    if (typeof item === 'function' ? item(currentItem) : item === currentItem) {
                        return currentItem;
                    }
                }
            }
        } catch (error) {

        }
    }
}

那么队列在日常生活中有哪些可以用到呢？我们来举一个例子，那就是击鼓传花的游戏，我想大家应该就明白了。

击鼓传花游戏规则是：击鼓传花需要几个人或数十人围坐呈一个圈或一排，并由一个人敲鼓或发出声音，声音响起时，第一个人或其中一个人拿小物品开始依次传递，声音结束后即要停止传递，最后收到物品的那个人就需要接受惩罚。 image.png

我们现在仔细把规则给解读下，一群人围坐一排或者一圈，那么我们可以用队列来将这个数据存储，第一个人或其中一个人拿小物品开始依次传递，那么我们假设A现在拿到花，那么A可以假定在队列的顶部，当把花移交给下一位的时候，A肯定不会被淘汰，那么我们可以先将A从顶部移除，然后将A加到队列尾部，那么花就在了B手上，这个时候B就为队列头，如果这个时候声音停了，那么B就要被淘汰，那么淘汰就是被移除的意思。所以我们的实现方法就可以出来了。

const drumFlowerFun = () => {
  let names = ['小明', '小红', '小绿', '小蓝', '小白'];
  let result = drumFlower(names, 10);
  ShopArr.value.drumFlowerData = result;
}
const drumFlower = (list: Array<string>, num: number): {
  passList: Array<string>,
  winner: string
} => {
  let queue = new Queue();
  let passList: Array<string> = [];
  // 将list传入到队列中
  list.forEach(item => {
    queue.enQueue(item);
  })
  // 当多余一个人的时候，首先需要将头部的人添加到末尾,当数据到了传递的次数(也就是鼓停)将当前队列第一的人淘汰
  while (queue.size() > 1) {
    for (let i = 0; i < num; i++) {
      queue.enQueue(queue.deQueue());
    }
    passList.push(queue.deQueue())
  }
  return {
    passList: passList,
    winner: queue.deQueue()
  }
}

至此队列我们也结束了吗，但是在实际的生活中，同样是排队，人们可以在队伍的尾部进入，然后从队伍的尾部走开，同样的也可以在队伍的头部走开，但是刚走出去再折回问下问题。那么就涉及到双端队列了

双端队列

双端队列，是在队列的基础上允许可以从队列的前端和后端添加和移除元素的特殊队列

双端队列

那么双端队列的方法同样的，仅仅是在队列的基础上增加了两个方法即可。下面我们来看下具体的实现代码

/**
 * peek() 返回头部
 * isEmpty() 判断是否为空
 * size() 返回size
 * remove()移除
 * findItem() 获取item
 * addFront() 从队列头部添加
 * removeFront() 从队列头部删除
 * addBackend() 从队列尾部添加
 * removeBackend() 从队列尾部删除
 * @export
 * @class Queue
 */
export default class Queue {
    private count: number;
    private topCount: number;
    public items: any;
    constructor() {
        this.count = 0;
        this.topCount = 0;
        this.items = {};
    }
    /**
     * 从队列尾部添加
     *
     * @param {*} item
     * @memberof Queue
     */
    public addBackend(item: any) {
        this.items[this.count] = item;
        this.count++;
    }
    /**
     * 从队列头部添加
     *
     * @param {*} item
     * @memberof Queue
     */
    public addFront(item: any) {
        if (this.isEmpty()) {
            this.addBackend(item);
        } else if (this.topCount > 0) {
            this.topCount--;
            this.items[this.topCount] = item;
        } else {
            for (let i = this.count; i > 0; i--) {
                this.items[i] = this.items[i - 1];
            }
            this.count++;
            this.topCount = 0;
            this.items[0] = item;
        }
    }
    /**
     *
     * 从队列头部移除
     * @returns
     * @memberof Queue
     */
    public removeFront() {
        if (!this.isEmpty()) {
            let result = this.items[this.topCount];
            delete this.items[this.topCount];
            this.topCount++;
            return result;
        } else {
            return undefined;
        }
    }
    /**
     *
     * 从队列尾部移除
     * @returns
     * @memberof Queue
     */
    public removeBackend() {
        if (!this.isEmpty()) {
            this.count--;
            let result = this.items[this.count];
            delete this.items[this.count];
            return result;
        } else {
            return undefined;
        }
    }
    /**
     * 返回队列头部数据 
     *
     * @returns
     * @memberof Queue
     */
    public peek() {
        if (this.isEmpty()) {
            return undefined;
        } else {
            return this.items[this.topCount];
        }
    }
    /**
     * 返回队列的数量
     *
     * @returns {number}
     * @memberof Queue
     */
    public size(): number {
        return this.count - this.topCount;
    }
    /**
     * 从队列任何一个地方移除
     *
     * @param {*} item
     * @returns {*}
     * @memberof Queue
     */
    public remove(item: any): any {
        let index = this.findIndex(item);
        if (index === this.topCount) {
            this.removeFront();
        } else {
            let result = this.items[index];
            delete this.items[index];
            this.count--;
            return result;
        }
    }
    /**
     * 判断是否是空
     *
     * @returns
     * @memberof Queue
     */
    public isEmpty() {
        return this.size() === 0
    }
    /**
     * 清空队列
     *
     * @memberof Queue
     */
    public clear() {
        this.count = 0;
        this.topCount = 0;
        this.items = {};
    }
    /**
     * 判断两个对象是否相同
     *
     * @param {*} firstObj
     * @param {*} secondObj
     * @returns
     * @memberof StackObject
     */
    public judgeObjectSame(firstObj: any, secondObj: any) {
        const aProps = Object.getOwnPropertyNames(JSON.parse(JSON.stringify(firstObj)));
        const bProps = Object.getOwnPropertyNames(JSON.parse(JSON.stringify(secondObj)));
        if (aProps.length !== bProps.length) {
            return false;
        }
        for (let i = 0; i < aProps.length; i++) {
            const propName = aProps[i]

            const propA = firstObj[propName]
            const propB = secondObj[propName]
            if ((typeof (propA) === 'object') && propA !== null) {
                if (this.judgeObjectSame(propA, propB)) {
                } else {
                    return false;
                }
            } else if (propA !== propB) {
                return false;
            } else { }
        }
        return true;
    }
    /**
     * 获取所在位置
     *
     * @param {*} item
     * @returns
     * @memberof StackObject
     */
    public findIndex(item: any | Function) {
        let index: number | string = -1;
        try {
            for (const key in this.items) {
                if (Object.prototype.hasOwnProperty.call(this.items, key)) {
                    let currentItem = this.items[key];
                    if (typeof item === 'function' ? item(currentItem) : this.judgeObjectSame(item, currentItem)) {
                        index = key;
                        throw new Error();
                    }
                }
            }
        } catch (error) {

        }
        return index;
    }
    public findItem(item: any | Function) {
        let result = undefined;
        try {
            for (const key in this.items) {
                if (Object.prototype.hasOwnProperty.call(this.items, key)) {
                    let currentItem = this.items[key];
                    if (typeof item === 'function' ? item(currentItem) : item === currentItem) {
                        return currentItem;
                    }
                }
            }
        } catch (error) {

        }
    }
}