查看: 187|回复: 0

[JavaScript/JQuery] 我对JS队列的学习

发表于 6 天前
我对JS队列的学习 什么是队列

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

在具体应用中通常用链表或者数组来实现。

队列的学习

队列的操作其实是和栈是差不多的,但是队列只允许新数据在后端进行添加。

1 创建队列

声明一个类

  1. function Queue() {
  2. //这里是属性和方法
  3. }
复制代码

需要一个用于存储队列中的元素的数据结构,这里选择数组。

  1. var items = [];
复制代码

2 队列的基本操作

添加元素到队列(只能添加到队列的末尾)

  1. this.enqueue = function (element) {
  2. items.push(element);
  3. }
复制代码

移除队列的第一项,并返回被移除的元素

  1. this.dequeue = function() {
  2. return items.shift();
  3. }
复制代码

获取队列最前面的元素

  1. this.front = function() {
  2. return items[0];
  3. }
复制代码

判断队列是否为空

  1. this.isEmpty = function() {
  2. return items.length == 0;
  3. }
复制代码

队列的长度

  1. this.size = function() {
  2. return items.length;
  3. }
复制代码

队列和栈的区别是dequeue()方法和front()方法,这是因为先进先出和后进先出的原则不同。

使用Queue类

1.初始化类,验证是否为空

  1. var queue = new Queue();
  2. console.log(queue.isEmpty()); //true;
复制代码

2.添加到队列,判断长度

  1. queue.enqueue("John");
  2. queue.enqueue("Jack");
  3. queeu.enqueue("Camila");
  4. console.log(queue.size()); //3
复制代码

3.移除两个元素,判断长度

  1. queue.dequeue();
  2. queue.dequeeu();
  3. console.log(queue.size()); //1;这时队列只剩下Camila
复制代码
优先队列

对,这就是特权!比如登机,头等舱商务舱能和经济舱的登机顺序一样??肯定他们的优先级高啊

实现一个优先队列,有两种选项:①设置优先级,然后在正确的位置添加元素。②用入列操作添加元素,然后按照优先级移除它们。

就是登机,你可以让优先级高的先进去候车室,然后登机的时候按顺序理所当然的头等舱的先登机。另一种就是头等舱经济舱什么的进去候车室的时候不按优先级,但是呢,等到登机的时候按照优先级喊人进去。

  1. function PriorityQueue() {
  2. var items = [];
  3. //创建一个元素包含了元素和优先级
  4. function QueueElement (element, priority) {
  5. this.element = element;
  6. thie.priority = priority;
  7. };
  8. this.queue = function(element, priority) {
  9. var queueElement = new QueueElement(element, priority);
  10. //队列为空,直接添加到队列(因为这时根本不用比较优先级啊)
  11. if(this.isEmpty()) {
  12. items.push(queueElement);
  13. } else {
  14. var added = false;
  15. //如果要添加的元素的优先级小于某一位置元素,那么就把要添加的元素放在这一位置元素的前面(这里用了splice方法)
  16. //优先级数字越小,优先级越高,应该越早处理,所以应该越靠近队列前面
  17. for(var i = 0; i < items.length; i++) {
  18. if(queueElement.priority < items[i].priority) {
  19. items.splice(i, 0, queueElement);
  20. added = true;
  21. //插入新元素之后,终止队列循环
  22. break;
  23. }
  24. }
  25. //到这一步就意味着所有的元素都比要添加的元素的优先级低,所以直接放到末尾就可以
  26. if(!added) {
  27. items.push(queueElement);
  28. }
  29. }
  30. };
  31. }
复制代码
  1. var priorityQueue = new PriorityQueue();
  2. priorityQueue.enqueue("John", 2);
  3. priorityQueue.enqueue("Jack", 1);
  4. priorityQueue.enqueue("Camila", 1);
复制代码

得到的队列就是 |Jack(1)|Camila(1)|John(2)|,优先级相同只需要放到同优先级的后面就可以。

这里是最小优先队列,优先值较小的元素被放置在队列最前面。

循环队列

击鼓传花,孩子们围成一个圆圈,把花尽快的传递给旁边的人,某一时刻传花停止,这个时候花在谁手里谁就淘汰。重复这个过程直到只剩下一个孩子。

  1. function hotPotato(nameList, num) {
  2. var queue = new Queue();
  3. //将所有的名字放入队列
  4. for(var i = 0; i < nameList.length; i++) {
  5. queue.enqueue(nameList[i]);
  6. }
  7. var eliminated = '';
  8. //一轮游戏淘汰一个人
  9. while(queue.size() > 1) {
  10. //一轮游戏传鼓7次
  11. for(var i = 0; i < num; i++) {
  12. //传鼓一次,你把花传给别人,你就安全了(队首的人拿花)
  13. //从队列开头移除一项放到队尾
  14. queue.enqueue(queue.dequeue());
  15. }
  16. //一轮游戏结束,淘汰手里拿花的那个人,即队首的那个
  17. eliminated = queue.dequeue();
  18. console.log(eliminated + "被淘汰");
  19. }
  20. //得到最后的队首
  21. return queue.dequeue();
  22. }
  23. var names = ["John", "Jack", "Camila", "Ingrid", 'Carl'];
  24. var winner = hotPotato(names, 7);
  25. console.log('胜利者' + winner);
复制代码

结果:
Camila Jack Carl Ingrid依次被淘汰
胜利者:John

下一篇链表。。。。



回复

使用道具 举报