javascriptデータ構造とアルゴリズム読書ノート＞第五章行列

キューはリストですが、要素を列の最後に挿入し、最初に削除します.キューは順番に並べられたデータを保存するために使用されます.先に出ます.そして、スタックは、むしろ後入スタックの要素が優先される.
実際にはプロセスプールやキュー操作に応用されます.
1.キューの操作
前の章のスタックと同様に、列も入隊、出隊、空行列という基本的な操作を持つべきです.
基本構造は以下の通りです.
 

function Queue(){

    this.dataStore = [];

    this.enqueue = enqueue;

    this.dequeue = dequeue;

    this.front = front;

    this.back = back;

    this.isEmpty = isEmpty; 
　　 this.clear = clear;
}

 
2.行列で実現する行列
入隊操作:

function enqueue(elem){

    this.dataStore.push(elem);

}

 
      列から出る操作(列の先頭要素をイジェクト):

function dequeue(){

    return this.dataStore.shft();

}

チームの先頭と最後の要素を返します.

function front(){

    return this.dataStore[0]

}

function back(){

    return this.dataStore[this.dataStore.length-1];

}

 キューが空かどうかを判断します.

function empty(){

   if(this.dataStore.length>0){

        return true;

   }else{

        return false;

   }

}

クリアキュー操作は他の操作と一致しています.リターン長は直接return this.dataStore.lengthでいいです.
3.四角いダンスのパートナー割り当て問題
まず、私たちはダンスホールのダンサーダンスが必要です.

function Dancer(name, sex){

   this.name = name;

   this.sex = sex;

}

その後、私たちはダンサーを追加して列に入ります.

var maleQueue = new Queue();
var femaleQueue = new Queue();

femaleQueue.enqueue(new Dancer('Herry', 'F')); 
femaleQueue.enqueue(new Dancer('Kerry', 'F')); 

maleQueue.enqueue(new Dancer('Jimmy', 'M')); 
maleQueue.enqueue(new Dancer('Lisa', 'M')); 
maleQueue.enqueue(new Dancer('Lima', 'M'));

マッチングダンサー:

function dance(males, females){

    console.info("The dancer partners are: 
");

    var person;

    while(!males.empty() && !females.empty()){

        person = males.dequeue();

        console.info("The Male is " + person.name);

        person = females.dequeue();

        console.info("The Female is " + person.name);

    }

    console.info('
');

    while(!males.empty()){

        person = males.dequeue();

        console.info(person.name + " is waiting!");

    }

    while(!females.empty()){

        person = females.dequeue();

        console.info(person.name + " is waiting!");

    }

}

テスト:

dance(femaleQueue, maleQueue);

4.データを並べ替える
キューの並べ替えを使用するのは効率的な最高の並べ替えアルゴリズムではなく、より興味深い方法といえる.
私達は並べ替えをする時、異なる桁数によって並べ替えます.
たとえば数字のセットがあります.
82,13,33,98,93,12,5,88,3
まずその桁数を並べ替えます.
0: 
1: 
2:82,12
3:13,33,93,3
4: 
5:5
6:
7:
8:98、88
9: 
その中の数字を順番に取り出します.
98,88,5,13,33,93,3,82,12
10桁の数字で並べ替えます.
0:
1:13,12
2:
3:33
4:
5:
6:
7:
8:88,82
9:98,93
データを取り出す:
98,93,88,82,33,13,12
残りの桁数を加えます.
98,93,88,82,33,13,12,5,3
 実装:
まず、一組の数をそれぞれの桁によって0～9十個の列に割り当てることを実現します.

/**

*    nums -----       

*    queues -----    0~9         

*    n -----  nums   n      

*      digit -----         

*/

function distribute(nums, queues, n, digit){



    //        

    var index = 0;

    

    //        n  

    for(var i=0;i<n;i++){

        

        //          

        if(digit == 1){

            

            //       10             

            index = nums[i] % 10; 

            

            //             

            queues[index].enqueue(nums[i]);

        }else{



            //        10             

            index = Math.floor(nums[i]/10); 



            //             

            queues[index].enqueue(nums[i]);

        }

    }

}

割り当てを行うたびに、私たちは一度にチームから出て操作し、新しい配列に入れます.

/**

*    queues -----    0~9         

*    nums -----        

**/

function collect(queues, nums){



    //        

    var i = 0;



    //        10   

    for(var digit=0; digit<10;digit++){



        //                    

        while(!queues[digit].empty()){



            //                    

            nums[i++] = queues[digit].dequeue();

        }

    }

}

配列の結果を表示:

//            

function dispArray(arr){

    for(var i=0;i<arr.length;i++){

        console.info(arr[i] + " ");

    }

}

テスト:

 1 //             ，      0~9       

 2 var queues = [];

 3 for(var i=0; i<10; i++){

 4     queues[i] = new Queue();

 5 }

 6 

 7 //                

 8 var nums = [];

 9 

10 //           1~99   

11 for(var i=0;i<10;i++){

12     nums[i] = Math.floor(Math.floor(Math.random() * 101));

13 }

14 

15 console.info("Before radix sort:");

16 dispArray(nums);

17 

18 //                

19 distribute(nums, queues, 10, 1);

20 

21 //                         

22 collect(queues, nums)

23 

24 //                

25 distribute(nums, queues, 10, 10);

26 

27 //                         

28 collect(queues, nums);

29 

30 console.info('

 After radix sort:');

31 dispArray(nums);

5.優先順位
私達は普通の状況では先発的な方式で列を作って作業することを知っていますが、この方法はいくつかの特殊な状況を満たすことができません.例えば、私達が並んでいる時にvipメンバーがいます.
行列内のオブジェクトにコード属性を追加できます.この変数の優先度を示します.

function Customer(name, code){

      this.name = name;

      this.code = code;
　　　 this.toString = function(){
         console.info(this.name+":"+this.code);
      };
}

var ord1 = new Customer('Jimmery', 1); var ord2 = new Customer('Kate', 1); var ord3 = new Customer('Lame', 1); var vip1 = new Customer('Andy', 2); var vip2 = new Customer('Dave', 2); var cusQueues = new Queue(); cusQueues.push(ord1); cusQueues.push(vip1); cusQueues.push(ord2); cusQueues.push(vip2); cusQueues.push(ord3);

このようにチーム操作をする時は優先度の比較を行います.

var dequeue = function(){

   

   //               

   var prio = this.dataStore[0].code;



   //           

   var index = 0;

   for(var i=1; i<this.dataStore.length; i++){

    

        //             

        if(this.dataStore[i].code>prio){

               

               //               

               index = i;

        }

   }



   return this.dataStore.splice(index, 1);   

} 

 
今テストを行います.

while(!cusQueues.empty()){

    var cus = cusQueues.dequeue();

    console.info(cus.toString());

}