JavaScript队列的应用实例详解【经典数据结构】

本文实例讲述了JavaScript队列的应用。分享给大家供大家参考，具体如下：

和前面介绍的栈相反，队列是一种先进先出的线性表，它只允许在表的一端进行插入，而在另一端进行删除。JavaScript自己提供了两个队列方法shift和push方法，分别是出队和入队，其原理就是将元素插入数组最后一个和删除第一个元素。

这里需要注意一点，就是unshift方法的效率比push的效率要低很多。因为它要将入队之前的数组全部往前移动一位。这里我们就不用代码再次演示了。

和线性表类似，队列也分为顺序队列和链队列。

和顺序栈类似，在队列的顺序存储结构中，除了使用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，还要设置两个指针front和rear分别指向队列头元素和队列尾元素。初始化时，front=rear=0；插入元素时，rear+1；删除元素时，front+1。所以在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置。

队列的应用有哪些呢？

我们先看看计算机组成层面的吧，首先就是CPU资源的竞争问题。在具有多个终端的计算机系统中，有多个用户需要使用CPU来各自运行程序，操作系统会按照每个请求在时间上的顺序，加请求排成一个队列。每次把CPU分配给队头的任务，完成后使其出队，然后依次。

第二个例子就是主机与外部设备之间速度不匹配的问题。我们以打印机和主机为例。主机输出数据给打印机打印，主机输出数据的速度远大于打印机打印速度，所以有一个打印数据缓冲区，主要把数据依次写入缓冲区，写满后主机就暂停输出，继而去做其他时间，只到打印机完成打印，再次请求主机发送数据，主机才继续输出数据。这样利用队列可以提高主机的效率。

我在这里挑一个常见的软件层面的例子，也就是银行排队问题。先说说实现思路，第一个客户到达的时刻为0，之后每个客户到达的时刻在前一个客户到达时设定随机值，因此在客户到达时需要产生两个随机数，一个是客户办理业务耗时durtime，一个是下一客户到达时间间隔intertime，假设当前时间为occurtime，则下一客户到达时为occurtime+intertime。

刚到达的客户应该插入到当前含元素最少的队列中。

在JavaScript的运用中，通常使用队列来进行任务的排序。而任务队列的任务是按进入队列的顺序延迟执行(解决状态一致性)的，即当前一个任务完成后，后面的任务才被执行，如果当前没有任务，则入队列的任务立即执行。代码如下：

<!DOCTYPE html>
<html>
 <head>
  <meta charset="utf-8">
  <title>队列</title>
 </head>
 <body>
<script type="text/javascript">
 function taskQueue() {
  taskList = [];
  var isRun = false;
  this.addTask = function (task) {
  taskList.push(task);
  };
  setInterval(function () {
  if (taskList.length > 0 && !isRun) {
   isRun = true;
   taskList.shift();
   isRun = false;
  }
  }, 100);
 }
 function show(){
  alert(taskList);
 }
  taskQueue();
  addTask(1);
  addTask(2);
  addTask(3);
  setTimeout('show()',99);//1,2,3
  setTimeout('show()',101);//2,3
  setTimeout('show()',400);//null
</script>
 </body>
</html>

更多关于JavaScript相关内容感兴趣的读者可查看本站专题：《JavaScript数据结构与算法技巧总结》、《JavaScript数学运算用法总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》

希望本文所述对大家JavaScript程序设计有所帮助。

赞 (0)

相关推荐

  • JavaScript数据结构与算法之栈与队列

    学习起因 曾经有一次在逛V2EX时,碰到这么一个帖子. 数学完全还给老师了,想学回一些基础数学,大概是高中程度的,有什么书籍推荐? 发帖的楼主大学没有高数课程,出去工作时一直在从事前端的工作.感觉到数学知识的匮乏,所以想补一补数学. 看了看帖子,感觉和我很像,因为我的专业是不开高数的,我学的也是前端.也同样感觉到了数学知识匮乏所带来的困顿.同时因为自己的数学思维实在是不怎么好,所以决定努力补习数学与计算机基础知识. 当时也有人说:"前端需要什么数据结构与算法",但是对于这个事情我有自己

  • JavaScript数据结构之链表的实现

    JavaScript数据结构之链表的实现

    前面楼主分别讨论了数据结构栈与队列的实现,当时所用的数据结构都是用的数组来进行实现,但是数组有的时候并不是最佳的数据结构,比如在数组中新增删除元素的时候需要将其他元素进行移动,而在javascript中使用spit()方法不需要访问其他元素.如果你在使用数组的时候发现很慢,就可以考虑使用链表. 链表的概念 链表是一种常见的数据结构.它是动态地进行存储分配的一种结构.链表有一个"头指针"变量,以head表示,它存放一个地址,指向一个元素.每个结点都使用一个对象的引用指标它的后继,指向另一

  • JavaScript数据结构和算法之二叉树详解

    JavaScript数据结构和算法之二叉树详解

    二叉树的概念 二叉树(Binary Tree)是n(n>=0)个结点的有限集合,该集合或者为空集(空二叉树),或者由一个根结点和两棵互不相交的.分别称为根结点的左子树和右子树的二叉树组成. 二叉树的特点 每个结点最多有两棵子树,所以二叉树中不存在度大于2的结点.二叉树中每一个节点都是一个对象,每一个数据节点都有三个指针,分别是指向父母.左孩子和右孩子的指针.每一个节点都是通过指针相互连接的.相连指针的关系都是父子关系. 二叉树节点的定义 二叉树节点定义如下: 复制代码 代码如下: struct

  • JavaScript数据结构学习之数组、栈与队列

    前言 数据结构就是关系,没错,就是数据元素相互之间存在的一种或多种特定关系的集合. 常用的数据结构有: 数组,队列(queue),堆(heap),栈(stack),链表(linked list ),树(tree),图(graph)和散列表(hash) 本文主要介绍的是数组.栈与队列,下面来一起看看详细的介绍吧. 一.数组 数组是平时使用最常用的数据结构,在JavaScript中数组是动态的分配大小,在这里我不会介绍JavaScript里面数组的所有的方法,而是针对数据结构这个方向谈谈所用到的方法

  • JS实现队列与堆栈的方法

    JS实现队列与堆栈的方法

    本文实例讲述了JS实现队列与堆栈的方法.分享给大家供大家参考,具体如下: 在面向对象的程序设计里,一般都提供了实现队列(queue)和堆栈(stack)的方法,而对于JS来说,我们可以实现数组的相关操作,来实现队列和堆栈的功能,看下面的相关介绍. 一.看一下它们的性质,这种性质决定了它们的使用场合 队列:是一种支持先进先出(FIFO)的集合,即先被插入的数据,先被取出! 堆栈:是一种支持后进先出(LIFO)的集合,即后被插入的数据,先被取出! 二.看一下实现的代码(JS代码) var a=new

  • JavaScript队列、优先队列与循环队列

    JavaScript队列、优先队列与循环队列

    队列是一种遵从先进先出(FIFO)原则的有序集合 队列在尾部添加新元素,从顶部移除元素 队列的理解 队列在我们生活中最常见的场景就是排队了 队列这个名字也已经很通俗易懂了 和栈很像,这不过队列是先入先出的数据结构 队列的前面是队头 队列的后面是队尾 出队从队头出 入队从队尾入 队列的创建 和栈类似,这里我就不就不啰嗦了 同样需要实现一些功能 这里我类比生活中的排队上厕所 向队列中添加元素(进入排队的队伍中) 移除队头元素(队伍最前面的人出队进入厕所) 查看队头元素(查看队伍最前面的人) 判断队列

  • javascript中利用数组实现的循环队列代码

    //循环队列 function CircleQueue(size){ this.initQueue(size); } CircleQueue.prototype = { //初始化队列 initQueue : function(size){ this.size = size; this.list = new Array(); this.capacity = size + 1; this.head = 0; this.tail = 0; }, //压入队列 enterQueue : functio

  • JavaScript数据结构之优先队列与循环队列实例详解

    JavaScript数据结构之优先队列与循环队列实例详解

    本文实例讲述了JavaScript数据结构之优先队列与循环队列.分享给大家供大家参考,具体如下: 优先队列 实现一个优先队列:设置优先级,然后在正确的位置添加元素. 我们这里实现的是最小优先队列,优先级的值小(优先级高)的元素被放置在队列前面. //创建一个类来表示优先队列 function Priorityqueue(){ var items=[];//保存队列里的元素 function QueueEle(e,p){//元素节点,有两个属性 this.element=e;//值 this.pr

  • JavaScript数组的栈方法与队列方法详解

    JavaScript数组的栈方法与队列方法详解

    数组(Array)和对象(Object)应该是JavaScript中使用最多也是最频繁的两种类型了,Array提供了很多常用的方法:栈方法.队列方法.重排序方法.操作方法.位置方法.迭代方法等等. 1.Array的栈方法 栈是一种LIFO(Last-In-First-Out,后进先出)的数据结构,也就是最新添加的项最早被移除.栈中项的插入(push)和移除,只发生在一个位置--栈的顶部.ECMAScript为数组提供了push()和pop()方法,可以实现类似栈的行为.下面两图分别演示了入栈与出

  • JS实现队列的先进先出功能示例

    本文实例讲述了JS实现队列的先进先出功能.分享给大家供大家参考,具体如下: /** * [Queue] * @param {[Int]} size [队列大小] */ function Queue(size) { var list = []; //向队列中添加数据 this.push = function(data) { if (data==null) { return false; } //如果传递了size参数就设置了队列的大小 if (size != null && !isNaN(s

  • Javascript数据结构与算法之列表详解

    Javascript数据结构与算法之列表详解

    前言:在日常生活中,人们经常要使用列表,比如我们有时候要去购物时,为了购物时东西要买全,我们可以在去之前,列下要买的东西,这就要用的列表了,或者我们小时候上学那段时间,每次考完试后,学校都会列出这次考试成绩前十名的同学的排名及成绩单,等等这些都是列表的列子.我们计算机内也在使用列表,那么列表适合使用在什么地方呢?不适合使用在什么地方呢? 适合使用在:当列表的元素不是很多的情况下,可以使用列表,因为对列表中的元素查找或者排序时,效率还算非常高,反之:如果列表元素非常多的情况下,就不适合使用列表了.

随机推荐