Skip to content

Latest commit

 

History

History
386 lines (305 loc) · 10.4 KB

队列.md

File metadata and controls

386 lines (305 loc) · 10.4 KB
Raw

队列

  • 队列是在表的一端插入，在另一端删除
  • 队列中，允许插入到一端叫做队尾，允许删除的一端叫做对头
  • FIFO，先进先出

基本形态

情况 1 : 队列空

  • 条件: Q.front == Q.rear
  • 操作: 不允许出队列

情况 2 : 队列非空

实现

这里封装了基本方法

方法 描述
enqueue(element) 向队列末尾添加元素 element
dequeue() 删除队列首的元素
getFront() 读取队列首元素
getTail() 读取队列尾元素
cleanrQueue() 清空当前队列
isEmpty() 判断队列是否为空
show() 显示队列所有的元素

单链队列

function QueueList() {
  var queue = [];

  // 向队列末尾添加元素element
  this.enqueue = function(element) {
    queue.push(element);
  };

  // 删除队列首的元素
  this.dequeue = function() {
    queue.shift();
  };

  // 读取队列首元素
  this.getFront = function() {
    if (queue.length !== 0) {
      return queue[0];
    } else {
      return false;
    }
  };

  // 读取队列尾元素
  this.getTail = function() {
    return queue[queue.length - 1];
  };

  // 清空当前队列
  this.clearQueue = function() {
    queue = [];
  };

  // 判断队列是否为空
  this.isEmpty = function() {
    if (queue.length === 0) {
      return true;
    } else {
      return false;
    }
  };

  // 显示队列所有的元素
  this.show = function() {
    console.log('出列顺序为: ', queue.join(''));
  };
}

var queue = new QueueList();
queue.enqueue('a');
queue.enqueue('b');
queue.enqueue('c');
queue.enqueue('d');
// console.log(queue.getTail())
queue.clearQueue();
queue.show();

应用场景 - 基数排序

基数排序（radix sort）属于“分配式排序”（distribution sort），它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为 O (nlog(r)m)，其中 r 为所采取的基数，而 m 为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。

先看一下基数排序的的实现步骤（以两位数为例），需要扫描两次，第一次按个位数字进行排序，第二次按十位数字排序，每个数字根据对应的数值分配到到不同的盒子里，最后将盒子的数字依次取出，组成新的列表即为排序好的数字。

1 . 假设我们有一串数字，分别为 73, 22, 93, 43, 55, 14, 28, 65, 39, 81

2 . 首先第一次排序，根据个位数字排序，放到不同的盒子里，比如 81，个位数是 1，放入盒子 1...如下图

3 . 接下来将这些盒子中的数值重新串接起来，成为以下的数列：81, 22, 73, 93, 43, 14, 55, 65, 28, 39

4 . 然后根据十位数字排序，再放到不同的盒子里，如下图

5 . 接下来将这些盒子中的数值重新串接起来，整个数列已经排序完毕：14, 22, 28, 39, 43, 55, 65, 73, 81, 93

function baseSort() {
  var queues = []; // 队列数组
  var nums = []; // 需要基数排序的数组

  // 检查是否是数组类型或者是空数组
  this.checkArray = function(arr) {
    if (
      Object.prototype.toString.call(arr) == '[object Array]' &&
      arr.length !== 0
    ) {
      for (let i = 0; i < arr.length; i++) {
        nums.push(arr[i]);
      }
    } else {
      this.constructor();
    }
  };

  // 初始化，从 0 - 99 随机选10个数字进行排序
  this.constructor = function() {
    for (let i = 0; i < 10; i++) {
      queues[i] = new QueueList();
      nums.push(Math.floor(Math.random() * 101));
    }
  };

  // 基数排序, nums 为需要排序数组，queues为队列数组，n为数组长度，digit代表个位或者十位的值
  this.distribution = function(n, digit) {
    for (let i = 0; i < n; i++) {
      if (digit == 1) {
        queues[nums[i] % 10].enqueue(nums[i]); // 21 ，则 21 % 10 = 1
      } else {
        queues[Math.floor(nums[i] / 10)].enqueue(nums[i]); // 83，则 83 / 10 = 8.3
      }
    }
  };

  // 从队列中收集数字
  this.collect = function() {
    var i = 0;
    for (let digit = 0; digit < 10; digit++) {
      while (!queues[digit].isEmpty()) {
        nums[i++] = queues[digit].getFront();
        queues[digit].dequeue();
      }
    }
  };

  // 显示排序结果
  this.showResult = function() {
    console.log('排序结果为: ', nums.join(' '));
  };
}

let sortArray = [23, 39, 2, 67, 90, 41, 47, 21, 98, 13];
let foo = new baseSort();
foo.checkArray(sortArray);
foo.distribution(10, 1);
foo.collect();
foo.showResult();

循环队列 - 队列的顺序表示和实现

在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，还需要两个指针 front 和 rear，分别指示队列头元素和队列尾元素的位置。

初始化建空队列时，另 front == rear == 0 ，当插入新的队列尾元素，尾指针+1，删除队列头元素，头指针+1，在非空队列中，头指针始终指向队列头元素，尾指针始终指向队列尾元素的下一位置

基本形态

    1 . 队列空
        - 条件: Q.front == Q.rear
        - 操作: 不允许出队列

    2 . 队列满
        - (Q.rear+1) % MaxSize == Q.front
        - 操作: 不能入队列

    3 . 不空也不满
        - 操作: 可以入队，也可以出队

    4 . 加一标志位区分队列空还是队列满，因为这两种清空的 Q.front == Q.rear
        - 队列空: Q.front == Q.rear && Q.flag = 0
        - 队列满: Q.front == Q.rear && Q.flag = 1

应用场景 - 击鼓传花

拿一个东西当“花”，轮着传，“鼓”一停，拿到花的同学就要站起来唱歌，仍有此方法可使用

方法 描述
enqueue(element) 向队列末尾添加元素 element
dequeue() 删除队列首的元素
getFront() 读取队列首元素
getTail() 读取队列尾元素
cleanrQueue() 清空当前队列
isEmpty() 判断队列是否为空
show() 显示队列所有的元素 
// 基于上边队列的创建

// 其实就是出队的人又入队，形成一个循环队列的�效果

function QueueList() {
  var queue = [];
  // 向队列末尾添加元素element
  this.enqueue = function(element) {
    queue.push(element);
  };

  // 删除队列首的元素
  this.dequeue = function() {
    queue.shift();
  };

  // 读取队列首元素
  this.getFront = function() {
    if (queue.length !== 0) {
      return queue[0];
    } else {
      return false;
    }
  };

  // 读取队列尾元素
  this.getTail = function() {
    return queue[queue.length - 1];
  };

  // 清空当前队列
  this.clearQueue = function() {
    queue = [];
  };

  // 判断队列是否为空
  this.isEmpty = function() {
    if (queue.length === 0) {
      return true;
    } else {
      return false;
    }
  };

  // 显示队列所有的元素
  this.show = function() {
    console.log('出列顺序为: ', queue.join(''));
  };
}

function hotPotato(arr, count) {
  var queue = new QueueList();

  for (let i = 0; i < arr.length; i++) {
    queue.enqueue(arr[i]); // 依次入队列
  }

  console.log(queue.queue);
  var string = '';
  while (!queue.isEmpty()) {
    for (let j = 0; j < count; j++) {
      queue.enqueue(queue.dequeue()); // 将出队的人重新入队
    }
    string = queue.dequeue();
    console.log('淘汰: ', string);
  }

  return queue.dequeue();
}

var arr = ['太一', '小二', '张三', '李四', '王五'];

var winner = hotPotato(arr, 7);

console.log('获胜者: ', winner); // 获胜者: 小二

优先队列

在我们排队上厕所的时候，来了一位拥有 VIP 会员卡的朋友，插到了队伍的最前面 ，过了一会儿又来了一位拥有 SVIP 会员卡的朋友，插到了 VIP 的前面，这就是优先队列

如果优先值小的元素放到队列的前面，这叫做最小优先队列

反之优先值大的元素放到队列的前面，这叫做最大优先队列

现在来实现一个最小优先队列

function priorityQueue() {
  var queue = [];

  var queElement = function(element, priority) {
    this.element = element;
    this.priority = priority;
  };

  // 入队列
  this.enqueue = function(element, priority) {
    var queObj = new queElement(element, priority);

    if (this.isEmpty()) {
      // 如果队列是空，直接入队
      queue.push(queObj);
    } else {
      var flag = false;
      for (let i = 0; i < queue.length; i++) {
        if (queObj.priority < queue[i].priority) {
          queue.splice(i, 0, queObj); // splice() 方法，在 i 这个位置，不会删除元素，并添加 queObj 元素, 也就是把 b 插入在 a 前
          flag = true;
          break;
        }
        // console.log(queue)
      }
      if (!flag) {
        queue.push(queObj); // 如果循环一圈都没有找到能插队的位置，直接插入队列尾部
      }
    }
  };
  // 删除队列首的元素
  this.dequeue = function() {
    queue.shift();
  };

  // 读取队列首元素
  this.getFront = function() {
    if (queue.length !== 0) {
      return queue[0];
    } else {
      return false;
    }
  };

  // 读取队列尾元素
  this.getTail = function() {
    return queue[queue.length - 1];
  };

  // 清空当前队列
  this.clearQueue = function() {
    queue = [];
  };

  // 判断队列是否为空
  this.isEmpty = function() {
    if (queue.length === 0) {
      return true;
    } else {
      return false;
    }
  };

  // 显示
  this.show = function() {
    console.log(queue);
  };
}

var proQueue = new priorityQueue();
proQueue.enqueue('a', 4);
proQueue.enqueue('b', 2);
proQueue.enqueue('c', 3);
proQueue.enqueue('d', 1);
proQueue.enqueue('e', 5);
proQueue.show(); // d b c a e