javascript实现数据结构与算法系列:队列 -- 链队列和循环队列实现及示例

时间:2022-09-21 19:54:56

1 队列的基本概念

队列(Queue):也是运算受限的线性表。是一种先进先出(First In First Out ,简称FIFO)的线性表。只允许在表的一端进行插入,而在另一端进行删除。

队首(front) :允许进行删除的一端称为队首。

队尾(rear) :允许进行插入的一端称为队尾。   

例如:排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。

队列中没有元素时称为空队列。在空队列中依次加入元素a1, a2, …, an之后,a1是队首元素,an是队尾元素。显然退出队列的次序也只能是a1, a2, …, an ,即队列的修改是依先进先出的原则进行的

利用一组连续的存储单元(一维数组) 依次存放从队首到队尾的各个元素,称为顺序队列。

队列的链式存储结构简称为链队列,它是限制仅在表头进行删除操作和表尾进行插入操作的单链表。

链队列结构图:

javascript实现数据结构与算法系列:队列 -- 链队列和循环队列实现及示例

链队列的表示:

 function Queue() {
this.rear = this.front = null;
this.size = 0;
}
exports.Queue = Queue;
Queue.prototype = {
clear: function () {
this.rear = this.front = null;
this.size = 0;
},
getHead: function () {
return this.front ? this.front.data : null;
},
enQueue: function (elem) {
if (this.front === null) {
this.rear = this.front = {data: elem, next: null};
} else {
var p = {data: elem, next: null};
this.rear.next = p;
this.rear = p;
}
this.size++;
},
deQueue: function () {
if (this.front) {
var elem = this.front.data;
this.front = this.front.next;
if (this.front === null) {
this.rear = null;
}
this.size--;
return elem;
} else {
return null;
}
},
queueTraverse: function (iterator) {
var current = this.front;
while (current) {
if (iterator(current.data)) break;
current = current.next;
}
},
peekAt: function (index) {
index = index || 0; if (index < this.size) {
var current = this.front;
for (var i = 0; i < index; i++) {
current = current.next;
}
return current.data;
} return null;
},
displayAll: function () {
if (this.front === null) {
return null;
} var arr = [];
var current = this.front; for (var i = 0, len = this.size; i < len; i++) {
arr[i] = current.data;
current = current.next;
} return arr;
}
}; var queue = new Queue();
queue.enQueue(1);
queue.deQueue();
queue.enQueue(2);
queue.enQueue(3);
console.log(queue.peekAt(0));
console.log(queue.peekAt(1));
console.log(queue.peekAt(2));
console.log(queue.peekAt(3));
console.log(queue.displayAll().join());

循环队列

顺序队列中存在“假溢出”现象。因为在入队和出队操作中,头、尾指针只增加不减小,致使被删除元素的空间永远无法重新利用。因此,尽管队列中实际元素个数可能远远小于数组大小,但可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假溢出。

为充分利用向量空间,克服上述“假溢出”现象的方法是:将为队列分配的向量空间看成为一个首尾相接的圆环,并称这种队列为循环队列(Circular Queue)。

在循环队列中进行出队、入队操作时,队首、队尾指针仍要加1,朝前移动。只不过当队首、队尾指针指向向量上界(MAX_QUEUE_SIZE-1)时,其加1操作的结果是指向向量的下界0。

用模运算可简化为:i=(i+1)%MAX_QUEUE_SIZE ;

显然,为循环队列所分配的空间可以被充分利用,除非向量空间真的被队列元素全部占用,否则不会上溢。因此,真正实用的顺序队列是循环队列。

例:设有循环队列QU[0,5],其初始状态是front=rear=0,各种操作后队列的头、尾指针的状态变化情况如下图:

javascript实现数据结构与算法系列:队列 -- 链队列和循环队列实现及示例

javascript实现数据结构与算法系列:队列 -- 链队列和循环队列实现及示例

入队时尾指针向前追赶头指针,出队时头指针向前追赶尾指针,故队空和队满时头尾指针均相等。因此,无法通过front=rear来判断队列“空”还是“满”。解决此问题的方法是:约定入队前,测试尾指针在循环意义下加1后是否等于头指针,若相等则认为队满。即:

◆ rear所指的单元始终为空。

◆ 循环队列为空:front=rear 。

◆ 循环队列满:(rear+1)%MAX_QUEUE_SIZE =front。

循环队列结构图:

javascript实现数据结构与算法系列:队列 -- 链队列和循环队列实现及示例

循环队列的表示:

 // 循环队列
function CycleQueue() {
this.base = {};
this.front = this.rear = 0;
this.MAXQSIZE = 100;
}
exports.CycleQueue = CycleQueue;
CycleQueue.prototype = {
enQueue: function (data) {
if ((this.rear + 1) % this.MAXQSIZE === 0) throw new Error('cycleQueue is already full!'); this.base[this.rear] = data;
this.rear = (this.rear + 1) % this.MAXQSIZE;
},
deQueue: function () {
if (this.front === this.rear) throw new Error('cycleQueue is already empty'); var elem = this.base[this.front];
this.front = (this.front + 1) % this.MAXQSIZE; return elem;
},
clear: function () {
this.base = {};
this.front = this.rear = 0;
},
size: function () {
return (this.rear - this.front + this.MAXQSIZE) % this.MAXQSIZE;
},
peekAt: function (index) {
index = (index || 0 + this.MAXQSIZE) % this.MAXQSIZE; return this.base[index + this.front] || null;
},
getHead: function () {
var elem = this.base[this.front];
return elem ? elem : null;
},
queueTraverse: function (iterator) {
for (var i = this.front, len = this.rear = this.front; i < len; i++) {
if (iterator(this.base[i], i)) break;
}
},
displayAll: function () {
var base = [].slice.call(this.base); return base.slice(this.front, this.rear - this.front);
}
}; var queue = new CycleQueue();
queue.enQueue(1);
queue.deQueue();
queue.enQueue(2);
queue.enQueue(3);
console.log(queue.peekAt(0));
console.log(queue.peekAt(1));
console.log(queue.peekAt(2));

单元测试代码:

 //var Queue = require('./Queue').Queue;
//var CycleQueue = require('./Queue').CycleQueue; describe('Queue tests', function(){
var queue = new Queue(); it('should enqueue 1', function(){
queue.enQueue(1);
expect(queue.getHead()).toBe(1);
expect(queue.size).toBe(1);
expect(queue.rear).toBe(queue.front);
}); it('should be an empty queue', function(){
queue.deQueue();
expect(queue.getHead()).toBe(null);
expect(queue.size).toBe(0);
expect(queue.rear).toBe(null);
expect(queue.front).toBe(null);
}); it('should enqueue 2 elems', function(){
queue.enQueue(2);
expect(queue.getHead()).toBe(2);
expect(queue.size).toBe(1);
queue.enQueue(3);
expect(queue.front.next.data).toBe(3);
expect(queue.size).toBe(2); expect(queue.rear.data).toBe(3);
expect(queue.front.data).toBe(2);
}); var queue2 = new CycleQueue(); it('should insert an element into cycleQueue, and then delete it, lastly it must be an empty queue', function(){
queue2.enQueue(1);
expect(queue2.front).toBe(0);
expect(queue2.rear).toBe(1);
expect(queue2.base[queue2.front]).toBe(1);
expect(queue2.base[queue2.rear]).toBe(undefined);
expect(queue2.getHead()).toBe(1);
expect(queue2.size()).toBe(1); queue2.deQueue();
expect(queue2.front).toBe(1);
expect(queue2.rear).toBe(queue2.front);
expect(queue2[this.front]).toBe(undefined);
expect(queue2.size()).toBe(0);
}); it('should insert into two elements into cycleQueue, and peek them in order', function(){
queue2.enQueue(2);
expect(queue2.front).toBe(1);
expect(queue2.rear).toBe(2);
expect(queue2.base[queue2.front]).toBe(2);
expect(queue2.base[queue2.rear]).toBe(undefined); queue2.enQueue(3);
expect(queue2.rear).toBe(3);
expect(queue2.base[queue2.front]).toBe(2);
expect(queue2.base[queue2.front + 1]).toBe(3);
expect(queue2.base[this.rear]).toBe(undefined);
expect(queue2.peekAt(0)).toBe(2);
expect(queue2.peekAt(1)).toBe(3);
expect(queue2.peekAt(2)).toBe(null);
}); });

示例1:离散事件模拟,利用链表和队列模拟银行业务程序

假设某银行有4个窗口对外接待客户,从早晨银行开门起不断有客户进入银行。由于每个窗口在某个时刻只能接待一个客户,因此在客户人数众多时需在每个窗口前顺次排队们对于刚进入银行的客户,如果某个窗口的业务员正空闲,则可上前办理业务。反之,若4个窗口均有客户所占,他便会排在人数最少的队伍后面。现在需要编制一个程序以模拟银行的这种业务活动并计算一天中客户的银行逗留的平均时间。

 var List = require('../linkedList/complete-LinkedList');
var Queue = require('./Queue').Queue; // 事件类型,有序链表LinkList的数据元素类型
function Event(occurTime, eventType) {
// 事件发生时刻
this.occurTime = occurTime || 0;
// 事件类型,0表示到达事件,1至4表示四个窗口的离开事件
this.eventType = eventType || 0;
} // 队列的数据元素类型
function QueueElemType(arrivalTime, duration) {
// 到达时刻
this.arrivalTime = arrivalTime || 0;
// 办理事务所需时间
this.duration = duration || 0;
} function Bank() {
// 事件表
this.eventList = null;
this.event = null;
// 4个客户队列
this.queues = new Array(4);
this.totalTime = 0;
this.customerNum = 0;
this.closeTime = 0;
}
Bank.prototype = {
cmp: function (event1, event2) {
if (event1.occurTime < event2.occurTime)
return -1;
else if (event1.occurTime === event2.occurTime)
return 0;
else
return 1;
},
// 初始化操作
openForDay: function () {
// 初始化累计时间和客户数为0
this.totalTime = 0;
this.customerNum = 0;
// 初始化事件链表
this.eventList = new List();
// 设定第一个用户到达事件
this.event = new Event(0, 0);
// 插入到事件表
this.eventList.orderInsert(this.event, this.cmp); // 置空队列
for (var i = 0, len = this.queues.length; i < len; i++)
this.queues[i] = new Queue();
},
// 处理客户到达事件
customerArrived: function (durtime, intertime) {
++this.customerNum; // 生成随机数
durtime = durtime || Math.floor(Math.random() * 20) + 1; // 办理业务所需时间
intertime = intertime || Math.floor(Math.random() * 5) + 1; // 两个相邻客户时间间隔
// 下一客户到达时刻
var t = this.event.occurTime + intertime;
// 银行尚未关门,插入事件表,这里还包括客户的离开时间
if (t < this.closeTime && t + durtime < this.closeTime) {
this.eventList.orderInsert(new Event(t, 0), this.cmp);
} // 求长度最短队列
var minQueueIndex = 0;
var allEqualed = false;
for(var i = 0, len = this.queues.length; i < len && this.queues[i + 1]; i++){
if(this.queues[i].size === 0) {
minQueueIndex = i;
break;
}
if(this.queues[i].size < this.queues[i + 1].size){
minQueueIndex = i;
allEqualed = false;
} else if(this.queues[i].size < this.queues[i + 1].size){
minQueueIndex = i;
allEqualed = true;
} else {
minQueueIndex = i + 1;
allEqualed = false;
}
}
// 如果所有队列长度都相等,取第一个
if(allEqualed) minQueueIndex = 0; this.queues[minQueueIndex]
.enQueue(new QueueElemType(this.event.occurTime, durtime)); // 设定第i队列的一个离开事件并插入事件表
if (this.queues[minQueueIndex].size === 1) {
this.eventList.orderInsert(new Event(this.event.occurTime + durtime, minQueueIndex + 1), this.cmp);
}
// 保存最新客户的到达时间
this.event.occurTime = t;
},
// 处理客户离开事件
customerDeparture: function (type) {
// 删除第i队列的排头客户
var i = type - 1 || 0;
var customer = this.queues[i].deQueue();
// 累计客户逗留时间
this.totalTime += this.event.occurTime - customer.arrivalTime; // 设定第i队列的一个离开事件并插入事件表
if (this.queues[i].size) {
customer = this.queues[i].getHead();
this.eventList.orderInsert(new Event(this.event.occurTime + customer.duration, i), this.cmp);
}
},
simulation: function (closeTime) {
this.closeTime = closeTime || 0;
this.openForDay();
while (this.eventList.head) {
var elem = this.eventList.delFirst().data;
if (elem.eventType === 0)
this.customerArrived();
else
this.customerDeparture(elem.eventType);
}
console.log('The average time is ' + this.totalTime / this.customerNum);
}
}; new Bank().simulation(20);

假设每个客户办理业务时间不超过20分钟;两个相邻到达银行的客户的时间间隔不超过5分钟。模拟程序从第一个客户到达时间为0开始运行。

删除事件表上地一个结点,得到event.occurTime = 0,因为event.eventType = 0,则随即得到两个随机数(23, 4),生成下一个客户到达银行的事件Event(occurTime = 4, eventType = 0)插入事件表;刚到的第一位客户排在第一个窗口的队列中QueueElemType(arrivalTime = 0, duration = 23),

由于他是排头,故生成一个客户将离开的事件Event(occurTime = 23, eventType = 1)插入事件表。

删除时间表上第一个结点,仍是新客户到达事件(因为event.eventType = 0),event.occurTime = 4,得到随机数为(3, 1),则下一个客户到达银行的时间为occurTime = 4 + 1 = 5,由于此时第二个窗口是空的,刚到的第二位客户为第二个队列的队头QueueElemType(arrivalTime = 4, duration = 3),因而生成一个客户将离开的事件Event(occurTime = 7, eventType = 2)插入事件表。

其他以此类推,直到银行关门时间结束程序。

javascript实现数据结构与算法系列:队列 -- 链队列和循环队列实现及示例的更多相关文章

  1. javascript实现数据结构与算法系列:栈 -- 顺序存储表示和链式表示及示例

    栈(Stack)是限定仅在表尾进行插入或删除操作的线性表.表尾为栈顶(top),表头为栈底(bottom),不含元素的空表为空栈. 栈又称为后进先出(last in first out)的线性表. 堆 ...

  2. javascript实现数据结构与算法系列

    1.线性表(Linear list) 线性表--简单示例及线性表的顺序表示和实现 线性表--线性链表(链式存储结构) 线性表的静态单链表存储结构 循环链表与双向链表 功能完整的线性链表 线性链表的例子 ...

  3. javascript实现数据结构与算法系列:循环链表与双向链表

    循环链表(circular linked list) 是另一种形式的链式存储结构.它的特点是表中最后一个结点的指针域指向头结点,整个表形成一个环. 循环链表的操作和线性链表基本一致,仅有细微差别. w ...

  4. javascript实现数据结构与算法系列:线性表的静态单链表存储结构

    有时可借用一维数组来描述线性链表,这就是线性表的静态单链表存储结构. 在静态链表中,数组的一个分量表示一个结点,同时用游标(cur)代替指针指示结点在数组中的相对位置.数组的第0分量可看成头结点,其指 ...

  5. javascript实现数据结构与算法系列:功能完整的线性链表

    由于链表在空间的合理利用上和插入,删除时不需要移动等的有点,因此在很多场合下,它是线性表的首选存储结构.然而,它也存在着实现某些基本操作,如求线性表长度时不如顺序存储结构的缺点:另一方面,由于在链表中 ...

  6. JavaScript 版数据结构与算法(二)队列

    今天,我们要讲的是数据结构与算法中的队列. 队列简介 队列是什么?队列是一种先进先出(FIFO)的数据结构.队列有什么用呢?队列通常用来描述算法或生活中的一些先进先出的场景,比如: 在图的广度优先遍历 ...

  7. Javascript数据结构与算法--队列&lpar;顺序队列、优先队列、循环队列&rpar;的实现与用法

    前言 队列和栈非常类似,前面已经讲过了栈的实现与用法,现在我们来说说队列. 队列介绍 队列遵循FIFO(First In First Out,先进先出)原则的一组有序的项. 队列是一种特殊的线性表,特 ...

  8. 【学习总结】java数据结构和算法-第三章-稀疏数组和队列

    相关链接 [学习总结]尚硅谷2019java数据结构和算法 github:javaDSA 目录 稀疏数组 队列 稀疏数组 稀疏数组介绍 图示 应用实例 代码实现 SparseArray.java:与二 ...

  9. 数据结构与算法系列2 线性表 链表的分类&plus;使用java实现链表&plus;链表源码详解

    数据结构与算法系列2.2 线性表 什么是链表? 链表是一种物理存储单元上非连续,非顺序的存储结构,数据元素的逻辑顺序是通过链表的链接次序实现的一系列节点组成,节点可以在运行时动态生成,每个节点包括两个 ...

随机推荐

  1. angular实现统一的消息服务

    后台API返回的消息怎么显示更优雅,怎么处理才更简洁?看看这个效果怎么样? 自定义指令和服务实现 自定义指令和服务实现消息自动显示在页面的顶部,3秒之后消失 1. 显示消息 这种显示消息的方式是不是有 ...

  2. jQuery 基础&lpar;4&rpar;jQuery 尺寸

    jQuery 尺寸方法jQuery 提供多个处理尺寸的重要方法:width()height()innerWidth()innerHeight()outerWidth()outerHeight()jQu ...

  3. 关于limit hashlimit资料整理

    这几天正在捣鼓防火墙,用到了hashlimit模块.Google了一圈发现相关的文档无论英文还 是中文都很少, 所以我就把自己的折腾的心得记录下来吧. hashlimit是iptables的一个匹配模 ...

  4. ELF

    http://www.360doc.com/content/11/0826/13/7588214_143424472.shtml 链接,装载都是基于数据结构ELF.

  5. inotify-java linux系统监听文件发生变化,实时通知java程序

    1 Overview     最近公司的一个任务需要实时监控文件系统中某个文件的内容变化.由于程序本身由Java编写,因此使用了inotify- java(http://code.google.com ...

  6. JS前端验证代码

    手机号码正则表达式验证: function checkPhone(){ var phone = document.getElementById('phone').value; if(!(/^1[345 ...

  7. PostgreSQL两种分页方法查询时间比较

    数据库中存了3000W条数据,两种分页查询测试时间 第一种 SELECT * FROM test_table WHERE i_id> limit 100; Time: 0.016s 第二种 SE ...

  8. Overture如何更改音符符尾设置

    Overture作为一款专业的五线谱打谱软件,深受每一个音乐爱好者喜爱.在我们使用Overture来进行打谱操作时,往往会遇到下面这种情况:我们一般打上两个八分音符时,软件会自动符尾相连,但当我们连续 ...

  9. 谈谈《Dotnet core结合jquery的前后端加密解密密码密文传输的实现》一文中后端解密失败的原因

    详情请看<Dotnet core结合jquery的前后端加密解密密码密文传输的实现>,正常来讲,这个博客里面的代码是没有问题的,但是我有时候却会直接报错,原因是后台解密失败:Interna ...

  10. 水塘抽样&lpar;Reservoir Sampling&rpar;问题

    水塘抽样是一系列的随机算法,其目的在于从包含n个项目的集合S中选取k个样本,其中n为一很大或未知的数量,尤其适用于不能把所有n个项目都存放到主内存的情况. 在高德纳的计算机程序设计艺术中,有如下问题: ...