Javascriptデータ構造とアルゴリズム学習(二)——キュー

記事の目次

列は何ですか?

列の動作

列の実践——ドラムカット

優先キューと補助クラス

行列とは
キュー(Que)——先入先出(FIFO)のデータ構造です.列は列の最後に要素を挿入するだけで、最初に要素を削除します.これはスタック(LIFO)とは構造が違っています.「列に並ぶ」と見られます.
キューの操作

列に入る:enqueue

列:dequeue

列ヘッダを表示する:front

いいえ、空です.isEmpty

列サイズ:size

JSは高級な言語ですので、行列を実現するために、行列を利用してよく実現できます.

function Queue(){
     
    var items = [];
    this.enqueue = function(item){
     
        items.push(item)
    }
    this.dequeue = function( ){
     
        return items.shift()
    }
    this.front = function(){
     
        return items[0]
    }
    this.isEmpty = function(){
     
        return items.length>0
    }
    this.size = function(){
     
        return items.length
    }
}

行列の実践——太鼓を叩いて花を伝える
説明:0から転送を開始し、3番目のビットに達するごとに、3番目のビットを削除し、最後の原理まで:列を取り出すごとに前のビットを列の最後に置いて、3番目のビットになると削除する.

function delevery(names,number){
     
    var queue = new Queue();
    for(let i=0;i<names.length;i++){
     
        queue.enqueue(names[i])
    }
    while(queue.length>1){
     
        for(let i=1;i<number;i++){
     
            queue.enqueue(queue.dequeue())
        }
        queue.dequeue();
    }
    console.log(queue.front())
}
var names = ['a','b','c','d','e','f'];
delevery(names,3);

優先キューと補助クラス
優先キュー:元素の優先順位によっては、列の要素が異なります.飛行機のように、上級会員が優先的に搭乗します.一般的には、列から削除される要素は、必ず率先して列に入る要素です.ただし、特別な場合は先の約束を守らない場合があります.

function PriorityQueue(){
     
    var items = []
    //    
    var QueueItem = function (name,priority){
     
        this.name = name;
        this.priority = priority
    }
    this.enqueue = function(ele,priority){
     
        var queueItem = new QueueItem(ele,priority);
        var added = false;
        for(let i=0;i<items.length;i++){
     
            if(queueItem.priority>items[i].priority){
     
                items.splice(i,0,queueItem)
                added= true;
                break;
            }
        }
        if(!added){
     
            items.push(queueItem)
        }
    }
    this.showQueue = function(){
     
        console.log(items)
    }
}
var test = new PriorityQueue();
test.enqueue('  ',5)
test.enqueue('  ',12)
test.showQueue()