前言
队列是一种先进先出的数据结构（先到先得），First In First Out(FIFO) 先进先出，就像你去银行取钱。
还是那句老话：光看文章能够掌握两成，动手敲代码、动脑思考、画图才可以掌握八成。源码仓库
不要完美主义。掌握好“度”。
太过于追求完美会把自己逼的太紧，会产生各种焦虑的心态，最后甚至会怀疑自己，温故而知新，不要停止不前，掌握好这个度，不存在你把那些你认为完全掌握了，然后就成了某一个领域的专家，相反一旦你产生很浓厚的厌恶感，那么就意味着你即将会放弃或者已经选择了放弃，虽然你之前想把它做到 100 分，但是由于你的放弃让它变为 0 分。
学习本着自己的目标去。不要在学的过程中偏离了自己的目标。要分清主次。
难的东西，你可以慢慢的回头看一看。那样才会更加的柳暗花明，更能提升自己的收获。
队列 Queue
队列也是一种线性的数据结构，依然就是将数据排成一排。相比数组，队列对应的操作是数组的子集。与栈只能在同一端添加元素和取出元素有所不同，在队列中只能从一端(队尾)添加元素，只能从另一端(队首)取出元素。
例如你去银行取钱：
你需要排队，入队的人不允许插队，所以他要从队尾开始排队，而前面取完钱的会从队首离开，然后后面的人再往前移动一位，最后重复这个过程，直到没人再排队取钱了。
队列的实现
Queue
void enqueue(E)：入队 E dequeue()：出队 E getFront()：查看队首的元素 int getSize()：获取队列中的实际元素大小 boolean isEmpty()：获取队列是否为空的 bool 值
写一个接口叫做 IMyQueue让 MyQueue 实现这个接口这样就符合了面向对象的特性。
代码实现
借用之前前面文章中实现的自定义数组
class: MyArray, class: MyQueue, class: Main)
MyArray
class MyArray {
// 构造函数，传入数组的容量capacity构造Array 默认数组的容量capacity=10
constructor(capacity = 10) {
this.data = new Array(capacity);
this.size = 0;
}
// 获取数组中的元素实际个数
getSize() {
return this.size;
}
// 获取数组的容量
getCapacity() {
return this.data.length;
}
// 判断数组是否为空
isEmpty() {
return this.size === 0;
}
// 给数组扩容
resize(capacity) {
let newArray = new Array(capacity);
for (var i = 0; i < this.size; i++) {
newArray[i] = this.data[i];
}
// let index = this.size - 1;
// while (index > -1) {
// newArray[index] = this.data[index];
// index --;
// }
this.data = newArray;
}
// 在指定索引处插入元素
insert(index, element) {
// 先判断数组是否已满
if (this.size == this.getCapacity()) {
// throw new Error("add error. Array is full.");
this.resize(this.size * 2);
}
// 然后判断索引是否符合要求
if (index < 0 || index > this.size) {
throw new Error(
'insert error. require index < 0 or index > size.'
);
}
// 最后 将指定索引处腾出来
// 从指定索引处开始，所有数组元素全部往后移动一位
// 从后往前移动
for (let i = this.size - 1; i >= index; i--) {
this.data[i + 1] = this.data[i];
}
// 在指定索引处插入元素
this.data[index] = element;
// 维护一下size
this.size++;
}
// 扩展 在数组最前面插入一个元素
unshift(element) {
this.insert(0, element);
}
// 扩展 在数组最后面插入一个元素
push(element) {
this.insert(this.size, element);
}
// 其实在数组中添加元素 就相当于在数组最后面插入一个元素
add(element) {
if (this.size == this.getCapacity()) {
// throw new Error("add error. Array is full.");
this.resize(this.size * 2);
}
// size其实指向的是 当前数组最后一个元素的 后一个位置的索引。
this.data[this.size] = element;
// 维护size
this.size++;
}
// get
get(index) {
// 不能访问没有存放元素的位置
if (index < 0 || index >= this.size) {
throw new Error('get error. index < 0 or index >= size.');
}
return this.data[index];
}
// 扩展： 获取数组中第一个元素
getFirst() {
return this.get(0);
}
// 扩展： 获取数组中最后一个元素
getLast() {
return this.get(this.size - 1);
}
// set
set(index, newElement) {
// 不能修改没有存放元素的位置
if (index < 0 || index >= this.size) {
throw new Error('set error. index < 0 or index >= size.');
}
this.data[index] = newElement;
}
// contain
contain(element) {
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
return true;
}
}
return false;
}
// find
find(element) {
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
return i;
}
}
return -1;
}
// findAll
findAll(element) {
// 创建一个自定义数组来存取这些 元素的索引
let myarray = new MyArray(this.size);
for (var i = 0; i < this.size; i++) {
if (this.data[i] === element) {
myarray.push(i);
}
}
// 返回这个自定义数组
return myarray;
}
// 删除指定索引处的元素
remove(index) {
// 索引合法性验证
if (index < 0 || index >= this.size) {
throw new Error('remove error. index < 0 or index >= size.');
}
// 暂存即将要被删除的元素
let element = this.data[index];
// 后面的元素覆盖前面的元素
for (let i = index; i < this.size - 1; i++) {
this.data[i] = this.data[i + 1];
}
this.size--;
this.data[this.size] = null;
// 如果size 为容量的四分之一时 就可以缩容了
// 防止复杂度震荡
if (Math.floor(this.getCapacity() / 4) === this.size) {
// 缩容一半
this.resize(Math.floor(this.getCapacity() / 2));
}
return element;
}
// 扩展：删除数组中第一个元素
shift() {
return this.remove(0);
}
// 扩展： 删除数组中最后一个元素
pop() {
return this.remove(this.size - 1);
}
// 扩展： 根据元素来进行删除
removeElement(element) {
let index = this.find(element);
if (index !== -1) {
this.remove(index);
}
}
// 扩展： 根据元素来删除所有元素
removeAllElement(element) {
let index = this.find(element);
while (index != -1) {
this.remove(index);
index = this.find(element);
}
// let indexArray = this.findAll(element);
// let cur, index = 0;
// for (var i = 0; i < indexArray.getSize(); i++) {
// // 每删除一个元素 原数组中就少一个元素，
// // 索引数组中的索引值是按照大小顺序排列的，
// // 所以 这个cur记录的是 原数组元素索引的偏移量
// // 只有这样才能够正确的删除元素。
// index = indexArray.get(i) - cur++;
// this.remove(index);
// }
}
// @Override toString 2018-10-17-jwl
toString() {
let arrInfo = `Array: size = ${this.getSize()}，capacity = ${this.getCapacity()}，\n`;
arrInfo += `data = [`;
for (var i = 0; i < this.size - 1; i++) {
arrInfo += `${this.data[i]}, `;
}
if (!this.isEmpty()) {
arrInfo += `${this.data[this.size - 1]}`;
}
arrInfo += `]`;
// 在页面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}MyQueue
class MyQueue {
constructor(capacity = 10) {
this.myArray = new MyArray(capacity);
}
// 入队
enqueue(element) {
this.myArray.push(element);
}
// 出队
dequeue() {
return this.myArray.shift();
}
// 查看队首的元素
getFront() {
return this.myArray.getFirst();
}
// 查看队列中实际元素的个数
getSize() {
return this.myArray.getSize();
}
// 查看 队列当前的容量
getCapacity() {
return this.myArray.getCapacity();
}
// 查看队列是否为空
isEmpty() {
return this.myArray.isEmpty();
}
// 输出队列中的信息
// @Override toString 2018-10-20-jwl
toString() {
let arrInfo = `Queue: size = ${this.getSize()}，capacity = ${this.getCapacity()}，\n`;
arrInfo += `data = front [`;
for (var i = 0; i < this.myArray.size - 1; i++) {
arrInfo += `${this.myArray.data[i]}, `;
}
if (!this.isEmpty()) {
arrInfo += `${this.myArray.data[this.myArray.size - 1]}`;
}
arrInfo += `] tail`;
// 在页面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}Main
class Main {
constructor() {
this.alterLine('MyQueue Area');
let mq = new MyQueue(10);
for (let i = 1; i <= 10; i++) {
mq.enqueue(i);
console.log(mq.toString());
}
console.log(mq.getFront());
this.show(mq.getFront());
while (!mq.isEmpty()) {
console.log(mq.toString());
mq.dequeue();
}
}
// 将内容显示在页面上
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 展示分割线
alterLine(title) {
let line = `--------------------${title}----------------------`;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}队列的复杂度分析
MyQueue
void enqueue(E)： O(1) 均摊 E dequeue()：O(n) 出队的性能消耗太大了 E getFront()：O(1) int getSize()：O(1) boolean isEmpty()：O(1)
出队的性能消耗太大了
如果有一百万条数据，每次都要操作一百万次，那么需要优化它，要让他出队的时候时间复杂度为O(1)，并且还要让他入队的时候时间复杂度依然是O(1)。可以使用循环队列的方式来解决这个问题。
循环队列
自定义队列的性能是有局限性的，出队操作时的时间复杂度为O(n)，要把他变为O(1)。
当取出队列的第一个元素后，第一个元素后面所有的元素位置不动，这样一来时间复杂度就为O(1)了，下一次再取元素的时候从第二个开始，取完第二个元素之后，第二个元素后面所有的元素位置也不动，入队的话直接往队尾添加元素即可。
循环队列的原理
你可以先用一个数字变量 front 指向队首，然后再用一个数字变量 tail 指向队尾，front 指向的是队列中的第一个元素，tail 指向的是队列中最后一个元素的后一个位置，当队列整体为空的时候，它们才会指向同一个位置，所以front == tail时队列就为空，如果有一个元素入队了，front 会指向这个元素，而 tail 会指向这个元素后一个位置（也就是 tail++）然后再有一个元素入队了front 还是指向第一个元素的位置而 tail 会指向第二个元素的后一个位置（还是 tail++）然后再来四个元素入队了front 还是指向第一个元素的位置而 tail 会指向第六个元素的后一个位置（tail++四次）之后 要出队两个元素front 会指向第三个元素的位置（也就是 front++两次）front 从指向第一个元素变成指向第三个元素的位置因为前两个已经出队了这时候再入队一个元素tail 会指向第七个元素的后一个位置（还是 tail++）这时队列的容量已经满了，可能需要扩容但是由于队列中有两个元素已经出队了那这两个位置空出来了，这时就需要利用这两个位置的空间了这就是循环队列了，以循环的方式重复利用空间自定义队列使用自定义数组实现的其实就是把数组看成一个环，数组中一共可以容纳 8 个元素索引是 0-7，那么 7 之后的索引应该是 0，tail 应该指向 0而不是认为整个数组的空间已经满了应该使用 tail 对数组的容量进行求余计算tail 为 8，容量也为 8，求余之后为 0，所以 tail 应该指向 0这时再入队一个元素，tail 指向这个元素的后一个位置，即 1这时候如果再入队一个元素，那么此时 tail 和 front 相等但是那并不能证明队列为空，反而是队列满了所以需要在队列满之前进行判断，tail+1==front就表示队列已满，当数组中只剩最后一个空间了队列就算是满的，因为再入队就会让 tail 与 front 相等而那个条件是队列已空才成立的，虽然对于整个数组空间来说是有意识地浪费了一个空间，但是减少了很大的时间消耗所以当(tail+1)%c==front时就可以扩容了将tail+1==front变成(tail+1)%c==front是因为 tail 从数组的末端跑到前端是有一个求余的过程例如 front 指向的是第一个元素，而 tail 指向的第六个元素之后的位置那么此时 front 为 0，tail 为 7，容量为 8，还有一个浪费掉的空间这时候(tail+1)%c==front，所以队列满了这就是循环队列所有的具体实现必须遵守的规则所有的 front 和 tail 向后移动的过程都要是这种循环的移动例如钟表，11 点钟的下一个钟头为 12 点钟，也可以管它叫做 0 点之后又会变成 1 点、2 点、3 点、4 点依次类推所以整个循环队列的索引也是像钟表一样形成了一个环只不过不一定有 12 刻度，而刻度的数量是由数组的容量(空间总数)决定的。
使用循环队列之后，出队操作不再是整体往前移动一位了而是通过改变 front 的指向，入队操作则是改变 tail 的指向，整个操作循环往复，这样一来出队入队的时间复杂度都为O(1)了。
循环队列的简单实现解析
循环队列 MyLoopQueue，他的实现与 MyQueue 有很大的不同，所以就不使用 MyArray 自定义动态数组了。
循环队列要从底层重新开始写起
data：一个数组。
front： 指向队头有效元素的索引。
tail： 指向队尾有效元素的后一个位置的索引。
size： 通过 front 和 tail 也可以做到循环。
但是使用 size 能够让逻辑更加的清晰明了。
循环队列实现完毕之后，你可以不使用 size 来进行循环队列的维护，而完完全全的使用 front 和 tail，这样难度会稍微的难一点，因为具体逻辑需要特别的小心，会有一些小陷阱。
可以添加 resize 数组扩容缩容功能到极致，从而锻炼逻辑能力、程序编写调试能力等等😏。
循环队列的实现
入队前先判断队列是否已经满了，判断方式 (tail + 1) % data.length == front，判断分析 (队尾指向的索引 + 1) 余以数组的容量是否为队首指向索引。
从用户的角度上来看，队列里就是有这么多元素，一侧是队首一侧是队尾，其它的内容包括实际的数组的大小是用户指定的容量大小+1，这些实现细节，用户是全部不知道的，给用户屏蔽掉了，这就是封装自定义数据结构的目的所在，用户在具体使用这些自定义数据结构的时候，只需要了解接口中所涉及到的这些方法即可，至于它的内部细节用户完全可以不用关心。
代码实现
(class: MyLoopQueue, class: Main)
MyLoopQueue
class MyLoopQueue {
constructor(capacity = 10) {
// 初始化新数组
this.data = new Array(capacity);
// 初始化 队首、队尾的值 (索引)
this.front = this.tail = 0;
// 队列中实际元素个数
this.size = 0;
}
// 扩容
resize(capacity) {
let newArray = new Array(capacity);
let index = 0;
for (let i = 0; i < this.size; i++) {
// 索引可能会越界，于是就要取余一下，
// 如果越界了，就从队首开始
index = (this.front + i) % this.getCapacity();
newArray[i] = this.data[index];
}
this.data = newArray;
this.front = 0;
this.tail = this.size;
}
// 入队
enqueue(element) {
// 判断队列中是否已满
if ((this.tail + 1) % this.getCapacity() === this.front) {
this.resize(Math.floor(this.getCapacity() * 2));
}
this.data[this.tail] = element;
this.tail = (this.tail + 1) % this.getCapacity();
this.size++;
}
// 出队
dequeue() {
// 判断队列是否为空
if (this.isEmpty()) {
throw new Error("can't dequeue from an empty queue.");
}
let element = this.data[this.front];
this.data[this.front] = null;
this.front = (this.front + 1) % this.getCapacity();
this.size--;
// 当size 为容量的四分之一时就缩容一倍
if (this.size === Math.floor(this.getCapacity() / 4)) {
this.resize(this.getCapacity() / 2);
}
return element;
}
// 查看队首的元素
getFront() {
if (this.isEmpty()) {
throw new Error('queue is empty.');
}
return this.data[front];
}
// 查看实际的元素个数
getSize() {
return this.size;
}
// 查看容量
getCapacity() {
return this.data.length;
}
// 队列是否为空
isEmpty() {
// return this.size === 0;
return this.front == this.tail;
}
// 输出循环队列中的信息
// @Override toString 2018-10-20-jwl
toString() {
let arrInfo = `LoopQueue: size = ${this.getSize()}，capacity = ${this.getCapacity()}，\n`;
arrInfo += `data = front [`;
for (var i = 0; i < this.myArray.size - 1; i++) {
arrInfo += `${this.myArray.data[i]}, `;
}
if (!this.isEmpty()) {
arrInfo += `${this.myArray.data[this.myArray.size - 1]}`;
}
arrInfo += `] tail`;
// 在页面上展示
document.body.innerHTML += `${arrInfo}<br /><br /> `;
return arrInfo;
}
}Main
class Main {
constructor() {
this.alterLine('MyLoopQueue Area');
let mlq = new MyQueue(10);
for (let i = 1; i <= 10; i++) {
mlq.enqueue(i);
console.log(mlq.toString());
}
console.log(mlq.getFront());
this.show(mlq.getFront());
while (!mlq.isEmpty()) {
console.log(mlq.toString());
mlq.dequeue();
}
}
// 将内容显示在页面上
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 展示分割线
alterLine(title) {
let line = `--------------------${title}----------------------`;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}两种方式的自定义队列对比
原来自定队列的出队时，时间复杂度为O(n)，使用循环队列的方式后，出队时时间复杂度为O(1)，复杂度的分析只是一个抽象上的理论结果，具体这个变化在性能上意味着会有一个质的飞跃，队列中元素越多，性能就更能够体现出来。
自定义队列的时间复杂度对比
MyQueue：数组队列，使用了自定义数组
void enqueue(E)：O(1) 均摊 E dequeue()：O(n) 出队的性能消耗太大了 E getFront()：O(1) int getSize()：O(1) boolean isEmpty()：O(1)
MyLoopQueue：循环队列，没有使用自定义数组
void enqueue(E)：O(1) 均摊 E dequeue()：O(1) 均摊 E getFront()：O(1) int getSize()：O(1) boolean isEmpty()：O(1)
循环队列的复杂度分析
通过设置循环队列底层的机制，虽然稍微比数组队列要复杂一些，但是这些复杂的工作是值得的，因为他使得在数组队列中，出队本该有O(n)的复杂度变为了O(1)的复杂度，但是这个O(1)为均摊的时间复杂度，因为出队还是会涉及到缩容的操作，在缩容的过程中还是免不了对队列中所有的元素进行一次遍历，但是由于不可能每一次操作都会触发缩容操作来遍历所有的元素，所以应该使用均摊复杂度的分析方式，那样才更加合理。
循环队列中所有的操作都是O(1)的时间复杂度。O(n)的复杂度要比O(1)要慢，但是具体会慢多少可以通过程序来进行测试，这样就能够知道在算法领域和数据结构领域要费这么大的劲去研究更加优化的操作这背后实际的意义到底在哪里。
让这两个队列进行入队和出队操作，操作的次数为 100000 次，通过在同一台机器上的耗时情况，就能够知道性能有什么不同。
数据队列与循环队列十万次入队出队操作后的结果是： MyQueue，time：15.463472711s，MyLoopQueue，time：0.009602136s，循环队列就算操作一亿次，时间也才MyLoopQueue，time：2.663835877s，这个差距主要是在出队的操作中体现出来的，这个性能差距是上千倍，所以这也是性能优化的意义。
测试性能时，不要只测试一次，你可以测试 100 次，取平均值即可，因为这不光和你的程序相关，还会和你当前计算机的状态有关，特别是在两个算法的时间复杂度一致时，测试性能时可能出入会特别大，因为这有多方面原因、如语法、语言、编译器、解释器等等，这些都会导致你代码真正运行的逻辑机制和你理论分析的是不一样的，但是当两个算法的时间复杂度不一致时，这时候测试性能的结果肯定会有巨大的差异，如O(1)对O(n)、O(n)对O(n^2)、O(n)对O(logn)。
测试代码示例
PerformanceTest
class PerformanceTest {
constructor() {}
testQueue(queue, openCount) {
let startTime = Date.now();
let random = Math.random;
for (var i = 0; i < openCount; i++) {
queue.enqueue(random() * openCount);
}
while (!queue.isEmpty()) {
queue.dequeue();
}
let endTime = Date.now();
return this.calcTime(endTime - startTime);
}
// 计算运行的时间，转换为 天-小时-分钟-秒-毫秒
calcTime(result) {
//获取距离的天数
var day = Math.floor(result / (24 * 60 * 60 * 1000));
//获取距离的小时数
var hours = Math.floor((result / (60 * 60 * 1000)) % 24);
//获取距离的分钟数
var minutes = Math.floor((result / (60 * 1000)) % 60);
//获取距离的秒数
var seconds = Math.floor((result / 1000) % 60);
//获取距离的毫秒数
var milliSeconds = Math.floor(result % 1000);
// 计算时间
day = day < 10 ? '0' + day : day;
hours = hours < 10 ? '0' + hours : hours;
minutes = minutes < 10 ? '0' + minutes : minutes;
seconds = seconds < 10 ? '0' + seconds : seconds;
milliSeconds =
milliSeconds < 100
? milliSeconds < 10
? '00' + milliSeconds
: '0' + milliSeconds
: milliSeconds;
// 输出耗时字符串
result =
day +
'天' +
hours +
'小时' +
minutes +
'分' +
seconds +
'秒' +
milliSeconds +
'毫秒' +
' <<<<============>>>> 总毫秒数：' +
result;
return result;
}
}Main
class Main {
constructor() {
this.alterLine('Queues Comparison Area');
let mq = new MyQueue();
let mlq = new MyLoopQueue();
let performanceTest = new PerformanceTest();
let mqInfo = performanceTest.testQueue(mq, 10000);
let mlqInfo = performanceTest.testQueue(mlq, 10000);
this.alterLine('MyQueue Area');
console.log(mqInfo);
this.show(mqInfo);
this.alterLine('MyLoopQueue Area');
console.log(mlqInfo);
this.show(mlqInfo);
}
// 将内容显示在页面上
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 展示分割线
alterLine(title) {
let line = `--------------------${title}----------------------`;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}总结
队列的概念在生活中随处可见，所以使用计算机来模拟生活中队列，如在业务方面你需要排队，或者更加专业的一些领域，比如 网络数据包的排队、操作系统中执行任务的排队等，都可以使用队列。
队列本身是一个很复杂的问题，对于排队来说，队首到底怎么定义，是有多样的定义方式的，也正因为如此，所以存在广义队列这个概念，这两种自定义队列在组建计算机世界的其它算法逻辑的时候也是有重要的应用的，最典型的应用是广度优先遍历。
