JavaScript 算法

【数据结构与算法】队列（JavaScript版详解）

By yesmore on 2021-08-12
阅读时间 25 分钟
文章共 5.8k 字
阅读量 次

要点：基本队列、优先队列、双端队列、循环队列、对应练习

先知：队列（Queue）是一种运算受限的线性表，特点：先进先出。(FIFO：First In First Out)

一、认识队列

1.1 定义

队列（Queue）是一种运算受限的线性表，特点：先进先出。(FIFO：First In First Out)

受限之处：

  • 只允许在表的前端（front）进行删除操作。
  • 只允许在表的后端（rear）进行插入操作。

生活中类似队列结构的场景：

  • 排队，比如在电影院，商场，甚至是厕所排队。
  • 优先排队的人，优先处理。 (买票、结账、WC)。

image

1.2 队列图解

image

1.3 队列在程序中的应用

打印队列：计算机打印多个文件的时候，需要排队打印。

线程队列：当开启多线程时，当新开启的线程所需的资源不足时就先放入线程队列，等待 CPU 处理。

我们在做性能优化的时候，很多时候会提到的一点就是“HTTP 1.1 的队头阻塞问题”，具体来说就是 HTTP2 解决了 HTTP1.1 中的队头阻塞问题，但是为什么 HTTP1.1 有队头阻塞问题，HTTP2 究竟怎么解决的这个问题，很多人都不清楚。

其实队头阻塞是一个专有名词，不仅仅在 HTTP 有，交换器等其他地方也都涉及到了这个问题。实际上引起这个问题的根本原因是使用了队列这种数据结构。

协议规定， 对于同一个 tcp 连接，所有的 http1.0 请求放入队列中，只有前一个请求的响应收到了，才能发送下一个请求，这个时候就发生了阻塞，并且这个阻塞主要发生在客户端。

这就好像我们在等红绿灯，即使旁边绿灯亮了，你的这个车道是红灯，你还是不能走，还是要等着。

HTTP/1.0 和 HTTP/1.1

在HTTP/1.0 中每一次请求都需要建立一个 TCP 连接，请求结束后立即断开连接。

在HTTP/1.1 中，每一个连接都默认是长连接 (persistent connection)。对于同一个 tcp 连接，允许一次发送多个 http1.1 请求，也就是说，不必等前一个响应收到，就可以发送下一个请求。这样就解决了 http1.0 的客户端的队头阻塞，而这也就是HTTP/1.1中管道 (Pipeline)的概念了。

但是，http1.1 规定，服务器端的响应的发送要根据请求被接收的顺序排队，也就是说，先接收到的请求的响应也要先发送。这样造成的问题是，如果最先收到的请求的处理时间长的话，响应生成也慢，就会阻塞已经生成了的响应的发送，这也会造成队头阻塞。可见，http1.1 的队首阻塞是发生在服务器端。

HTTP/2 和 HTTP/1.1

为了解决HTTP/1.1中的服务端队首阻塞，HTTP/2采用了二进制分帧 和 多路复用 等方法。

帧是HTTP/2数据通信的最小单位。在 HTTP/1.1 中数据包是文本格式，而 HTTP/2 的数据包是二进制格式的，也就是二进制帧。

采用帧的传输方式可以将请求和响应的数据分割得更小，且二进制协议可以被高效解析。HTTP/2中，同域名下所有通信都在单个连接上完成，该连接可以承载任意数量的双向数据流。每个数据流都以消息的形式发送，而消息又由一个或多个帧组成。多个帧之间可以乱序发送，根据帧首部的流标识可以重新组装。

多路复用用以替代原来的序列和拥塞机制。在HTTP/1.1中，并发多个请求需要多个 TCP 链接，且单个域名有 6-8 个 TCP 链接请求限制（这个限制是浏览器限制的，不同的浏览器也不一定一样）。在HTTP/2中，同一域名下的所有通信在单个链接完成，仅占用一个 TCP 链接，且在这一个链接上可以并行请求和响应，互不干扰。

此网站 可以直观感受 HTTP/1.1 和 HTTP/2 的性能对比。

二、队列的实现

队列的实现和栈一样，有两种方案：

  • 基于数组实现。
  • 基于链表实现。

2.1 队列常见的操作

enqueue(element) 向队列尾部添加一个（或多个）新的项。

dequeue() 移除队列的第一（即排在队列最前面的）项，并返回被移除的元素。

front() 返回队列中的第一个元素——最先被添加，也将是最先被移除的元素。队列不做任何变动（不移除元素，只返回元素信息与 Map 类的 peek 方法非常类似）。

isEmpty() 如果队列中不包含任何元素，返回 true，否则返回 false。

size() 返回队列包含的元素个数，与数组的 length 属性类似。

toString() 将队列中的内容，转成字符串形式。

2.2 代码实现

顺序队列

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
class Queue {
  constructor() {
    this.items = [];
  }

  // enqueue(item) 入队，将元素加入到队列中
  enqueue(item) {
    this.items.push(item);
  }

  // dequeue() 出队，从队列中删除队头元素，返回删除的那个元素
  dequeue() {
    return this.items.shift();
  }

  // front() 查看队列的队头元素
  front() {
    return this.items[0];
  }

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

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

  // toString() 将队列中的元素以字符串形式返回
  toString() {
    let result = "";
    for (let item of this.items) {
      result += item + " ";
    }
    return result;
  }
}

链式队列

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
function LinkedQueue() {
    let Node = function (ele) {
        this.ele = ele;
        this.next = null;
    }

    let length = 0,
        front, //队首指针
        rear; //队尾指针
    this.push = function (ele) {
        let node = new Node(ele),
            temp;

        if (length == 0) {
            front = node;
        } else {
            temp = rear;
            temp.next = node;
        }
        rear = node;
        length++;
        return true;
    }

    this.pop = function () {
        let temp = front;
        front = front.next
        length--;
        temp.next = null
        return temp;
    }

    this.size = function () {
        return length;
    }
    this.getFront = function () {
        return front;
        // 有没有什么思路只获取队列的头结点,而不是获取整个队列
    }
    this.getRear = function () {
        return rear;
    }
    this.toString = function () {
        let string = '',
            temp = front;
        while (temp) {
            string += temp.ele + ' ';
            temp = temp.next;
        }
        return string;
    }
    this.clear = function () {
        front = null;
        rear = null;
        length = 0;
        return true;
    }
}

let myQueue = new LinkedQueue();

myQueue.push(1)
myQueue.push(2)
myQueue.push(3)
myQueue.push(4)
console.log(myQueue.toString()) // 1 2 3 4 
console.log(myQueue.pop()) // Node { ele: 1, next: null }
console.log(myQueue.toString()) // 2 3 4

2.3 测试代码

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
const queue = new Queue();

// enqueue() 测试
queue.enqueue("a");
queue.enqueue("b");
queue.enqueue("c");
queue.enqueue("d");
console.log(queue.items); //--> ["a", "b", "c", "d"]

// dequeue() 测试
queue.dequeue();
queue.dequeue();
console.log(queue.items); //--> ["c", "d"]

// front() 测试
console.log(queue.front()); //--> c

// isEmpty() 测试
console.log(queue.isEmpty()); //--> false

// size() 测试
console.log(queue.size()); //--> 2

// toString() 测试
console.log(queue.toString()); //--> c d

三、优先队列

3.1 定义

生活中类似优先队列的场景：

  • 优先排队的人，优先处理。 (买票、结账、WC)。
  • 排队中，有紧急情况（特殊情况）的人可优先处理。

所谓优先队列，顾名思义，就是说插入到队列中的元素可以根据优先级设置先后顺序。优先级越高位置越靠前，优先级越低位置越靠后。假设优先级用数字来表示，如果数字越小表示的优先级越高，形成的队列就称之为最小优先队列，反之则称之为最大优先队列。

3.2 代码实现

优先级队列主要考虑的问题：

  • 每个元素不再只是一个数据，还包含优先级。
  • 在添加元素过程中，根据优先级放入到正确位置。
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
// 优先队列内部的元素类
class QueueElement {
  constructor(element, priority) {
    this.element = element;
    this.priority = priority;
  }
}

// 优先队列类（继承 Queue 类）
export class PriorityQueue extends Queue {
  constructor() {
    super();
  }

  // enqueue(element, priority) 入队，将元素按优先级加入到队列中
  // 重写 enqueue()
  enqueue(element, priority) {
    // 根据传入的元素，创建 QueueElement 对象
    const queueElement = new QueueElement(element, priority);

    // 判断队列是否为空
    if (this.isEmpty()) {
      // 如果为空，不用判断优先级，直接添加
      this.items.push(queueElement);
    } else {
      // 定义一个变量记录是否成功添加了新元素
      let added = false;

      for (let i = 0; i < this.items.length; i++) {
        // 让新插入的元素进行优先级比较，priority 值越小，优先级越大
        if (queueElement.priority < this.items[i].priority) {
          // 在指定的位置插入元素
          this.items.splice(i, 0, queueElement);
          added = true;
          break;
        }
      }

      // 如果遍历完所有元素，优先级都大于新插入的元素，就将新插入的元素插入到最后
      if (!added) {
        this.items.push(queueElement);
      }
    }
  }

  // dequeue() 出队，从队列中删除前端元素，返回删除的元素
  // 继承 Queue 类的 dequeue()
  dequeue() {
    return super.dequeue();
  }

  // front() 查看队列的前端元素
  // 继承 Queue 类的 front()
  front() {
    return super.front();
  }

  // isEmpty() 查看队列是否为空
  // 继承 Queue 类的 isEmpty()
  isEmpty() {
    return super.isEmpty();
  }

  // size() 查看队列中元素的个数
  // 继承 Queue 类的 size()
  size() {
    return super.size();
  }

  // toString() 将队列中元素以字符串形式返回
  // 重写 toString()
  toString() {
    let result = "";
    for (let item of this.items) {
      result += item.element + "-" + item.priority + " ";
    }
    return result;
  }
}

可以看到，唯一有区别的只有enqueue方法。我们规定所有添加到优先队列的元素都必须满足{element, priority}这种JSON格式，以保证队列中的每一个元素都有一个priority属性来表示优先级。如果要添加的元素的优先级和队列中已有元素的优先级相同，仍然遵循队列的先进先出原则。如果队列中所有元素的优先级比要添加的元素的优先级都高，则将元素添加到队列的末尾。

3.3 测试代码

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
const priorityQueue = new PriorityQueue();

// 入队 enqueue() 测试
priorityQueue.enqueue("A", 10);
priorityQueue.enqueue("B", 15);
priorityQueue.enqueue("C", 11);
priorityQueue.enqueue("D", 20);
priorityQueue.enqueue("E", 18);
console.log(priorityQueue.items);
//--> output:
// QueueElement {element: "A", priority: 10}
// QueueElement {element: "C", priority: 11}
// QueueElement {element: "B", priority: 15}
// QueueElement {element: "E", priority: 18}
// QueueElement {element: "D", priority: 20}

// 出队 dequeue() 测试
priorityQueue.dequeue();
priorityQueue.dequeue();
console.log(priorityQueue.items);
//--> output:
// QueueElement {element: "B", priority: 15}
// QueueElement {element: "E", priority: 18}
// QueueElement {element: "D", priority: 20}

// isEmpty() 测试
console.log(priorityQueue.isEmpty()); //--> false

// size() 测试
console.log(priorityQueue.size()); //--> 3

// toString() 测试
console.log(priorityQueue.toString()); //--> B-15 E-18 D-20

四、双端队列

4.1 定义

允许从前端(front)和后端(rear)添加元素, 遵循的原则先进先出或后进先出.

双端队列可以理解为就是栈(后进先出)和队列(先进先出)的一种结合体. 既然是结合那么相应的操作也支持队列，栈的操作。

4.2 代码实现

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
  constructor() {
    this.items = {}
    this.count = 0
    this.lowestCount = 0
  }

  addFront(ele) {
    if (this.isEmpty()) {
      this.items[this.count] = ele
    } else if (this.lowestCount > 0) {
      this.lowestCount -= 1
      this.items[this.lowestCount] = ele
    } else {
      for (let i = this.count; i > 0; i--) {
        this.items[i] = this.items[i - 1]
      }
      this.items[0] = ele
    }
      this.count++
      return ele
    }

  removeFront() {
    if (this.isEmpty()) {
      return
    }
    const delEle = this.items[this.lowestCount]
    delete this.items[this.lowestCount]
    this.lowestCount++
    return delEle
  }

  addBack(ele) {
    this.items[this.count] = ele
    this.count++
  }

  removeBack() {
    if (this.isEmpty()) {
      return
    }

    const delEle = this.items[this.count - 1]
    delete this.items[this.count - 1]
    this.count--
    return delEle
  }

  peekFront() {
    if (this.isEmpty()) {
      return
    }
    return this.items[this.lowestCount]
  }

  peekBack() {
    if (this.isEmpty()) {
      return
    }
    return this.items[this.count - 1]
  }

  size() {
    return this.count - this.lowestCount
  }

  isEmpty() {
    return this.size() === 0
  }

  clear() {
    this.items = {}
    this.count = 0
    this.lowestCount = 0
  }

  toString() {
    if (this.isEmpty()) {
      return ''
    }
    let objString = `${this.items[this.lowestCount]}`
    for (let i = this.lowestCount + 1; i < this.count; i++){
      objString = `${objString}, ${this.items[i]}`
    }
    return objString
  }

}

五、循环队列

5.1 定义

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。 你的实现应该支持如下操作：

  • MyCircularQueue(k): 构造器，设置队列长度为 k 。
  • Front: 从队首获取元素。如果队列为空，返回 -1 。
  • Rear: 获取队尾元素。如果队列为空，返回 -1 。
  • enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
  • deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
  • isEmpty(): 检查循环队列是否为空。
  • isFull(): 检查循环队列是否已满。

想要实现上面的功能，其实主要就是判断循环队列是否为空isEmpty，是否已满isFull，这里我们使用两个指针来表示队首（head）和队尾的指针（tail）。假设初始化的时候两个指针的值都是-1。那么显然是否为空的判断条件就是两个指针都是-1的时候。

5.2 代码实现

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
/**
 * Initialize your data structure here. Set the size of the queue to be k.
 * @param {number} k
 */
var MyCircularQueue = function(k) {
    this.size = k
    this.head = -1
    this.tail = -1
    this.data = []
};
 
/**
 * Insert an element into the circular queue. Return true if the operation is successful. 
 * @param {number} value
 * @return {boolean}
 */
MyCircularQueue.prototype.enQueue = function(value) {
    if (this.isFull()) {
        return false
    }
    if (this.isEmpty()) {
        this.head = 0
    }
    this.tail = (this.tail + 1)%this.size
    this.data[this.tail] = value
    return true
};
 
/**
 * Delete an element from the circular queue. Return true if the operation is successful.
 * @return {boolean}
 */
MyCircularQueue.prototype.deQueue = function() {
    if (!this.isEmpty()) {
        if (this.tail === this.head) {
            this.tail = -1
            this.head = -1
        } else {
            this.head = (this.head + 1)%this.size
        }
        return true
    }
    return false
};
 
/**
 * Get the front item from the queue.
 * @return {number}
 */
MyCircularQueue.prototype.Front = function() {
    return this.head === -1? -1 : this.data[this.head]
};
 
/**
 * Get the last item from the queue.
 * @return {number}
 */
MyCircularQueue.prototype.Rear = function() {
    return this.tail === -1 ? -1 : this.data[this.tail]
};
 
/**
 * Checks whether the circular queue is empty or not.
 * @return {boolean}
 */
MyCircularQueue.prototype.isEmpty = function() {
    return this.tail === -1 && this.head === -1
};
 
/**
 * Checks whether the circular queue is full or not.
 * 当队列满的时候，则为指针的下一个地址应该等于头指针的位置：
 * @return {boolean}
 */
MyCircularQueue.prototype.isFull = function() {
    return (this.tail + 1)%this.size === this.head
};
 
MyCircularQueue.createNew = function(k) {
    return new MyCircularQueue(k)
};
 
/** 
 * Your MyCircularQueue object will be instantiated and called as such:
 * var obj = Object.create(MyCircularQueue).createNew(k)
 * var param_1 = obj.enQueue(value)
 * var param_2 = obj.deQueue()
 * var param_3 = obj.Front()
 * var param_4 = obj.Rear()
 * var param_5 = obj.isEmpty()
 * var param_6 = obj.isFull()
 */

六、队列的应用

6.1 击鼓传花-循环队列

使用队列实现小游戏：击鼓传花。

分析：现实例子就是击鼓传花(Hot Potato)，在游戏中，孩子们围着圆圈，把花尽快地传递给旁边的人。某一时刻传花停止，这个时候花在谁手里，谁就退出圆圈结束游戏。重复这个过程，直到只剩一个孩子(胜利)。

传入一组数据集合和设定的数字 number，循环遍历数组内元素，遍历到的元素为指定数字 number 时将该元素删除，直至数组剩下一个元素。

代码实现

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
// 利用队列结构的特点实现击鼓传花游戏求解方法的封装
function passGame(nameList, number) {
  // 1、new 一个 Queue 对象
  const queue = new Queue();

  // 2、将 nameList 里面的每一个元素入队
  for (const name of nameList) {
    queue.enqueue(name);
  }

  // 3、开始数数
  // 队列中只剩下 1 个元素时就停止数数
  while (queue.size() > 1) {
    // 不是 number 时，重新加入到队尾
    // 是 number 时，将其删除

    for (let i = 0; i < number - 1; i++) {
      // number 数字之前的人重新放入到队尾（即把队头删除的元素，重新加入到队列中）
      queue.enqueue(queue.dequeue());
    }

    // number 对应这个人，直接从队列中删除
    // 由于队列没有像数组一样的下标值不能直接取到某一元素，
    // 所以采用，把 number 前面的 number - 1 个元素先删除后添加到队列末尾，
    // 这样第 number 个元素就排到了队列的最前面，可以直接使用 dequeue 方法进行删除
    queue.dequeue();
  }

  // 4、获取最后剩下的那个人
  const endName = queue.front();

  // 5、返回这个人在原数组中对应的索引
  return nameList.indexOf(endName);
}

测试代码

1
2
3
4
// passGame() 测试
const names = ["lily", "lucy", "tom", "tony", "jack"];
const targetIndex = passGame(names, 4);
console.log("击鼓传花", names[targetIndex]); //--> lily

6.2 基数排序

使用队列实现基数排序

队列不仅用于执行现实生活中关于队列相关的操作，还可以用于对数据进行排序。计算机刚刚出现的时候，程序是通过穿孔输入主机的，每一张卡包含一条程序语句。这些穿孔卡装在一个盒子里面，经过一个机械装置进行排序。我们可以用一组队列来模拟这个过程。这种排序技术叫做基数排序。

对于0~99的数字，基数排序将数据集扫描两次。第一次按照个位上的数字进行排序，第二次按照十位上的数字进行排序。每个数组根据对应位上的数字被分配在不同的盒子里。

举例如下：假如有数字 91，46，85，15，92，35，31，22

经过基数排序第一次扫描之后按照个位数的大小排序，数字被分配大如下的盒子中：

第0个盒子：
第1个盒子：91，31
第2个盒子：92，22
第3个盒子：
第4个盒子：
第5个盒子：85，15，35
第6个盒子：46
第7个盒子：
第8个盒子：
第9个盒子：

根据盒子的顺序，对数字经行第一次排序的结果如下：

91，31，92，22，85，15，35，46

然后根据十位上的数值再将上次排序结果分配到不同的盒子里

第0个盒子：
第1个盒子：15
第2个盒子：22
第3个盒子：31,35
第4个盒子：46
第5个盒子：
第6个盒子：
第7个盒子：
第8个盒子：85
第9个盒子：92,92

最后将盒子里的数字取出，组成一个新的列表，该列表即为排好顺序的数字：

15，22，31，35，46，85，91，92

使用队列代表盒子，可以实现这个算法，我们需要9个队列，每个对应一个数字。将所有队列保存在一个数组中，使用取余和出发操作决定各位和十位。算法的剩余部分将数字加入对应的队列，根据个位数值重新排序，然后再根据十位数值经行排序，结果即为排好顺序的数字。

代码实现

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
97
98
99
100
101
102
/*--------------Queue类的定义和测试代码----------------*/
function Queue(){
        this.dataStore = [];
        this.enqueue = enqueue;
        this.dequeue = dequeue;
        this.front = front;
        this.back = back;
        this.toString = toString;
        this.empty = empty;
}

//入队，就是在数组的末尾添加一个元素
function enqueue(element){
    this.dataStore.push(element);
}
//出队，就是删除数组的第一个元素
function dequeue(){
    return this.dataStore.shift();
}
//取出数组的第一个元素
function front(){
    return this.dataStore[0];
}
//取出数组的最后一个元素
function back(){
    return this.dataStore[this.dataStore.length-1];
}

function toString(){
    var retStr = "";
    for (var i=0; i<this.dataStore.length; ++i) {
        retStr += this.dataStore[i] + " "
    }
    return retStr;
}
//判断数组是否为空
function empty(){
    if(this.dataStore.length == 0){
        return true;
    }else{
        return false;
    }    
}
//返回数组中元素的个数
function count(){
    return this.dataStore.length;
}

/*----------------基数排序-----------------*/

function distribute(nums,queues,n,digit){
    for (var i=0; i<n; ++i) {
        if(digit == 1){
            //各位数字入队
            queues[nums[i]%10].enqueue(nums[i]);
        }else{
            //十位数字入队
            queues[Math.floor(nums[i] / 10)].enqueue(nums[i]);
        }
    }    
}

//收集队列中的数字放在数字nums中
function collect(queues,nums){
    var i=0;
    for (var digit=0; digit<10; ++digit) {
        while (!queues[digit].empty()){
            nums[i++] = queues[digit].dequeue();
        }
    }
}

function dispArray(arr){
    for (var i=0; i<arr.length; ++i) {
        document.write(arr[i] + " ");
    }
}

//初始化9个队列
var queues = [];
for (var i = 0; i < 10; i++) {
    queues[i] = new Queue();
}
//初始化10个二位整数
var nums = [];
for (var i=0; i<10; ++i) {
    nums[i] = Math.floor(Math.random()*100);
}

document.write('排序之前');document.write('<br>');
dispArray(nums);
document.write('<br>');
//按照个位数字入相应的队列
distribute(nums, queues, 10, 1);
//收集队列中的数字放在数组nums中
collect(queues, nums);
//按照十位数字如相应的队列
distribute(nums, queues, 10, 10);
//手机队列中的数字放在nums中
collect(queues, nums);
document.write("排序之后");document.write('<br>');
dispArray(nums);

6.3 银行排队

实现思路：第一个客户到达的时刻为0，之后每个客户到达的时刻在前一个客户到达时设定随机值，因此在客户到达时需要产生两个随机数，一个是客户办理业务耗时durtime，一个是下一客户到达时间间隔intertime，假设当前时间为occurtime，则下一客户到达时为occurtime+intertime。

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

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

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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

6.4 判断回文

上一篇栈（使用栈判断回文）中也有涉及回文的实现, 下面我们通过双端队列来实现同样的功能

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
function palindromeChecker(aString) {
  if (!aString || typeof aString !== 'string' || !aString.trim().length) {
    return false
  }
  const deque = new Deque()
  const lowerString = aString.toLowerCase().split(' ').join('')

  // 加入队列

  for (let i = 0; i < lowerString.length; i++) {
    deque.addBack(lowerString[i])
  }

  let isEqual = true
  let firstChar = ''
  let lastChar = ''

  while (deque.size() > 1 && isEqual) {
    firstChar = deque.removeFront()
    lastChar = deque.removeBack()
    if (firstChar != lastChar) {
      isEqual = false
    }
  }

  return isEqual

}

图解

1

6.5 生成 1 到 n 的二进制数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function generatePrintBinary(n) {
  var q = new Queue()
  q.enqueue('1')
  while (n-- > 0) {
    var s1 = q.peek()
    q.dequeue()
    console.log(s1)
    var s2 = s1
    q.enqueue(s1 + '0')
    q.enqueue(s2 + '1')
  }
}
 
generatePrintBinary(5) // => 1 10 11 100 101

回顾

数组、栈和队列图解

Tips: Please indicate the source and original author when reprinting or quoting this article.

特色标签
JavaScript 算法
链友
ESC