队列数据结构

队列(queue) 数据结构是一种 受限 的数据结构，符合是 先进先出 的原则。后端(末端)是负责增加，前端(前面)负责删除。就如同我们去食堂买饭，后来的同学需要在对列最后排队等候，前面买上饭的同学就可以离开买饭的对列中了。

队列的优先级

优先级队列 就好比们生活中的一些事情，比如去做飞机，往往头等舱的乘客会比经济舱的乘客优先上飞机一样~。

队列的优先级封装

  1.   //  优先级队列封装
  2.   function PriorityQueue() {
  3.     //  在类内部在创建一个类，成为内部类
  4.     function QueueElement(element, priority) {
  5.       this.element = element; //  元素
  6.       this.priority = priority  //  优先级
  7.     }
  8.     this.items = [];
  9.     //  插入方法
  10.     PriorityQueue.prototype.enqueue = function (element, priority) {
  11.       //  创建一个内部类的实例
  12.       let queueElement = new QueueElement(element, priority)
  13.       //  更具条件排列队列的顺序
  14.       if (this.items.length === 0) {
  15.         //  如果队列是空直接放进去
  16.         this.items.push(queueElement)
  17.       } else {
  18.         let added = false
  19.         for (let i = 0; i < this.items.length; i++) {
  20.           // 如果不为空，判断优先级，顺序插入数据
  21.           if (queueElement.priority < this.items[i].priority) {
  22.             // 更近优先级的位置插入
  23.             this.items.splice(i, 0, queueElement)
  24.             added = true;
  25.             break
  26.           }
  27.         }
  28.         // 如果这个值优先级最小，放到最后面
  29.         if (!added) {
  30.           this.items.push(queueElement)
  31.         }
  32.       }
  33.     }
  34.   }
  35.   let priorityQueue = new PriorityQueue();
  36.   priorityQueue.enqueue('a', 1)
  37.   priorityQueue.enqueue('a', 151)
  38.   priorityQueue.enqueue('a', 11)
  39.   priorityQueue.enqueue('a', 10)
  40.   console.log(priorityQueue.items);

封装队列的方法

  1.   function Queue() {
  2.     this.items = [];
  3.     //  push 增加队列
  4.     Queue.prototype.enqueue = function (el) {
  5.       console.log(el);
  6.       return this.items.push(el)
  7.     }
  8.     //  delQueue 删除队列
  9.     Queue.prototype.delQueue = function () {
  10.       return this.items.shift()
  11.     }
  12.     //  front 查看队列的第一个元素
  13.     Queue.prototype.front = function () {
  14.       return this.items[0]
  15.     }
  16.     //  isEmpty 查看队列是否有值 返回Boolean
  17.     Queue.prototype.isEmpty = function () {
  18.       return this.items.length === 0;
  19.     }
  20.     //  size 返回队列长度
  21.     Queue.prototype.size = function () {
  22.       return this.items.length;
  23.     }
  25.     //  
  26.   }
  27.   let q = new Queue();
  28.   q.enqueue('abc')
  29.   q.enqueue('bcd')
  30.   q.enqueue('cde')
  31.   console.log(q)    //    需要注释掉下面内容才能看到，否则为之后一项
  32.   q.delQueue()
  33.   console.log(q)
  34.   q.delQueue()
  35.   console.log(q)
  36.   console.log(q.front());
  37.   console.log(q.isEmpty());
  38.   console.log(q.size())

双端队列数据结构

双端队列数据结构 是一种允许我们同时从前端和后端添加和移除元素的特殊队列。 由于双端队列同时遵守了先进先出和后进先出的原则，可以说他是把队列和栈结合的一种数据结构。举个例子：好比我们去电影院，一个刚买了票的人如果只是还需要在问一些问题，就可以直接回到队伍的头部。在队伍末尾的人如果赶时间，也可以直接离开队伍。

双端队列同时遵循 先进先出，后仅先出 的原则，可以说她是吧队列和栈相结合的一种数据结构。

  1.     class Deque {
  2.         constructor() {
  3.             this.count = 0;
  4.             this.locwestCount = 0;   //  记录队列前端第一位；
  5.             this.items = {};
  6.         }
  7.         //  队列前端添加一个元素
  8.         addFront(element) {
  9.             //  队列为空
  10.             if (this.isEmtry()) {
  11.                 this.addBack(element)
  12.             } else if (this.locwestCount > 0) {
  13.                 //  一个元素已经被双端队列的前端移除；
  14.                 this.locwestCount -= 1;
  15.                 this.items[this.locwestCount] = element;
  16.             } else {
  17.                 for (let i = this.count; i > 0; i--) {
  18.                     this.items[i] = this.items[i - 1];
  19.                 }
  20.                 this.count += 1;
  21.                 this.locwestCount = 0;
  22.                 this.items[0] = element;
  23.             }
  24.         }
  25.         //  队列后端添加一个元素
  26.         addBack(element) {
  27.             this.items[this.count] = element;
  28.             this.count += 1;
  29.         }
  30.         //  移除队列前端第一个元素
  31.         removeFront() {
  32.             if (this.isEmtry()) return undefined;
  33.             const result = this.items[this.locwestCount];
  34.             delete this.items[this.locwestCount]
  35.             this.locwestCount += 1;
  36.             return result;
  37.         }
  38.         //  移除队列后端一个元素
  39.         removeBack() {
  40.             if (this.isEmtry()) return undefined;
  41.             this.count -= 1;
  42.             const result = this.items[this.count];
  43.             delete this.items[this.count]
  44.             return result;
  45.         }
  46.         // 获取队列前端第一项
  47.         peekFront() {
  48.             if (this.isEmtry()) return undefined;
  49.             return this.items[this.locwestCount]
  50.         }
  51.         //  获取队列后端第一项
  52.         peekBack() {
  53.             if (this.isEmtry()) return undefined;
  54.             return this.items[this.items.length - 1]
  55.         }
  56.         isEmtry() {
  57.             return this.count - this.locwestCount === 0;
  58.         }
  60.         size() {
  61.             return this.count - this.locwestCount;
  62.         }
  64.         clear() {
  65.             this.count = 0;
  66.             this.locwestCount = 0;
  67.             this.items = {};
  68.         }
  70.         toString() {
  71.             if (this.isEmtry()) return '';
  72.             let objString = `${this.items[this.locwestCount]}`; //  先把第一项放进去
  73.             for (let i = this.locwestCount + 1; i < this.count; i++) {
  74.                 objString = `${objString},${this.items[i]}`;    //  每一项依次放进去
  75.             }
  76.             return objString;
  77.         }
  78.     }
  80.     const deque = new Deque();
  82.     console.log(deque.isEmtry(), '真为空');      //  true "真为空"
  83.     deque.addBack('a')
  84.     deque.addBack('b');
  85.     console.log(deque.items);       //  {0: "a", 1: "b"}
  86.     deque.addBack('c')
  87.     console.log(deque.size(), '长度');       //  3 "长度"
  88.     console.log(deque.isEmtry(), '假为不空');        //  false "假为不空"
  89.     console.log(deque.removeFront(), '移除掉的值');      //  a 移除掉的值
  90.     console.log(deque.items);       //  {1: "b", 2: "c"}
  91.     console.log(deque.removeBack(), '被删除的值');       //  c 被删除的值
  92.     console.log(deque.items);
  93.     deque.addBack('d')
  94.     console.log(deque.items);       //  {1: "b"}
  95.     console.log(deque.toString());      //  b,d

击鼓传花案例

游戏规则：十几人或几十人围成圆圈坐下，其中一人拿花，一人背着大家或蒙眼击鼓，击鼓n次，就传n次,到一轮之后，花在谁手中，谁就淘汰，最后只剩一人

  1.   //击鼓传花算法 基于上面的封装方法实现
  2.   function pasGame(nameList, num) {
  3.     //创建一个队列结构
  4.     let queue = new Queue();
  6.     //  将所有的人都加到队列中
  7.     for (let i = 0; i < nameList.length; i++) {
  8.       queue.enqueue(nameList[i])
  9.     }
  10.     // 开始每次数数，直到剩下一个人
  11.     while (queue.size() > 1) {
  12.       // 点睛之笔，可以得出循环的这个值 是不是num
  13.       for (let i = 0; i < num - 1; i++) {
  14.         //  这里其实是 栈的感觉，先执行完里面在执行外面。
  15.         //  如果不等于num 删掉他重新放到最后面。
  16.         queue.enqueue(queue.delQueue())
  17.       }
  18.       //  得到和num相等的值，直接删除
  19.       queue.delQueue()
  20.     }
  21.     //  获取剩下的那个人
  22.     alert('还剩' + queue.size() + '个人') //  剩下人数长度
  23.     let name = queue.front()  //得到剩下的那个人
  24.     alert('身下的人为' + name);
  25.     alert('剩下人的原来下标为' + nameList.indexOf(name))
  27.   }
  28.   pasGame(['a', 'b', 'c', 'd'], 3)

双端队列判断回文数

  1.     function palindromeChecker(palindrome) {
  2.         if (palindrome === undefined || palindrome === null || (palindrome !== null && palindrome.length === 0)) {
  3.             return false;
  4.         }
  6.         const deque = new Deque();
  7.         //  只能校样字符串。不过这是一种思路
  8.         const lowerString = palindrome.toLocaleLowerCase().split(' ').join('');
  10.         let isEqual = true;
  11.         let firstChar,lastChar;
  12.         for (let i = 0; i < lowerString.length; i++) {
  13.             deque.addBack(lowerString.charAt(i));
  14.         }
  16.         while(deque.size() > 1 && isEqual){
  17.             //  统一移除前端 后端各一项
  18.             firstChar = deque.removeFront();
  19.             lastChar = deque.removeBack();
  20.             // 如果移除的两项相不等说明不是回文数
  21.             if(firstChar !== lastChar){
  22.                 isEqual = false
  23.             }
  24.         }
  25.         return isEqual;
  26.     }
  28.     console.log(palindromeChecker('aa1qwedaa'));