国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

數(shù)據(jù)結(jié)構(gòu)-隊(duì)列

miya / 1935人閱讀

摘要：隊(duì)列是一種列表不同的是隊(duì)列只能在隊(duì)尾插入元素在隊(duì)首刪除元素是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)隊(duì)列被用在很多地方比如提交操作系統(tǒng)執(zhí)行的一系列進(jìn)程打印任務(wù)池等一些仿真系統(tǒng)用隊(duì)列來模擬銀行或雜貨店排隊(duì)的顧客隊(duì)列的操作主要有兩種操作向隊(duì)尾中插入新元素入隊(duì)刪除

隊(duì)列是一種列表, 不同的是隊(duì)列只能在隊(duì)尾插入元素, 在隊(duì)首刪除元素. 是一種 先進(jìn)先出 的數(shù)據(jù)結(jié)構(gòu). 隊(duì)列被用在很多地方, 比如提交操作系統(tǒng)執(zhí)行的一系列進(jìn)程、打印任務(wù)池等, 一些仿真系統(tǒng)用隊(duì)列來模擬銀行或雜貨店排隊(duì)的顧客.
隊(duì)列的操作

主要有兩種操作:

向隊(duì)尾中插入新元素 入隊(duì) ;

刪除隊(duì)頭的元素 _出隊(duì)_;

隊(duì)列的另一項(xiàng)重要操作是讀取隊(duì)頭的元素. 這個(gè)操作叫做peek(). 該操作返回隊(duì)頭元素, 但不把它從隊(duì)列中刪除. 除了讀取隊(duì)頭元素, 我們還想知道隊(duì)列中存儲了多少元素, 可以使用length屬性滿足該需求; 想要清空隊(duì)列中所有元素, 可以使用clear()方法.

用數(shù)組實(shí)現(xiàn)的隊(duì)列

使用數(shù)組來實(shí)現(xiàn)隊(duì)列看起來順理成章. js中的數(shù)組具有其他編程語言中沒有的優(yōu)點(diǎn), 數(shù)組的push()方法可在數(shù)組末尾加入元素, shift()方法則可刪除數(shù)組的第一個(gè)元素.

push()方法將它的參數(shù)插入數(shù)組中第一個(gè)開放的位置, 該位置總是在數(shù)據(jù)的末尾, 即使是一個(gè)空數(shù)組也是如此. eg:

class Queue {
    constructor() {
        this._dataStore = [];
    }
    enqueue(element) {
        this._dataStore.push(element);
    }
    dequeue(element) {
        return this._dataStore.shift();
    }
    front() {
        return this._dataStore[0];
    }
    back() {
        return this._dataStore[this._dataStore.length - 1];
    }
    toString() {
        return this._dataStore.join(" ");
    }
    empty() {
        if(this._dataStore.length) {
            return false;
        };
        return true;
    }
    count() {
        return this._dataStore.length;
    }
};

// 測試
const q = new Queue();
q.enqueue("a");
q.enqueue("b");
q.enqueue("c");
console.log(q.toString());
q.dequeue();
console.log(q.toString());
console.log(`隊(duì)首: ${q.front()}`);
console.log(`隊(duì)尾: ${q.back()}`);

/*
輸出結(jié)果:
a b c
b c
隊(duì)首: b
隊(duì)尾: c
*/
實(shí)例 方塊舞的舞伴分配問題

當(dāng)男男女女來到舞池, 他們按照自己的性別排成兩列. 當(dāng)舞池中有地方空出來時(shí), 選兩個(gè)隊(duì)列中的第一個(gè)人組成舞伴. 他們身后的人各自向前移動(dòng)一位, 變成新的隊(duì)首. 當(dāng)一對舞伴邁入舞池時(shí), 主持人會大聲喊出他們的名字. 當(dāng)一對舞伴走出舞池, 且兩排隊(duì)伍中有任意一隊(duì)沒人時(shí), 主持人也會把這種情況告訴大家.
我們把跳舞的男男女女存在persons對象中.

function getDancers(maleDancers, femaleDancers) {
    let dancers = [];
    for(let i = 0; i < 8; i++) {
        dancers.push({
            name: `男${i + 1}`,
            sex: "M"
        });
        if(i < 5) {
            dancers.push({
                name: `女${i + 1}`,
                sex: "F"
            });
        }
    };
    
    dancers.forEach(i => {
        if(i.sex === "F") {
            femaleDancers.enqueue(i);
        } else {
            maleDancers.enqueue(i)
        }
    })
};

function dance(maleDancers, femaleDancers) {
    while(!maleDancers.empty() && !femaleDancers.empty()) {
        const female = femaleDancers.dequeue();
        const male = maleDancers.dequeue();
        console.log(`將要入場的舞者是: ${female.name}和${male.name}`);
    }
}

const maleDancers = new Queue();
const femaleDancers = new Queue();
getDancers(maleDancers, femaleDancers);
dance(maleDancers, femaleDancers);

程序輸出為:

將要入場的舞者是: 女1和男1
將要入場的舞者是: 女2和男2
將要入場的舞者是: 女3和男3
將要入場的舞者是: 女4和男4
將要入場的舞者是: 女5和男5

可能還想對該程序作如下修改: 想顯示排隊(duì)等候跳舞的男性和女性的數(shù)量. 隊(duì)列中目前尚沒有顯示元素個(gè)數(shù)的方法, 加入count()在Queue類中.

function getDancers(maleDancers, femaleDancers) {
    let dancers = [];
    for(let i = 0; i < 8; i++) {
        dancers.push({
            name: `男${i + 1}`,
            sex: "M"
        });
        if(i < 5) {
            dancers.push({
                name: `女${i + 1}`,
                sex: "F"
            });
        }
    };
    
    dancers.forEach(i => {
        if(i.sex === "F") {
            femaleDancers.enqueue(i);
        } else {
            maleDancers.enqueue(i)
        }
    })
};

function dance(maleDancers, femaleDancers) {
    while(!maleDancers.empty() && !femaleDancers.empty()) {
        const female = femaleDancers.dequeue();
        const male = maleDancers.dequeue();
        console.log(`將要入場的舞者是: ${female.name}和${male.name}`);
    }
};

const maleDancers = new Queue();
const femaleDancers = new Queue();
getDancers(maleDancers, femaleDancers);
dance(maleDancers, femaleDancers);
if(maleDancers.count() > 0) {
    console.log(`還有${maleDancers.count()}名男舞者等候`)
};
if(femaleDancers.count() > 0) {
    console.log(`還有${maleDancers.count()}名女舞者等候`)
};

程序輸出為:

將要入場的舞者是: 女1和男1
將要入場的舞者是: 女2和男2
將要入場的舞者是: 女3和男3
將要入場的舞者是: 女4和男4
將要入場的舞者是: 女5和男5
還有3名男舞者等候
數(shù)據(jù)排序

隊(duì)列不僅用于執(zhí)行顯示生活中與排隊(duì)有關(guān)的操作, 還可以用于對于數(shù)據(jù)進(jìn)行排序. 計(jì)算機(jī)剛出現(xiàn)時(shí), 程序是通過穿孔卡輸入主機(jī)的, 每張卡包含一條程序語句. 這些穿孔卡裝在個(gè)盒子里, 經(jīng)一個(gè)機(jī)械裝置進(jìn)行排序.
這種排序叫做 基礎(chǔ)排序 . 雖然它不是最快的排序算法, 但是它展現(xiàn)了一些有趣的隊(duì)列使用方法.

對于0~99的數(shù)字, 基數(shù)排序?qū)?shù)據(jù)集掃描兩次. 第一次按個(gè)位上的數(shù)字進(jìn)行排序, 第二次按照十位上的數(shù)字進(jìn)行排序. 每個(gè)數(shù)字根據(jù)對應(yīng)位上的數(shù)值被分在不同盒子里. 假設(shè)有如下數(shù)字:

91, 46, 85, 15, 92, 35, 31, 22

經(jīng)過基數(shù)排序第一次掃描之后, 數(shù)字被分配到如下盒子中:

Bin 0:
Bin 1: 91, 31
Bin 2: 92, 22
Bin 3:
Bin 4:
Bin 5: 85, 15, 35
Bin 6: 46
Bin 7:
Bin 8:
Bin 9:

根據(jù)盒子的順序, 對數(shù)字進(jìn)行一次排序的結(jié)果如下:

91, 31, 92, 22, 85, 15, 35, 46

然后根據(jù)十位上的數(shù)值再將上次排序的結(jié)果分配到不同的盒子中:

Bin 0:
Bin 1: 15
Bin 2: 22
Bin 3: 31, 35
Bin 4: 46
Bin 5: 
Bin 6: 
Bin 7:
Bin 8: 85
Bin 9: 91, 92

最后將盒子中的數(shù)字取出, 組成一個(gè)新的列表, 該列表即為排好序的數(shù)字:

15, 22, 31, 35, 45, 85, 91, 92

算法如下:

function distribute(nums, queues, n, digit) {
    for(let i = 0; i < n; i++) {
        if(digit === 1) {
            queues[nums[i] % 10].enqueue(nums[i]);
        } else {
            queues[Math.floor(nums[i] / 10)].enqueue(nums[i]);
        }
    }
};

function collect(queues, nums) {
    let i = 0;
    for(let digit = 0; digit < 10; digit++) {
        while (!queues[digit].empty()) {
            nums[i++] = queues[digit].dequeue();
        }
    }
};

function dispArray(arr) {
    let str = "";
    arr.forEach(i => {
        str += " " + i
    });
    console.log(str)
};

const queues = [];
for(let i = 0; i <= 10; i++) {
    queues[i] = new Queue()
};

const nums = [];
for(let i = 0; i < 10; i++) {
    nums[i] = Math.floor(Math.floor(Math.random() * 100))
};

dispArray(nums);
distribute(nums, queues, 10, 1);
collect(queues, nums);
distribute(nums, queues, 10, 10);
collect(queues, nums);
dispArray(nums);

下面是運(yùn)行幾次的結(jié)果:

32 35 21 63 59 83 72 22 16 10
10 16 21 22 32 35 59 63 72 83

80 22 14 57 95 11 38 99 6 11
6 11 11 14 22 38 57 80 95 99
優(yōu)先隊(duì)列

一般情況下, 從隊(duì)列中刪除元素, 一定是率先入隊(duì)的元素. 但是也有一些使用隊(duì)列的應(yīng)用, 在刪除刪除元素時(shí)不必遵守先進(jìn)先出的約定. 這種應(yīng)用, 需要使用一個(gè)叫做 優(yōu)先隊(duì)列 的數(shù)據(jù)結(jié)構(gòu)來進(jìn)行模擬.

從優(yōu)先隊(duì)列中刪除元素時(shí), 需要考慮優(yōu)先權(quán)的限制. 比如醫(yī)院急癥科的候診室, 就是一個(gè)采用 優(yōu)先隊(duì)列 的例子. 當(dāng)病人進(jìn)入候診室時(shí), 分診護(hù)士會評估患者病情的嚴(yán)重程度, 然后給一個(gè)優(yōu)先級代碼. 高優(yōu)先級的患者先于低優(yōu)先級的患者就醫(yī), 同樣優(yōu)先級的患者按照先來先服務(wù)的順序就醫(yī).

首先定義存儲隊(duì)列元素的對象, 然后再構(gòu)建我們的 優(yōu)先隊(duì)列 系統(tǒng):

function Patient(name, code) {
    this.name = name;
    this.code = code;
};

變量code是一個(gè)整數(shù), 表示患者的優(yōu)先級或病情嚴(yán)重程度.

現(xiàn)在需要重新定義dequeue()方法, 使其刪除隊(duì)列中擁有最高級優(yōu)先級的元素. 我們規(guī)定: 優(yōu)先碼的值最小的元素優(yōu)先級最高. 新的dequeue()方法遍歷隊(duì)列的底層存儲數(shù)組, 從中找出優(yōu)先碼最低的元素, 然后使用數(shù)組的splice()方法刪除優(yōu)先級最高的元素. 新的dequeue()方法如下:

dequeue(element) {
    let entry = 0;
    this._dataStore.forEach((i, index) => {
        if(i.code < this._dataStore[entry].code) {
            entry = index;
        }
    });
    return this._dataStore.splice(entry, 1);
}

dequeue()方法使用簡單的順序查找方法尋找優(yōu)先級最高的元素(代碼越小優(yōu)先級越高, eg: 1比5的優(yōu)先級高). 該方法返回包含一個(gè)元素的數(shù)組 一一 從隊(duì)列中刪除的元素.

最后需要定義toString()方法來顯示Patient對象:

toString() {
    var str = "";
    this._dataStore.forEach(i => {
        str += i.name + " code:" + i.code + "
";
    });
    return str;
}

實(shí)現(xiàn):

const ed = new Queue();
ed.enqueue(new Patient("病患1", 5))
ed.enqueue(new Patient("病患2", 4))
ed.enqueue(new Patient("病患3", 6))
ed.enqueue(new Patient("病患4", 1))
ed.enqueue(new Patient("病患5", 1))
console.log(ed.toString())
const seen = ed.dequeue();
console.log(seen[0].name)
console.log(ed.toString())

const seen1 = ed.dequeue();
console.log(seen1[0].name)
console.log(ed.toString())

const seen2 = ed.dequeue();
console.log(seen2[0].name)
console.log(ed.toString())

輸出如下:

病患1 code:5
病患2 code:4
病患3 code:6
病患4 code:1
病患5 code:1

病患4
病患1 code:5
病患2 code:4
病患3 code:6
病患5 code:1

病患5
病患1 code:5
病患2 code:4
病患3 code:6

病患2
病患1 code:5
病患3 code:6
練習(xí) 雙向隊(duì)列

修改一個(gè)Queue類, 形成一個(gè)Deque類. 這是一個(gè)和隊(duì)列類似的數(shù)據(jù)結(jié)構(gòu), 允許從隊(duì)列兩端添加和刪除元素, 因此也叫 雙向隊(duì)列 . 寫一段測試程序測試該類:

class Queue {
    constructor() {
        this._dataStore = [];
    }
    // 隊(duì)尾入隊(duì)
    enqueueBack(element) {
        this._dataStore.push(element);
    }
    // 隊(duì)首入隊(duì)
    enqueueFront(element) {
        this._dataStore.unshift(element);
    }
    // 隊(duì)尾出隊(duì)
    dequeueBack() {
        return this._dataStore.pop();
    }
    // 隊(duì)首出隊(duì)
    dequeueFront() {
        return this._dataStore.shift();
    }
    // 第一個(gè)
    front() {
        return this._dataStore[0];
    }
    // 最后一個(gè)
    back() {
        return this._dataStore[this._dataStore.length - 1];
    }
    // 輸出
    toString() {
        return this._dataStore.join(" ");
    }
    // 是否為空
    empty() {
        if(this._dataStore.length) {
            return false;
        };
        return true;
    }
    // 個(gè)數(shù)
    count() {
        return this._dataStore.length;
    }
};

const d = new Queue();
d.enqueueBack(3)
d.enqueueBack(4)
d.enqueueBack(5)
console.log(d.toString())
d.enqueueFront(2)
d.enqueueFront(1)
console.log(d.toString())
d.dequeueBack()
d.dequeueBack()
console.log(d.toString())
d.dequeueFront()
console.log(d.toString())

輸入結(jié)果:

3 4 5
1 2 3 4 5
1 2 3
2 3
使用Deque類來判斷一個(gè)給定單詞是否為回文

首先讓單詞每個(gè)字母入隊(duì), 然后兩端同時(shí)出隊(duì), 判斷隊(duì)首隊(duì)尾字母是否相等.

const str = "121"

function isPalindrome(word) {
    const d = new Queue();

    for(let w of word) {
        d.enqueueBack(w)
    };

    while(!d.empty()) {
        if(d.front() !== d.back()) {
            return false;
        } else {
            d.dequeueBack();
            d.dequeueFront();
        }
    };

    return true;
};

console.log(isPalindrome(str)); // true
修改文章中 優(yōu)先隊(duì)列 使得優(yōu)先級高的元素優(yōu)先碼也大.

這里只需要在出隊(duì)的時(shí)候按照優(yōu)先碼最大的先出隊(duì).

...
dequeue(element) {
    let entry = 0;
    this._dataStore.forEach((i, index) => {
        if(i.code > this._dataStore[entry].code) {
            entry = index;
        }
    });
    return this._dataStore.splice(entry, 1);
}
...

驗(yàn)證:

function Patient(name, code) {
    this.name = name;
    this.code = code;
};
const ed = new Queue();
ed.enqueue(new Patient("病患1", 5))
ed.enqueue(new Patient("病患1-1", 5))
ed.enqueue(new Patient("病患3", 6))
ed.enqueue(new Patient("病患4", 1))
ed.enqueue(new Patient("病患5", 1))
console.log(ed.toString())
const seen = ed.dequeue();
console.log("出隊(duì)病患 =>", seen[0].name)
console.log(ed.toString())

const seen1 = ed.dequeue();
console.log("出隊(duì)病患 =>", seen1[0].name)
console.log(ed.toString())

const seen2 = ed.dequeue();
console.log("出隊(duì)病患 =>", seen2[0].name)
console.log(ed.toString())

輸入結(jié)果:

病患1 code:5
病患1-1 code:5
病患3 code:6
病患4 code:1
病患5 code:1

出隊(duì)病患 => 病患3
病患1 code:5
病患1-1 code:5
病患4 code:1
病患5 code:1

出隊(duì)病患 => 病患1
病患1-1 code:5
病患4 code:1
病患5 code:1

出隊(duì)病患 => 病患1-1
病患4 code:1
病患5 code:1
修改上例, 使得候診室內(nèi)的活動(dòng)可以被控制

類似菜單系統(tǒng), 讓用戶可以進(jìn)行如下選擇:

患者進(jìn)入候診室

患者就診

顯示等待就診患者名單

class Queue {
    constructor() {
        this._dataStore = [];
    }
    enqueue(element) {
        this._dataStore.push(element);
    }
    dequeue(element) {
        let entry = 0;
        this._dataStore.forEach((i, index) => {
            if(i.code > this._dataStore[entry].code) {
                entry = index;
            }
        });
        return this._dataStore.splice(entry, 1);
    }
    front() {
        return this._dataStore[0];
    }
    back() {
        return this._dataStore[this._dataStore.length - 1];
    }
    toString() {
        var str = "";
        this._dataStore.forEach(i => {
            str += i.name + " code:" + i.code + "
";
        });
        return str;
    }
    empty() {
        if(this._dataStore.length) {
            return false;
        };
        return true;
    }
    count() {
        return this._dataStore.length;
    }
};

class Room {
    constructor() {
        this._q = new Queue();
    }
    // 患者進(jìn)入候診室 code值越大 優(yōu)先級越高
    enter(name, code) {
        this._q.enqueue({
            name, code
        });
    }
    // 患者就診 也是就是從候診室隊(duì)列中出隊(duì)
    seeDoctor() {
        return this._q.dequeue()[0].name;
    }
    // 顯示等待就診患者名單
    showRoom() {
        return this._q.toString();
    }
};

const r = new Room();
r.enter("患者1", 2);
r.enter("患者2", 3);
r.enter("患者3", 1);
r.enter("患者4", 4);
r.enter("患者5", 4);
r.enter("患者6", 5);
console.log(r.showRoom())
console.log(r.seeDoctor(), "   就診")
console.log(r.seeDoctor(), "   就診")
console.log(r.showRoom())
console.log(r.seeDoctor(), "   就診")
console.log(r.showRoom())

輸出結(jié)果:

患者1 code:2
患者2 code:3
患者3 code:1
患者4 code:4
患者5 code:4
患者6 code:5

患者6    就診
患者4    就診
患者1 code:2
患者2 code:3
患者3 code:1
患者5 code:4

患者5    就診
患者1 code:2
患者2 code:3
患者3 code:1

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/97847.html

相關(guān)文章

  • JavaScript數(shù)據(jù)結(jié)構(gòu)《隊(duì)列》

    摘要：在隊(duì)列的這種數(shù)據(jù)結(jié)構(gòu)里面，新增的元素都在尾部，要移除的元素都在頂部。代碼實(shí)現(xiàn)下面用代碼來實(shí)現(xiàn)隊(duì)列這個(gè)數(shù)據(jù)結(jié)構(gòu)，同樣都采用的語法，我們先定義一個(gè)類來表示隊(duì)列，然后在這個(gè)類的基礎(chǔ)上定義一下方法來模擬隊(duì)列的行為。 隊(duì)列和棧非常的類似，但是他們采用了不同的原則，棧采用的是后進(jìn)先出，隊(duì)列正好相反，采用的是先進(jìn)先出的原則。隊(duì)列的定義如下 隊(duì)列是遵循FIFO(先進(jìn)先出)原則的有序集合，新添加的元素保...

    saucxs 評論0 收藏0

  • Java數(shù)據(jù)結(jié)構(gòu)與算法[原創(chuàng)]——隊(duì)列

    摘要：前言數(shù)據(jù)結(jié)構(gòu)與算法專題會不定時(shí)更新，歡迎各位讀者監(jiān)督。隊(duì)列和棧類似，也是一個(gè)遵循特殊規(guī)則約束的數(shù)據(jù)結(jié)構(gòu)。將沒有元素的隊(duì)列稱之為空隊(duì)，往隊(duì)列中插入元素的過程稱之為入隊(duì)，從隊(duì)列中移除元素的過程稱之為出隊(duì)。 聲明：碼字不易，轉(zhuǎn)載請注明出處，歡迎文章下方討論交流。 前言：Java數(shù)據(jù)結(jié)構(gòu)與算法專題會不定時(shí)更新，歡迎各位讀者監(jiān)督。本文介紹數(shù)據(jù)結(jié)構(gòu)中的隊(duì)列（queue）的概念、存儲結(jié)構(gòu)、隊(duì)列的特點(diǎn)...

    韓冰 評論0 收藏0

  • [ JavaScript ] 數(shù)據(jù)結(jié)構(gòu)與算法 —— 隊(duì)列

    摘要：而且目前大部分編程語言的高級應(yīng)用都會用到數(shù)據(jù)結(jié)構(gòu)與算法以及設(shè)計(jì)模式。隊(duì)列在尾部添加新元素，并從頂部移除元素。最新添加的元素必須排在隊(duì)列的末尾。 前言 JavaScript是當(dāng)下最流行的編程語言之一，它可以做很多事情： 數(shù)據(jù)可視化（D3.js，Three.js，Chart.js）; 移動(dòng)端應(yīng)用(React Native,Weex,AppCan,Flutter,Hybrid App,小程...

    Yi_Zhi_Yu 評論0 收藏0

  • java 隊(duì)列

    摘要：是基于鏈接節(jié)點(diǎn)的線程安全的隊(duì)列。通過這些高效并且線程安全的隊(duì)列類，為我們快速搭建高質(zhì)量的多線程程序帶來極大的便利。隊(duì)列內(nèi)部僅允許容納一個(gè)元素。該隊(duì)列的頭部是延遲期滿后保存時(shí)間最長的元素。 隊(duì)列簡述 Queue： 基本上，一個(gè)隊(duì)列就是一個(gè)先入先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)Queue接口與List、Set同一級別，都是繼承了Collection接口。LinkedList實(shí)現(xiàn)了Deque接 口。...

    goji 評論0 收藏0

發(fā)表評論

0條評論

miya

男|高級講師

TA的文章

閱讀更多
最新活動(dòng)
閱讀需要支付1元查看
<