当前位置:   article > 正文

数据结构与算法——队列、栈、列表(理论+实现)_队列是列表吗

队列是列表吗

队列

队列是一种列表,用于存储按顺序排列的数据。

先进先出。在一端进行插入,在另外一端进行删除。插入的一端称为队尾,删除的一端称为队头,先进队列的元素优先处理。

应用

可以将队列想象成排队的人群。队列用在很多地方,例如:提交操作系统执行的一系列操作等等

属性

队列没有自定义属性,通常用数组来模拟队列,直接使用的是数组的一些属性,比如length等。

实现代码

/**
 * 队列构造函数
 */
 function Queue() {

    /**
     * 用数组来模拟队列
     * @type {Array}
     */
    var items = [];
  
    /**
     * 将元素推入队列
     * @param  {Any} ele 要推入队列的元素
     */
    this.enqueue = function(ele) {
      items.push(ele);
    };
  
    /**
     * 将队列中第一个元素弹出
     * @return {Any} 返回被弹出的元素
     */
    this.dequeue = function() {
      return items.shift()  //shift()删除数组的第一个元素
    };
  
    /**
     * 查看队列的第一个元素
     * @return {Any} 返回队列中第一个元素
     */
    this.front = function() {
      return items[0];
    };
  
    /**
     * 确定队列是否为空
     * @return {Boolean} 若队列为空则返回true,不为空则返回false
     */
    this.isAmpty = function() {
      return items.length === 0
    };
  
    /**
     * 返回队列的长度
     * @return {Number} 队列的长度
     */
    this.size = function() {
      return items.length;
    };
  
    /**
     * 清空队列中所有内容
     */
    this.clear = function() {
      items = [];
    };
  
    /**
     * 以字符串显示队列中所有内容
     */
    this.print = function() {
      console.log(items.toString());
    };
  }
  
  /**
   * 击鼓传花的小游戏
   * @param  {Array} nameList 参与人员列表
   * @param  {Number} num  在循环中要被弹出的位置
   * @return {String}    返回赢家(也就是最后活下来的那个)
   */
  function hotPotato(nameList, num) {
    var queue = new Queue();
  
    for (var i = 0; i < nameList.length; i++) {
      queue.enqueue(nameList[i]);
    }
  
    var eliminated = '';
  
    while (queue.size() > 1) {
      for (var i = 0; i < num; i++) {
        queue.enqueue(queue.dequeue());
      }
  
      eliminated = queue.dequeue();
      console.log(eliminated + " Get out!")
    }
  
    return queue.dequeue()
  }
  
  var nameList = ['小明', '小红', '小王', '小强']

  hotPotato(nameList,5);
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
'
运行

栈是一种高效的数据结构,因为数据只能在一端(栈顶)进行添加或删除,所以这样的操作很快。

栈是一种很特殊的列表。

先进后出,栈内元素只能通过列表的一端访问,这一端称为栈顶。

应用

栈可以进行:

(1)进制间的相互转换

(2)回文:将字符串的每个字符按从左至右的顺序压入栈。 当字符串中的字符都入栈后,原来字符串尾部就在栈顶,字符串第一个字符在栈顶, 栈内就保存了一个反转后的字符串。 通过持续弹出栈中的每个字母就可以得到一个新字符串, 该字符串刚好是原来的字符串的逆序。 我们只需要比较这两个字符串即可, 如果它们相等, 就是一个回文。

实现代码

**
 * 栈的构造函数
 */

 function Stack() {

    /**
     * 用数组来模拟栈
     * @type {Array}
     */
    var items = [];
  
    /**
     * 将元素送入栈,放置于数组的最后一位
     * @param  {Any} element 接受的元素,不限制类型
     */
    this.push = function(element) {
      items.push(element);
    };
  
    /**
     * 弹出栈顶元素
     * @return {Any} 返回被弹出的值
     */
    this.pop = function() {
      return items.pop();  //返回的是被弹出来的值
    };
  
    /**
     * 查看栈顶元素
     * @return {Any} 返回栈顶元素
     */
    this.peek = function() {
      return items[items.length - 1];  //栈是后进先出,后面进去的是栈顶,这是栈顶元素
    }
  
    /**
     * 确定栈是否为空(用于判断)
     * @return {Boolean} 若栈为空则返回true,不为空则返回false
     */
    this.isAmpty = function() {
      return items.length === 0
    };
  
    /**
     * 清空栈中所有内容
     */
    this.clear = function() {
      items = [];
    };
  
    /**
     * 返回栈的长度
     * @return {Number} 栈的长度
     */
    this.size = function() {
      return items.length;
    };
  
    /**
     * 以字符串显示栈中所有内容
     */
    this.print = function() {
      console.log(items.toString());
    };
  }
  
  /**
   * 将10进制数字转为2进制数字
   * 原理就是输入要转换的数字,不断的除以二并取整。并且最后运用while循环,将栈中所有数字拼接成字符串输出。
   * @param  {Number} decNumber 要转换的10进制数字
   * @return {Number}           转换后的2进制数字
   */
  function divideBy2(decNumber) {
  
    var remStack = new Stack(),   //声明一个新的栈
      rem, //表示数字除以2以后的余数
      binaryString = '';
  
    while (decNumber > 0) {
      rem = Math.floor(decNumber % 2);
      remStack.push(rem);  //将余数放入栈中
      decNumber = Math.floor(decNumber / 2);    //数字每取一次余数,就要除以2
    }
  //最后得到的栈是:第一个余数去到栈底,最后一个余数在栈顶
    //然后出栈,就能得到依次余数的逆序,就能得到求得的二进制数
    while (!remStack.isAmpty()) {
      binaryString += remStack.pop().toString();
    }
  
    return binaryString;
  };

  console.log(divideBy2(10));

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95

补充内容:

列表

列表是一组有序的数据,列表中的每个数据项称为元素。
在 JavaScript 中, 列表中的元素可以是任意数据类型。 列表中可以保存多少元素并没有事先限定,实际中受内存限制。

常用属性及方法

  • length:返回列表中元素的个数
  • append():在列表末尾添加新的元素
  • listToString(): 返回列表的字符串形式
  • getElement():返回当前位置的元素
  • find():查找给定的元素,如果找到就返回元素的对应下标(元素在列表中的位置),如果没有找到就返回-1.
  • remove():删除列表元素
  • contains():判断元素是否存在于列表中
  • clear():清空列表中所有元素
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/盐析白兔/article/detail/1001678
推荐阅读
相关标签
  

闽ICP备14008679号