背景

去年下半年，我在微信书架里加入了许多技术书籍，各种类别的都有，断断续续的读了一部分。

没有计划的阅读，收效甚微。

新年伊始，我准备尝试一下其他方式，比如阅读周。每月抽出1~2个非连续周，完整阅读一本书籍。

这个“玩法”虽然常见且板正，但是有效，已经坚持阅读四个月。

已读完书籍：《架构简洁之道》、《深入浅出的Node.js》、《你不知道的JavaScript（上卷）》、《你不知道的JavaScript（中卷）》、《你不知道的JavaScript（下卷）》。

当前阅读周书籍：《数据结构与算法JavaScript描述》。

队列

对队列的操作

队列的两种主要操作是：向队列中插入新元素和删除队列中的元素。插入操作也叫做入队，删除操作也叫做出队。入队操作在队尾插入新元素，出队操作删除队头的元素。

队列的另外一项重要操作是读取队头的元素。这个操作叫做peek()。该操作返回队头元素，但不把它从队列中删除。除了读取队头元素，我们还想知道队列中存储了多少元素，可以使用length属性满足该需求；要想清空队列中的所有元素，可以使用clear()方法来实现。

一个用数组实现的队列

使用数组来实现队列，数组的push()方法可以在数组末尾加入元素，shift()方法则可删除数组的第一个元素。

准备开始实现Queue类，先从构造函数开始：

function Queue() {
  this.dataStore = [];
  this.enqueue = enqueue;
  this.dequeue = dequeue;
  this.front = front;
  this.back = back;
  this.toString = toString;
  this.empty = empty;
}

enqueue()方法向队尾添加一个元素：

function enqueue(element) {
  this.dataStore.push(element);
}

dequeue()方法删除队首的元素：

function dequeue() {
  return this.dataStore.shift();
}

可以使用如下方法读取队首和队尾的元素：

function front() {
  return this.dataStore[0];
}

function back() {
  return this.dataStore[this.dataStore.length - 1];
}

还需要toString()方法显示队列内的所有元素：

function toString() {
  var retStr = '';
  for (var i = 0; i < this.dataStore.length; ++i) {
    retStr += this.dataStore[i] + '\n';
  }
  return retStr;
}

最后，需要一个方法判断队列是否为空：

function empty() {
  if (this.dataStore.length == 0) {
    return true;
  } else {
    return false;
  }
}

测试代码：

//测试程序
var q = new Queue();
q.enqueue("Meredith");
q.enqueue("Cynthia");
q.enqueue("Jennifer");
print(q.toString());
q.dequeue();
print(q.toString());
print("Front of queue: " + q.front());
print("Back of queue: " + q.back());

输出为：

Meredith
Cynthia
Jennifer
Cynthia
Jennifer

Front of queue: Cynthia
Back of queue: Jennifer

使用队列对数据进行排序

对于0～99的数字，基数排序将数据集扫描两次。第一次按个位上的数字进行排序，第二次按十位上的数字进行排序。每个数字根据对应位上的数值被分在不同的盒子里。假设有如下数字：

91, 46, 85, 15, 92, 35, 31, 22

经过基数排序第一次扫描之后，数字被分配到如下盒子中：

Bin 0:
Bin 1: 91, 31
Bin 2: 92, 22
Bin 3:
Bin 4:
Bin 5: 85, 15, 35
Bin 6: 46
Bin 7:
Bin 8:
Bin 9:

根据盒子的顺序，对数字进行第一次排序的结果如下：

91, 31, 92, 22, 85, 15, 35, 46

然后根据十位上的数值再将上次排序的结果分配到不同的盒子中：

Bin 0:
Bin 1: 15
Bin 2: 22
Bin 3: 31, 35
Bin 4: 46
Bin 5:
Bin 6:
Bin 7:
Bin 8: 85
Bin 9: 91, 92

最后，将盒子中的数字取出，组成一个新的列表，该列表即为排好序的数字：

15, 22, 31, 35, 46, 85, 91, 92

使用队列代表盒子，可以实现这个算法。我们需要九个队列，每个对应一个数字。将所有队列保存在一个数组中，使用取余和除法操作决定个位和十位。算法的剩余部分将数字加入相应的队列，根据个位数值对其重新排序，然后再根据十位上的数值进行排序，结果即为排好序的数字。

基数排序：

function distribute(nums, queues, n, digit) {
  for (var i = 0; i < n; ++i) {
    if (digit == 1) {
      queues[nums[i] % 10].enqueue(nums[i]);
    } else {
      queues[Math.floor(nums[i] / 10)].enqueue(nums[i]);
    }
  }
}

function collect(queues, nums) {
  var i = 0;
  for (var digit = 0; digit < 10; ++digit) {
    while (!queues[digit].empty()) {
      nums[i++] = queues[digit].dequeue();
    }
  }
}
function dispArray(arr) {
  for (var i = 0; i < arr.length; ++i) {
    putstr(arr[i] + ' ');
  }
}

//主程序

var queues = [];
for (var i = 0; i < 10; ++i) {
  queues[i] = new Queue();
}
var nums = [];
for (var i = 0; i < 10; ++i) {
  nums[i] = Math.floor(Math.floor(Math.random() * 101));
}
print('Before radix sort: ');
dispArray(nums);
distribute(nums, queues, 10, 1);
collect(queues, nums);
distribute(nums, queues, 10, 10);
collect(queues, nums);
print('\n\nAfter radix sort: ');
dispArray(nums);

下面是程序运行几次的结果：

Before radix sort:
45 72 93 51 21 16 70 41 27 31

After radix sort:
16 21 27 31 41 45 51 70 72 93

Before radix sort:
76 77 15 84 79 71 69 99 6 54

After radix sort:
6 15 54 69 71 76 77 79 84 99

总结

队列是一种列表，是一种先进先出（First-In-First-Out, FIFO）的数据结构,不同的是队列只能在队尾插入元素，在队首删除元素。队列用于存储按顺序排列的数据，先进先出，这点和栈不一样，在栈中，最后入栈的元素反而被优先处理。

作者介绍
非职业「传道授业解惑」的开发者叶一一。
《趣学前端》、《CSS畅想》等系列作者。华夏美食、国漫、古风重度爱好者，刑侦、无限流小说初级玩家。
如果看完文章有所收获，欢迎点赞👍 | 收藏⭐️ | 留言📝。