js中模拟队列详解编程语言

队列是一种先进先出的数据结构，队列的主要操作是向队列中插入新元素和删除队列中的元素，入队操作在队尾插入新元素，出队操作删除队头的元素。还有一个重要操作是读取队头的元素peek，底层的数据结构选用数组，这里通过使用js数组对象中shift和push方法简化代码。队列的构造函数如下:

   function Queue(){ 
       this.dataStore = []; 
       this.enqueue = enqueue; 
       this.dequeue = dequeue; 
       this.front = front; 
       this.back = back; 
       this.toString = toString; 
       this.empty = empty; 
   }

方法实现

enqueue方法向队尾添加一个元素

   function enqueue(element){ 
       this.dataStore.push(element); 
   }

dequeue方法删除队头的元素

   function dequeue(){ 
       this.dataStore.shift(); 
   }

用如下方法读取队首和队尾的元素

   function front(){ 
       return this.dataStore[0]; 
   } 
   function back(){ 
       return this.dataStore[this.dataStore.length - 1]; 
   }

toString方法显示队列内元素

   function toString(){ 
       var str = ''; 
       for(var i = 0, i = this.dataStore.length; i < len; i++){ 
           str += this.dataStore[i] + '/n'; 
       } 
       return str; 
   }

empty判断队列是否为空

   function empty(){ 
       return this.dataStore.length == 0; 
   }

方法使用

使用队列排序叫做基数排序，对于0-99的数字，将数据集扫描两次，第一次按照个位数上的数字进行排序，第二次按十位上的数字进行排序。

   function distribute(nums, queues, n, digit){ 
        //digit参数表示十位或个位上的值 
        //使用十个队列临时保存排序结果,n为要排序数组长度 
        //当digit=1，第一次排序后，数组在个位上有序 
        //因为队列先入先出原则，第二次排序个位上数字小的在十位队列中靠前 
    for(var i = 0; i < n; i++){ 
        digit == 1 ? 
        queues[nums[i] % 10].enqueue(nums) : 
        digit == 10 ?  
        queues[Math.floor(nums[i] / 10)].equeue(nums) 
    } 
   } 
   function collect(queues, nums, n){ 
       //对nums数组进行改变，因为nums保存了数组的引用 
       var i = 0; 
       for(var j = 0; j < n; j++){ 
          while(!queues[j].empty()){ 
             num[i++] = queues[j].dequeue(); 
          } 
       } 
   }

在调用中，先创建10个队列

   var queues = []; 
   //数组queues保存十个用来排序的队列 
   for(var i = 0; i < 10; i++){ 
       queues[i] = new Queue(); 
   } 
   //nums为要排序的数组 
   var nums = [91， 46， 85， 15， 92， 35， 31， 22]; 
   distribute(nums, queues, nums.length, 1); 
   collect(queues, nums, nums.length); 
   // nums = [91, 31, 92, 22, 85, 15, 35, 46]; 
   distribute(nums, queues, nums.length, 10); 
   collect(queues, nums, nums.length); 
   //nums = [15, 22, 31, 35, 46, 85, 91, 92];

优先队列

在一般情况下，在队列中删除的元素，一定是率先入队的元素。但是有些使用队列的应用，在删除元素不想遵守这个约定，需要使用一个叫做优先队列的数据结构来模拟。这里实现一个简单的静态优先队列，如果要使用动态的优先队列可以参考我另一篇博文堆
从优先队列中删除元素时，需要考虑优先优先权的限制，比如银行中排队的VIP用户。

   function Rank(){ 
      this.name = name; 
      //变量code标识重要程度 
      this.vipCode = vipCode; 
   }

现在重新定义dequeue方法，我们约定优先码code值最小的元素优先级最高

   function dequeue(){ 
       var entry = 0; 
       for(var i = 1; i < this.dataStore.length; i++){ 
          entry = this.dataStore[i].vipCode < this.dataStore[entry].vipCode ? i : entry; 
       } 
       //splice方法直接改变数组 
       return this.dataStore.splice(entry, 1); 
   }

在使用中，将栈的基本元素通过Rank构造

    var customer1 = new Rank('John', 5); 
    var customer2 = new Rank('Merry', 1); 
    var queue = new Queue(); 
    queue.enqueue(customer1); 
    ...