基本概念

队列是一种列表，不同的是队列只能在队尾插入元素，在队首删除元素。队列用于存储按 顺序排列的数据，先进先出，队列是一种先进先出（First-In-First-Out，FIFO）的数据结构。
浏览器/操作系统中的事件处理就是队列的数据结构，而函数调用栈使用栈数据结构。

队列的基本操作

  • 插入操作也叫做入队 enqueue()
  • 删除操作也叫做出队 dequeue()
  • 是读取队首队尾的元素 front(),back()。
  • 队列中存储了多少元素使用 length 属性
  • 清空队列中的所有元素，可以使用 clear() 方法
  • toString() 方法显示队列内的所有元素

    队列的顺序存储-JavaScript实现

    线性表的顺序存储和链式存储，对于队列来说，也是同样适用的。
    1. function Queue() {
    2. this.dataSource = [];
    3. this.enqueue = enqueue;
    4. this.dequeue = dequeue;
    5. this.front = front;
    6. this.back = back;
    7. this.toString = toString;
    8. this.clear = clear;
    9. this.empty = empty;
    10. }
    11. function enqueue(element) {
    12. this.dataSource.push(element);
    13. }
    14. function dequeue() {
    15. return this.dataSource.shift();
    16. }
    17. function front() {
    18. return this.dataSource[0];
    19. }
    20. function back() {
    21. return this.dataSource[this.dataSource.length - 1];
    22. }
    23. function toString() {
    24. let retStr = "";
    25. for (let i = 0; i < this.dataSource.length; ++i) {
    26.   retStr += this.dataSource[i] + "\n";
    27. }
    28. return retStr;
    29. }
    30. function empty() {
    31. return this.dataSource.length === 0;
    32. }
    33. function clear() {
    34. this.dataSource = [];
    35. }

    使用队列来解决问题-基数排序

    基数排序将数据集扫描两次，第一次按个位上的数字进行排序，第二次按十位上的数字进行排序。每个数字根据对应位上的数值被分在不同的盒子里。使用队列代表盒子。
    1. function distribute(nums,queues,n,digit) {
    2.   for (let i = 0;i<n;n++){
    3.       if (digit === 1){
    4.           queues[nums[i]%10].enqueue(nums[i])
    5.       }else{
    6.           queues[Math.floor(nums[i]/10)].enqueue(nums[i])
    7.       }
    8.   }
    9. }
    10. function collect(queues, nums) {
    11.   let i = 0;
    12.   for (let digit = 0; digit < 10; ++digit) {
    13.       while (!queues[digit].empty()) {
    14.           nums[i++] = queues[digit].dequeue();
    15.       }
    16.   }
    17. }
    下面是实例：
    1. let nums = [45, 78, 78, 89, 45, 45, 42, 14, 48];
    2. let queues = [];
    3. for (let i = 0; i < 10; ++i) {
    4. queues[i] = new Queue();
    5. }
    6. distribute(nums, queues, 1);
    7. collect(queues,nums);
    8. distribute(nums, queues, 10);
    9. collect(queues,nums);
    先把nums数据放到queues里，再把queues数据按顺序放回nums里，进行两次就排好了