前言
队列，是一种常见的逻辑数据结构。具备什么特点呢？经常性的我们会听到一个类比“队列就像队伍过桥洞”，队列中的元素遵循了“先进先出、后进后出”的原则。
在JavaScript中有很多的方式来实现一个队列，让我们一起来看看都是如何实现的呢？
方案一：直接操作数组
直接使用数组存储队列元素，模拟队列特点。
上代码~~~
/** * @description 基于数组实现队列的类 */ class QueueArray { // 设置私有属性，存储队列元素 private list: number[] = []; /** * @method add * @description 将元素插入队列 - 队尾元素 * @param n number 待插入的元素 */ add(n: number) { this.list.push(n); } /** * @method delete * @description 队列进行出队，移除元素 - 队头元素 * @returns number | undefined */ delete(): number | undefined { // 队头元素移除 return this.list.shift(); } /** * @description 队列长度 */ get length(): number { return this.list.length; } }
接下来我们来测试下性能，同样以10W条数据为例。
// 实例化，创建队列 const queueArray = new QueueArray(); // 检测add入队插入方法的性能 console.time('add'); // 插入10W条数据 for (let i = 0; i < 10 * 10000; i++) { queueArray.add(i); } // 获取队列长度 console.log(queueArray.length); console.timeEnd('add'); // 检测delete出队删除元素方法的性能 console.time('delete'); // 这里出队1W条数据 for (let i = 0; i < 10000; i++) { queueArray.delete(); } console.timeEnd('delete');
看下浏览器中的数据展示
网络异常，图片无法展示
|
再次强调下，不同性能电脑设备打印数据略有不同
我们来分析下直接基于数组Array实现的队列复杂度、性能问题。
- 在执行
add进行入队元素操作时，10W条数据还是非常快的，执行的都是push操作；
- 执行
delete进行出队操作时，出队了1W条数据，我们看到消耗的时间有了急剧的增加；有小伙伴可能要问为啥会这样呢？在之前的文章数组旋转，来来来，走个K步~中，胡哥说过数组在内存中是有序连续存储的，一旦涉及到数组元素移动的方法，都是非常损耗性能的，如shift、unshift、splice方法等。也就是说从队头移除一个元素，就需要将剩余的其他元素统一向前移动一位，带来了O(n)O(n)O(n)的时间复杂度。
以上实现虽然达到了目的，却不是我们最想要的。那还有更优雅的方式吗？
方案二：基于栈结构
现在我们采用栈结构模拟实现队列。在这里我们仍然选择数组来实现栈，不过不同于方案一，不再使用shift方法。
设置两个栈 stack1、stack2，
- 每次入队时，向
stack1中插入元素;
- 每次出队时，先将
stack1中的元素依次pop弹出，然后push到stack2中，将stack2中的最后一个元素pop出，然后再将stack2中的元素再依次放回stack1中，这样就完成了出队。
在这样的操作下，push、pop方法都是非常快速的，时间复杂度O(1)O(1)O(1)。
/** * @description 基于栈结构实现队列 */ class QueueStack { private statck1: number[] = []; private statck2: number[] = []; /** * @method add * @description 将元素插入队列 - 队尾元素 * @param n number 待插入的元素 */ add(n: number) { this.statck1.push(n); } /** * @method delete * @description 队列进行出队，移除元素 - 队头元素 * @returns number | undefined */ delete(): number | undefined { let n; // 1. 将stack1中的元素依次取出，放入stack2中 while ((n = this.statck1.pop()) !== undefined) { this.statck2.push(n); } // 2. 抛出stack2最后一个元素，移除队头元素-即栈顶元素 const res = this.statck2.push(); // 3. 然后stack2中元素再依次放入stack1中 while ((n = this.statck2.pop()) !== undefined) { this.statck1.push(); } return res; } /** * @description 队列长度 */ get length(): number { // 所有的元素都放在stack1中，直接返回stack1的长度即可 return this.statck1.length; } }
同样的数据条件-10W条数据，我们来看下性能测试。
const queueStack = new QueueStack(); // 检测add入队插入方法的性能 console.time('add - stack'); // 入队10W个元素 for (let i = 0; i < 10 * 10000; i++) { queueStack.add(i); } // 获取队列长度 console.log(queueStack.length); console.timeEnd('add - stack'); // 检测delete出队删除元素方法的性能 console.time('delete - stack'); for (let i = 0; i < 10000; i++) { queueStack.delete(); } console.timeEnd('delete - stack');
来来来，看下浏览器中数据：
网络异常，图片无法展示
|
从数据上对比下，add添加队列元素的方法，性能是一样的，相差无几。而delete删除队列元素的方法，性能相差甚大，方案二 - 基于栈结构的实现性能更优。
分析下原因：
- 在
delete方法中，有两层while循环可记做O(n)O(n)O(n)，执行push和pop方法都是O(1)O(1)O(1)时间复杂度的。从时间复杂度这个标准来看，方案二和方案一都是O(n)O(n)O(n)时间复杂度，但是数组的shift方法涉及到移动数组元素，实际性能明显偏低。
- 在方案一种，只有
list一个数组变量，空间复杂度记为O(n)；方案二中有两个stack1、stack2数组变量，空间复杂度也是记为O(n)O(n)O(n)，实际内存空间肯定是比方案一多了一倍。虽然空间占用多了，但实际算法执行时间有了非常明显的降低，也就是说空间换时间，是非常值的。
二者比较，我们肯定会选择方案二。
问题？
那还有没有更优的算法实现队列呢，肯定是有的，比如说链表结构，当然这是后话，今天暂且不提。欢迎大家持续关注呦~
