数据结构与算法 （队列实现篇）
在数据结构与算法中，队列(queue)是一种受限的线性储存结构，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。遵循先进先出（FIFO）的规则。
队列结构示意图
queue.png
队列结构使用
生活中很多地方使用到队列，例如医院门诊看病就是按挂号的号数来排队就诊；公司里面的打印机是按文件发送的顺序进行打印。
3.jpg
在编程中，队列常用作消息发送。例如消息发送队列。待发送的消息依次入队列，待一个消息出队列发送完毕，才会进行下一个消息出队列进行发送。
实现普通队列结构的功能
- push(element)：push是入队列操作，其中element是需要进队列的元素，返回操作成功与否布尔值。
- shift()：shift移除队列front元素操作，返回移除的移除元素。
- size()：获取栈中的队列元素数量，返回一个数字。
- isEmpty()：判断队列是否为空，返回一个布尔值。
- peek()：返回队头元素，但不移除栈顶元素。
- bottom()：返回队尾元素。
- clear()：清除所有队列元素，返回操作成功与否布尔值。
进队列与出队列流程
flow.png
ES6 队列结构代码
class Queue{
constructor(){
this.lists = [];
}
size(){
return this.lists.length;
}
isEmpty(){
return this.lists.length === 0;
}
peek(){
return this.list[0];
}
bottom(){
const topIndex = this.size() -1;
return this.lists[topIndex];
}
push(element){
this.lists.push(element);
return true;
}
shift(){
return this.lists.shift();
}
clear(){
this.lists = [];
return true;
}
toString(){
let result = "";
this.lists.forEach(value=>{
result = result + ""+value;
});
return result;
}
}
ES5 队列结构代码
通过ES5把功能函数可以绑定在对象的实例上，也可以把功能函数加在函数的原型链上
function Queue(){
this.lists = [];
}
Queue.prototype.push = function(element){
this.lists.push(element);
return true;
}
Queue.prototype.shift = function(){
return this.lists.shift();
}
Queue.prototype.clear = function(){
this.lists = [];
return true;
}
// 返回队头元素
Queue.prototype.peek = function(){
return this.lists[0];
}
Queue.prototype.size = function(){
return this.lists.length;
}
Queue.prototype.isEmpty = function(){
return this.lists.length === 0;
}
Queue.prototype.bottom = function(){
var topIndex = this.size() -1;
return this.lists[topIndex];
}
Queue.prototype.toString = function(){
var result = "";
for(var i=0;i<this.lists.length;i++){
result = result + '' +this.lists[i];
}
return result;
}
实现优先队列结构的功能
上面实现的是普通队列情况，在日常生活中总遇到需要紧急处理的情况，例如银行VIP客户，急诊室危急病人，紧急文件。这时候需要优先处理这种情况。
优先队列和普通队列的不同主要在优先队列的每一个元素都具有一个权值，代表该元素的优先权大小。还有就是根据权值大小插入队列之中。
prority.png
ES6 最大优先队列结构代码
class Node{
constructor(element,prority){
this.element = element;
this.prority = prority;
}
}
class Queue{
constructor(){
this.lists = [];
}
size(){
return this.lists.length;
}
isEmpty(){
return this.lists.length === 0;
}
peek(){
return this.list[0];
}
bottom(){
const topIndex = this.size() -1;
return this.lists[topIndex];
}
//插入队列
append(node){
//当队列为空时
if(this.lists.length == 0){
this.lists.push(node);
return true;
}else{
this.lists.forEach((val,index)=>{
if(node.prority > val["prority"]){
this.lists.splice(index,0,node);
return true;
}
if(index == this.lists.length){
this.lists.push(node);
return true;
}
});
}
}
shift(){
return this.lists.shift();
}
clear(){
this.lists = [];
return true;
}
toString(){
let result = "";
this.lists.forEach(value=>{
result = result + ""+value;
});
return result;
}
}
ES5 最大优先队列结构代码
通过ES5把功能函数可以绑定在对象的实例上，也可以把功能函数加在函数的原型链上
function Node(element,prority){
this.element = element;
this.prority = prority;
}
function Queue(){
this.lists = [];
}
Queue.prototype.append = function(node){
//当队列为空时
if(this.lists.length == 0){
this.lists.push(node);
return true;
}
for(var i=0;i<this.lists.length;i++){
if(node.prority > this.lists[i]["prority"]){
this.lists.splice(i,0,node);
return true;
}
if(i == this.lists.length){
this.lists.push(node);
return true;
}
}
}
Queue.prototype.shift = function(){
return this.lists.shift();
}
Queue.prototype.clear = function(){
this.lists = [];
return true;
}
// 返回队头元素
Queue.prototype.peek = function(){
return this.lists[0];
}
Queue.prototype.size = function(){
return this.lists.length;
}
Queue.prototype.isEmpty = function(){
return this.lists.length === 0;
}
Queue.prototype.bottom = function(){
var topIndex = this.size() -1;
return this.lists[topIndex];
}
Queue.prototype.toString = function(){
var result = "";
for(var i=0;i<this.lists.length;i++){
result = result + '' +this.lists[i];
}
return result;
}
循环队列结构图
循环队列就是把队头元素出队列后，再入队列。击鼓传花就是用到了循环队列的原理
image.png
image.png
循环队列代码
循环队列主要实现代码如下
class SqQueue {
constructor(length) {
this.queue = new Array(length + 1)
// 队头
this.first = 0
// 队尾
this.last = 0
// 当前队列大小
this.size = 0
}
enQueue(item) {
// 判断队尾 + 1 是否为队头
// 如果是就代表需要扩容数组
// % this.queue.length 是为了防止数组越界
if (this.first === (this.last + 1) % this.queue.length) {
this.resize(this.getLength() * 2 + 1)
}
this.queue[this.last] = item
this.size++
this.last = (this.last + 1) % this.queue.length
}
deQueue() {
if (this.isEmpty()) {
throw Error('Queue is empty')
}
let r = this.queue[this.first]
this.queue[this.first] = null
this.first = (this.first + 1) % this.queue.length
this.size--
// 判断当前队列大小是否过小
// 为了保证不浪费空间，在队列空间等于总长度四分之一时
// 且不为 2 时缩小总长度为当前的一半
if (this.size === this.getLength() / 4 && this.getLength() / 2 !== 0) {
this.resize(this.getLength() / 2)
}
return r
}
getHeader() {
if (this.isEmpty()) {
throw Error('Queue is empty')
}
return this.queue[this.first]
}
getLength() {
return this.queue.length - 1
}
isEmpty() {
return this.first === this.last
}
resize(length) {
let q = new Array(length)
for (let i = 0; i < length; i++) {
q[i] = this.queue[(i + this.first) % this.queue.length]
}
this.queue = q
this.first = 0
this.last = this.size
}
}
完成数据结构与算法队列篇。
网友评论