数据结构-队列

1/9/2021 JavaScriptAlgorithm

# 文章目录

# 一、什么是队列?

我们已经学习了一种受限的线性结构:栈结构
并且已经知道这种受限的数据结构对于解决某些特定问题,会有特别的效果。

下面,我们再来学习另外一个受限的数据结构:队列

队列( Queue),它是一种受限的线性表先进先出( FIFO First In First Out)

  • 受限之处在于它只允许在表的前端( front)进行删除操作
  • 而在表的后端(rear)进行插入操作

在这里插入图片描述

# 二、队列的应用

在这里插入图片描述

# 三、队列的实现(基于数组)

我们先来搭建基本框架,再搭建具体的 API

<script>
  // 封装队列类 function Queue()
  {
    // 属性
    (this.items = [])

    // 方法
  }
  // 使用队列 let s = new Queue()
</script>
1
2
3
4
5
6
7
8
9
10

# 3.1 队列的常见操作

  • enqueue 进入队列(enterQueue)
  • dequeue 移除(deleteQueue)
    在这里插入图片描述

# 3.2 一个基本的队列模型

<script>
  // 封装队列类
  function Queue(){
    // 属性
    this.items = []

    // 方法
    // 1.将元素加入到队列中
    Queue.prototype.enqueue = function (element){
      this.items.push(element)
    }

    // 2.删除前端的元素
    Queue.prototype.dequeue = function (){
      return this.items.shift()
    }

    // 3.返回前端的元素
    Queue.prototype.front = function (){
      return  this.items[0]
    }

    // 4.查看队列是否为空
    Queue.prototype.isEmpty = function (){
      return this.items.length == 0
    }

    // 5.查看队列中元素的个数
    Queue.prototype.size = function (){
      return this.items.length
    }

    // 6. toString方法
    Queue.prototype.toString = function (){
      return this.items.toString()
    }
  }

  // 使用队列
  let queue = new Queue()

  // 1.将元素加入到队列
  queue.enqueue('a')
  queue.enqueue('b')
  queue.enqueue('c')
  console.log(queue);

  // 2.删除元素
  queue.dequeue()
  console.log(queue);

  // 3.返回前端元素
  console.log(queue.front());

  // 4.查看队列是否为空
  console.log(queue.isEmpty());

  // 5.查看队列中的元素个数
  console.log(queue.size());

  // 6.toString 方法
  console.log(queue.toString());
</script>
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

# 四、面试题 击鼓传花

击鼓传花是一个常见的面试算法题。使用队列可以非常方便的实现最终的结果。

原游戏规则:

  • 班级中玩一个游戏,所有学生围成一圈,从某位同学手里开始向旁边的同学传一束花
  • 这个时候某个人(比如班长),在击鼓,鼓声停下的一颗花落在谁手里,谁就出来表演节目

我们来修改一下这个游戏规则

  • 几个朋友一起玩一个游戏,围成一圏,开始数数,数到某个数字的人自动淘汰
  • 最后剩下的这个人会获得胜利,请词最后剩下人的是原来在哪一个位置上的人

示意图(假设数到 5 淘汰):
在这里插入图片描述

封装个基于队列的函数

  • 参数:所有参与人的姓名,基于的数字
  • 结果:最终剩下的一人的姓名

# 4.1 实现代码

<script>
  // 封装队列类
  function Queue() {
    // 属性
    this.items = []

    // 方法
    // 1.将元素加入到队列中
    Queue.prototype.enqueue = function (element) {
      this.items.push(element)
    }

    // 2.删除前端的元素
    Queue.prototype.dequeue = function () {
      return this.items.shift()
    }

    // 3.返回前端的元素
    Queue.prototype.front = function () {
      return this.items[0]
    }

    // 4.查看队列是否为空
    Queue.prototype.isEmpty = function () {
      return this.items.length == 0
    }

    // 5.查看队列中元素的个数
    Queue.prototype.size = function () {
      return this.items.length
    }

    // 6. toString方法
    Queue.prototype.toString = function () {
      return this.items.toString()
    }
  }

  // 面试题:击鼓传花
  function passGame(nameList, num) {
    // 1.创建一个队列结构
    let queue = new Queue()

    // 2.将所有人依次加入到队列中
    nameList.forEach(el => {
      queue.enqueue(el)
    });

    // 3.开始数数字
    while (queue.size() > 1) {
      // 不是num,重新加入到队列的末尾
      // 是num,将其从队列删除
      // 3.1 num数字之前的人重新加入到队列的末尾
      for (let i = 0; i < num - 1; i++) {
        // 把删除的元素加入到末尾
        queue.enqueue(queue.dequeue())
      }
      // 3.2 num对应的这个人,直接删除掉
      queue.dequeue()
    }

    // 4.获取剩下的人
    console.log('最终剩下的人数:',queue.size());
    let endName = queue.front()
    console.log("最终剩下的人:",endName);
    return nameList.indexOf(endName)
  }

  console.log('胜出人的下标:',passGame(['张三','李四','王五','马六','赵七','小明'],5));
</script>
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

结果:
在这里插入图片描述

# 五、优先级队列

在这里插入图片描述

# 5.1 优先级队列的封装

  1.        封装元素和优先级放在一起(可以封装一个新的构造函数)
    
  2.        添加元素时,将新插入元素的优先级和队列中已经存在的元素优先级进行比较,以获得自己正确的位置。
    
// 封装优先级队列 Priority(优先级)
function PriorityQueue() {
  // 在一个类里边封装另外一个类
  function QueueElement(element, priority) {
    this.element = element;
    this.priority = priority;
  }
  // 封装属性
  this.items = [];

  // 1.实现插入方法
  PriorityQueue.prototype.enqueue = function(element, priority) {
    // 1.创建QueueElement对象
    let queueElement = new QueueElement(element, priority);

    // 2.判断队列是否为空
    if (this.items.length == 0) {
      this.items.push(queueElement);
    } else {
      // added 用于控制所有都比他小的
      let added = false;
      for (let i = 0; i < this.items.length; i++) {
        if (queueElement.priority < this.items[i].priority) {
          this.items.splice(i, 0, queueElement);
          added = true;
          // 插入后终止循环
          break;
        }
      }
      if (!added) {
        // 没有比他大的 插入到最后
        this.items.push(queueElement);
      }
    }
  };

  // 2.删除前端的元素
  PriorityQueue.prototype.dePriorityQueue = function() {
    return this.items.shift();
  };

  // 3.返回前端的元素
  PriorityQueue.prototype.front = function() {
    return this.items[0];
  };

  // 4.查看队列是否为空
  PriorityQueue.prototype.isEmpty = function() {
    return this.items.length == 0;
  };

  // 5.查看队列中元素的个数
  PriorityQueue.prototype.size = function() {
    return this.items.length;
  };

  // 6. toString方法
  PriorityQueue.prototype.toString = function() {
    // return '6'
    let resultString = "";
    for (var i = 0; i < this.items.length; i++) {
      resultString +=
        this.items[i].element + "-" + this.items[i].priority + " ";
    }
    return resultString;
  };
}

// 测试代码
let pq = new PriorityQueue();
pq.enqueue("nnn", 1000);
pq.enqueue("abc", 1);
pq.enqueue("cba", 100);
pq.enqueue("nba", 10);
console.log(pq);
alert(pq);
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

效果:
在这里插入图片描述

最后更新于: 2021年9月15日星期三晚上10点10分
Faster Than Light
Andreas Waldetoft / Mia Stegmar