什么是队列
队列是一种列表，不同的是队列只能在队尾插入元素，在队首删除元素。队列用于存储按 顺序排列的数据，先进先出，这点和栈不一样，在栈中，最后入栈的元素反而被优先处 理。
队列是一种先进先出(First-In-First-Out，FIFO)的数据结构。
队列的实现
在JavaScript中，我们可以用如下函数实现队列：
function Queue() {
this.dataStore = [];
this.enqueue = enqueue;
this.dequeue = dequeue;
this.front = front;
this.back = back;
this.toString = toString;
this.empty = empty;
this.count = count;
}
//enqueue() 方法向队尾添加一个元素:
function enqueue(element) {
this
.dataStore
.push(element);
}
// dequeue() 方法删除队首的元素:
function dequeue() {
return this
.dataStore
.shift();
}
// front() 读取队首元素：
function front() {
return this.dataStore[0];
}
// back 读取队尾的元素：
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;
}
}
//显示元素个数
function count() {
return this.dataStore.length;
}
实战
习题一
使用队列来模拟跳方块舞的人。当 男男女女来到舞池，他们按照自己的性别排成两队。当舞池中有地方空出来时，选两个队 列中的第一个人组成舞伴。他们身后的人各自向前移动一位，变成新的队首。当一对舞伴 迈入舞池时，主持人会大声喊出他们的名字。当一对舞伴走出舞池，且两排队伍中有任意 一队没人时，主持人也会把这个情况告诉大家。
代码如下：
// 模拟舞会成员
var dancers = [
'F Allison McMillan',
'M Frank Opitz',
'M Mason McMillan',
'M Clayton Ruff',
'F Cheryl Ferenback',
'M Raymond Williams',
'F Jennifer Ingram',
'M Bryan Frazer',
'M David Durr',
'M Danny Martin',
'F Aurora Adney'
];
//舞者
function Dancer(name, sex) {
this.name = name;
this.sex = sex;
}
// 对跳舞的成员按性别分组
function getDancers(males, females) {
var dancer,
sex,
name;
for (var i = 0; i < dancers.length - 1; i++) {
dancer = dancers[i].split(' ');
sex = dancer[0];
name = dancer[1];
if (sex === 'F') {
females.enqueue(new Dancer(name, sex));
} else {
males.enqueue(new Dancer(name, sex));
}
}
}
// 进入舞池跳舞
function dance(males, females) {
console.log('The dance partners are: \n');
var person;
while (!females.empty() && !males.empty()) {
person = females.dequeue();
console.log("Female dancer is: " + person.name);
person = males.dequeue();
console.log(" and the male dancer is: " + person.name);
}
}
var maleDancers = new Queue();
var femaleDancers = new Queue();
getDancers(maleDancers, femaleDancers);
dance(maleDancers, femaleDancers);
if (!femaleDancers.empty()) {
console.log(femaleDancers.front().name + " is waiting to dance.");
}
if (!maleDancers.empty()) {
console.log(maleDancers.front().name + " is waiting to dance.");
}
结果如下：
The dance partners are:
Female dancer is: Allison and the male dancer is: Frank
Female dancer is: Cheryl and the male dancer is: Mason
Female dancer is: Jennifer and the male dancer is: Clayton
Raymond is waiting to dance.
习题二
对于 0~99 的数字，基数排序将数据集扫描两次。第一次按个位上的数字进行排序，第二 次按十位上的数字进行排序。每个数字根据对应位上的数值被分在不同的盒子里。
用以上算法对数据进行排序。
思路：
我们需要九个队列，每个对应一个数字。将所有 队列保存在一个数组中，使用取余和除法操作决定个位和十位。算法的剩余部分将数字加 入相应的队列，根据个位数值对其重新排序，然后再根据十位上的数值进行排序，结果即 为排好序的数字。
// nums 要排序的数字数组。 queues 0-9队列数组 n 数字的个数 digit 按个位还是十位排序
function distribute(nums, queues, n, digit) {
for (var i = 0; i < n - 1; 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) {
console.log(arr);
}
var queues = [];
for (var i = 0; i < 10; i++) {
queues[i] = new Queue();
}
var nums = [];
// 随机生成10个数字
for (var i = 0; i < 10; i++) {
nums[i] = Math.floor(Math.random() * 101);
}
console.log("Before radix sort: ");
dispArray(nums);
distribute(nums, queues, 10, 1);
collect(queues, nums);
distribute(nums, queues, 10, 10);
collect(queues, nums);
console.log("\n\nAfter radix sort: ");
dispArray(nums);
结果可能如下：
Before radix sort:
[ 18, 80, 5, 71, 18, 78, 87, 61, 19, 38 ]
After radix sort:
[ 5, 18, 18, 19, 61, 71, 78, 80, 87, 38 ]
习题三
修改 Queue 类，形成一个 Deque 类。这是一个和队列类似的数据结构，允许从队列两端 添加和删除元素，因此也叫双向队列。写一段测试程序测试该类
Deque类的代码如下：
function Deque() {
this.dataStore = [];
this.enterFrontQueue = enterFrontQueue;
this.enterBackQueue = enterBackQueue;
this.delFrontQueue = delFrontQueue;
this.delBackQueue = delBackQueue;
this.front = front;
this.back = back;
this.toString = toString;
this.empty = empty;
this.count = count;
}
// enterFrontQueue 向队列头部添加元素
function enterFrontQueue(element) {
this.dataStore.unshift(element);
}
// enterBackQueue 向队列尾部添加元素
function enterBackQueue(element) {
return this.dataStore.push(element);
}
// delFrontQueue 从队列头部删除元素
function delFrontQueue() {
return this.dataStore.shift();
}
// delBackQueue 从队列尾部删除元素
function delBackQueue() {
this.dataStore.pop();
}
// front() 读取队首元素：
function front() {
return this.dataStore[0];
}
// back() 读取队尾元素：
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;
}
}
//显示元素个数
function count() {
return this.dataStore.length;
}
测试Deque类：
var d = new Deque();
d.enterBackQueue('a');
console.log(d.dataStore);
d.enterBackQueue('b');
console.log(d.dataStore);
d.enterFrontQueue('c');
console.log(d.dataStore);
d.enterFrontQueue('d');
console.log(d.dataStore);
d.enterFrontQueue('e');
console.log(d.dataStore);
d.enterBackQueue('f');
console.log(d.dataStore);
d.delBackQueue();
console.log(d.dataStore);
d.delFrontQueue();
console.log(d.dataStore);
结果如下：
[ 'a' ]
[ 'a', 'b' ]
[ 'c', 'a', 'b' ]
[ 'd', 'c', 'a', 'b' ]
[ 'e', 'd', 'c', 'a', 'b' ]
[ 'e', 'd', 'c', 'a', 'b', 'f' ]
[ 'e', 'd', 'c', 'a', 'b' ]
[ 'd', 'c', 'a', 'b' ]
习题四
使用前面完成的 Deque 类来判断一个给定单词是否为回文。
思路:
将字符串中的字符挨个推入双向队列中。然后每次弹出队列的首部元素和尾部元素进行比较。如果不相等，就说明不是回文。当双向队列中的元素只剩一个或一个不剩，循环结束。
代码如下：
function isPalindrome(word){
var deque = new Deque();
var result =true; //是否是回文。默认为true，即是回文。
for(var i=0;i<word.length;i++){
deque.enterBackQueue(word[i]);
}
while(deque.count()>1){
if(deque.delBackQueue() !== deque.delFrontQueue()){
result = false;
break;
}
}
return result;
}
console.log(isPalindrome('word')); // false
console.log(isPalindrome('pop')); // true
console.log(isPalindrome('woow')); // true