数据结构之队列结构

基本定义

队列结构是一种受限的数据结构，它是一种线性表，符合先进先出的特点(FIFO—-> First In First Out)。受限之处是因为他只允许在前端进行删除操作，在后端进行插入操作。比如说我们日常生活中的排队，有限排队的人优先处理。

在JavaScript中实现队列结构

实现队列结构可以通过数组实现，也可以基于链表实现，采用数组实现效率不高，因为我们删除了第一个元素，会导致后面的所有元素都要往前面移一位，但是还没有学习到链表，于是我们就采取熟悉的数组实现。

队列的常见操作

  1. enqueue：向队列尾部添加一个或多个项
  2. dequeue：移除队列第一个项，也是需要删除的哪一项，并且返回被删除的元素
  3. front：返回队列的第一个元素，队列不做任何操作，单纯的看一眼会被移除的元素
  4. isEmpty：如果队列为空则返回true，反之返回false
  5. size：返回队列中的元素个数
  6. toString：将队列的元素转换为字符串

利用数组实现队列结构

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
class Queue {
  constructor() {
    this.items = [];
  }
  enqueue(item) {
    this.items.push(item);
  }
  dequeue() {
    return this.items.shift();
  }
  front() {
    return this.items[0];
  }
  isEmpty() {
    return this.items.length > 0 ? false : true;
  }
  size() {
    return this.items.length;
  }
  toString() {
    let str = "";
    this.items.forEach(item => {
      str = str + item + " ";
    });
    return str;
  }
}

const queue = new Queue();

击鼓传花案例

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
class Queue {
  constructor() {
    this.items = [];
  }
  enqueue(item) {
    this.items.push(item);
  }
  dequeue() {
    return this.items.shift();
  }
  front() {
    return this.items[0];
  }
  isEmpty() {
    return this.items.length > 0 ? false : true;
  }
  size() {
    return this.items.length;
  }
  toString() {
    let str = "";
    this.items.forEach(item => {
      str = str + item + " ";
    });
    return str;
  }
}

//封装函数
function cuurent(playerList, number) {
  const queue = new Queue();
  playerList.forEach(item => {
    queue.enqueue(item);
  });
  while (!(queue.size() === 1)) {
    for (let i = 0; i < number - 1; i++) {
      queue.enqueue(queue.dequeue());
    }
    queue.dequeue();
  }
  return queue.front();
}

//定义需要传入的数组
const playerList = [
  "amy",
  "doinb",
  "coderwei",
  "zys",
  "jacker",
  "join",
  "rokkie",
  "bin",
  "faker",
  "the shy",
];

console.log(cuurent(playerList, 5)); //coderwei