04.md

队列

什么是队列

1. 队列是一种先进先出的数据结构
2. 队列相对于栈是在队尾插入元素，在队首删除元素
3. 插入的动作叫入队，删除的动作叫出队

队列的实现

普通队列

• 普通队列

function Queue() {
  this.storeData = [];
  this.enqueue = enqueue;
  this.dequeue = dequeue;
  this.front = front;
  this.back = back;
  this.toString = toString;
  this.isEmpty = isEmpty;
}
// 入队
var enqueue = function(value) {
  this.storeData.push(value);
};
// 出队
var dequeue = function() {
  return this.storeData.shift();
};
// 队首元素
var front = function() {
  return this.storeData[0];
};
// 队尾元素
var back = function() {
  return this.storeData.slice(-1);
};
// 显示队列
var toString = function() {
  return this.storeData.toString();
};
// 是否为空
var isEmpty = function() {
  return this.storeData.length === 0 ? true : false;
};

• 队列的排序方法：基数排序

// 1. 建立10个队列queues，10-99之间的10个数字nums
// 2. 先把相同个位的数组 push到第个数数值的队列中
// 3. 依次pop出来，赋值给nums
// 3. 再把相同十位的数字push到第十位数值的队列中
// 4. 依次pop出来，赋值给nums
// 5. 这种方法，必须按个十都要排
function distribute(queues, nums, n, d) {
  for (var i = 0; i < 10; i++) {
    var a;
    if (d === 1) {
      a = parseInt(nums[i] % 10);
      queues[a].enqueue(nums[i]);
    } else if (d == 10) {
      a = parseInt((nums[i] / 10) % 10);
      queues[a].enqueue(nums[i]);
    } else if (d === 100) {
      a = parseInt((nums[i] / 10 / 10) % 10);
      queues[a].enqueue(nums[i]);
    }
  }
}
function collect(queues, nums) {
  var n = 0;
  for (var i = 0; i < 10; i++) {
    while (!queues[i].isEmpty()) {
      nums[n] = queues[i].dequeue();
      n++;
    }
  }
}
function random(min, max) {
  return parseInt(min + Math.random() * (max + 1 - min));
}
var queues = [];
for (var i = 0; i < 10; i++) {
  queues[i] = new Queue();
}
var nums = [];
for (var i = 0; i < 10; i++) {
  // nums[i] = random(10, 99);
  nums[i] = random(10, 999);
}
// console.log("begain", nums.toString());
// distribute(queues, nums, 10, 1);
// for (var i = 0; i < queues.length; i++) {
//   console.log("middle-queue-" + (i + 1), queues[i].storeData);
// }
// collect(queues, nums);
// console.log("middle", nums.toString());
// distribute(queues, nums, 10, 10);
// for (var i = 0; i < queues.length; i++) {
//   console.log("end-queue" + (i + 1), queues[i].storeData);
// }
// collect(queues, nums);
// console.log("end", nums.toString());
distribute(queues, nums, 10, 1);
collect(queues, nums);
distribute(queues, nums, 10, 10);
collect(queues, nums);
distribute(queues, nums, 10, 100);
collect(queues, nums);
console.log(nums);

优先队列

function Queue2() {
  this.code = 6;
  this.storeData = [];
  this.enqueue = enqueue;
  this.dequeue = dequeue;
  this.front = front;
  this.back = back;
  this.toString = toString;
  this.isEmpty = isEmpty;
}
// 入队
var enqueue = function(value) {
  this.storeData.push(value);
};
// 出队
var dequeue = function() {
  var arr = this.storeData;
  for (var i = 0; i < arr.length; i++) {
    arr[i].code >= this.code && arr.splice(i, 1);
  }
};
// 队首元素
var front = function() {
  return this.storeData[0];
};
// 队尾元素
var back = function() {
  return this.storeData.slice(-1);
};
// 显示队列
var toString = function() {
  var arr = this.storeData;
  var result = "";
  for (var i = 0; i < arr.length; i++) {
    result += "-" + arr[i].code;
  }
  return result;
};
// 是否为空
var isEmpty = function() {
  return this.storeData.length === 0 ? true : false;
};

var q2 = new Queue2();
q2.enqueue({ code: 5 });
q2.enqueue({ code: 4 });
q2.enqueue({ code: 6 });
q2.enqueue({ code: 1 });
q2.enqueue({ code: 1 });
q2.dequeue();
q2.dequeue();
q2.dequeue();
q2.dequeue();
q2.dequeue();
q2.dequeue();
q2.dequeue();
console.log(q2.toString());

双向队列

js 中的数组可以 pop、shift、push、unshift，所以双向队列也变得简单