共计 2031 个字符，预计需要花费 6 分钟才能阅读完成。
队列
上一篇数据结构讲到了栈，队列和栈非常类似。队列也是一种特殊的列表，它与栈的区别在于，栈是先入后出，而队列则是遵循 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 这几个数据了
后续
下一张的数据结构会为大家介绍链表