队列上一篇数据结构讲到了栈，队列和栈非常类似。队列也是一种特殊的列表，它与栈的区别在于，栈是先入后出，而队列则是遵循FIFO先入先出的原则，换言之队列只能在队尾插入元素，而在队列的头部去删除元素。举个简单的例子，队列就相当于在生活中排队购物，后来的人需要排在队尾，而队伍最前面的人会一次结账后出列。队列的应用非常广泛，常用于实现缓冲区，广度优先搜索，优先级队列等等。队列最主要的两个操作分别是enqueue(入列)和dequeue(出列)队列的实现逻辑通过上面这张图我们可以看到队列的几个特点初始化有一块连续的空间用来去存储队列有一个头部指向第一个数据的地址有一个尾部指向数据后一个空位的地址空间的大小队列内部数据的长度 class Queue { constructor(max=1000){ // 定义一块连续的存储空间用来存储数据 this.data = new Array(1000); // 开辟的空间大小 this.max = max; // 头部位置 this.head = 0; // 尾部位置 this.tail = 0; // 数据长度 this.size = 0; } }enqueue 入列当数据长度超出了开辟的空间大小会报overflow的错误向尾部添加新数据尾部指针向后挪动一位，如果尾部没有空间，则指向0（见上图的两个enqueue操作） enqueue(x) { // 溢出 if(this.size === this.max){ throw ‘overflow’ } // 添加新数据到尾部 this.data[this.tail] = x; // 数据长度+1 this.size++; // 尾部指针向后挪动一位，如果后面没有空间，则指向0 if(this.tail === this.max-1){ this.tail = 0; }else{ this.tail++ } }dequeue出列如果当前数据长度为0，则抛出underflow的错误取出头部位置的数据头部指针向后挪动一位数据长度-1返回该数据 dequeue(){ if(this.size === 0){ throw ‘underflow’; } const x = this.data[this.head]; this.head++; this.size–; return x; }整个代码 class Queue { constructor(max = 1000) { this.data = new Array(max); this.max = max; this.head = 0; this.tail = 0; this.size = 0; } // 入列 enqueue(x) { if (this.size === this.max) { throw ‘overflow’; } this.data[this.tail] = x; this.size++; if (this.tail === this.max - 1) { this.tail = 0; } else { this.tail++; } } // 出列 dequeue() { if (this.size === 0) { throw ‘underflow’; } const x = this.data[this.head]; this.head++; this.size–; return x; } get length() { return this.size; } } module.exports = Queue;扩展–栈实现队列队列也可以通过两个栈来实现，不了解栈的同学可以看上一篇关于栈文章，接下来会引入之前写好的栈，具体代码见下面。 // 上一节中，栈的实现代码 const Stack = require(’./stack’); class Queue { constructor(max=1000){ // 实例化两个栈，分别是s1和s2, s1栈用来做入列,s2栈用来出列使用 this.s1 = new Stack(max); this.s2 = new Stack(max); this.max = max; } // 入列 enqueue(x) { if(this.s1.length === this.max){ throw ‘overflow’ } // s1作为入列 this.s1.push(x); } // 出列 dequeue(){ if(this.s2.length>0){ return this.s2.pop; } while(this.s1.length){ this.s2.push(this.s1.pop()); } return this.s2.pop(); } }在这里大致简单的说明一下以上用两个栈来实现队列的逻辑吧。栈s1 入栈后假设数据为 1,2,3,4,5，队列遵循先入先出，所以dequeue的时候的顺序应该是1,2,3,4,5,那么下面我们看如何利用栈s2出栈。首先栈s1 pop()出栈后的数据则为 5,4,3,2,1 正好倒过来, 我们利用循环将栈s1出栈的数据push到栈s2，则栈s2中的数据就会是5,4,3,2,1。下面我们再执行s2.pop()的时候，是不是就能刚好能依次拿到1,2,3,4,5这几个数据了后续下一张的数据结构会为大家介绍链表