Toc
  1. 栈的创建
  2. 队列的创建
  3. 优先队列
  4. 循环队列
Toc
0 results found
FBB
数据结构之栈、队列
2019/03/21 数据结构

学习JavaScript数据结构与算法之栈和队列篇章。前端小白简单的学习笔记。

栈是一种遵从后进先出(LIFO)原则的有序集合。新添加的或待删除的元素都保存在栈的末尾,称作栈顶,另一端就叫栈底。在栈里,新元素都靠近栈顶,旧元素都接近栈底。

队列是遵循FIFO(First In First Out,先进先出,也称为先来先服务)原则的一组有序的项。队列在尾部添加新元素,并从顶部移除元素。最新添加的元素必须排在队列的末尾。

栈的创建

function Stack() {
  var items = []
  this.push = function (elememt) {   //负责往栈里添加新元素,该方法只添加元素到栈顶
    items.push(elememt)
  }
  this.pop = function () {     //用来移除栈里的元素,栈遵从LIFO原则,移出的是最后添加进去的元素
    return items.pop()
  }
  this.peek = function () {    //返回栈顶元素
    return items[items.length - 1]
  }
  this.isEmpty = function () {   //判断栈是否为空
    return items.length === 0
  }
  this.size = function () {   //返回栈的大小
    return items.length
  }
  this.clear = function () {    //用来移除栈里所有的元素,把栈清空
    items = [];
  };
}

队列的创建

function Queue() {
  var items = []
  this.enqueue = function (element) {    //这个方法负责向队列添加新元素,新的项只能添加到队列末尾
    items.push(element);
  }
  this.dequeue = function () {      //负责从队列移除项,由于队列遵循先进先出原则,先添加的项也是最先被移除的
    return items.shift();
  }
  this.front = function () {       //会返回队列最前面的项
    return items[0];
  }
  this.isEmpty = function () {      //判断队列是否为空
    return items.length == 0;
  }
  this.clear = function () {        //清空队列
    items = [];
  }
  this.size = function () {      //返回队列的大小
    return items.length;
  }
}

优先队列

元素的添加和删除基于优先级的。

function PriorityQueue() {
  var items = []
  function QueueElement(element, priority) {    //要添加的元素和元素的优先级
    this.element = element;
    this.priority = priority;
  }
  this.enqueue = function (element, priority) {
    var queueElement = new QueueElement(element, priority)
    if (this.isEmpty) {    //当队列为空的时候,直接添加元素
      item.push(queueElement)
    } else {
      var added = false
      for (var i = 0; i < items.length; i++) {
        if (queueElement.priority < items[i].priority) {         //添加元素的优先级和已有元素的优先级的比较
          items.splice(i, 0, queueElement)       //插入元素
          added = true
          break
        }
      }
      if (!added) {             //判断是否添加,如果没有的话,说明优先级最高,放到最后
        items.push(queueElement)
      }
    }
  }

  //其他方法和普通队列实现是一样的
}

循环队列

循环队列的一个例子就是击鼓传花游戏(HotPotato)。在这个游戏中,孩子们围成一个圆圈,把花尽快地传递给旁边的人。某一时刻传花停止,这个时候花在谁手里,谁就退出圆圈结束游戏。重复这个过程,直到只剩一个孩子(胜者)。

function hotPotato(nameList, num) {
  var queue = new queue()    //基本队列
  nameList.forEach(item => queue.enqueue(item))   //把数据放到队列里面
  var eliminated = ''   //初始化淘汰者的名字
  while (queue.size() > 1) {    //当队列里还有两个及其以上的元素
    for (var i = 0; i < num; i++) {
      queue.enqueue(queue.dequeue())     //从队列开头移除一项,再将其添加到队列末尾
    }
    eliminated = queue.dequeue()     //处于队列首位的就是淘汰者
    console.log('这次淘汰的人:' + eliminated)
  }
  return queue.dequeue()     //返回游戏的胜利者
}

至此,栈和队列的基本使用方法已经总结完毕。接下来会是链表的学习。👍

打赏
支付宝
微信
本文作者:FBB
版权声明:本文首发于FBB的博客,转载请注明出处!