隊列是一種遵從先進先出(FIFO)原則的有序集合
隊列在尾部添加新元素,從頂部移除元素
隊列的理解
隊列在我們生活中最常見的場景就是排隊了
隊列這個名字也已經很通俗易懂了
和棧很像,這不過隊列是先入先出的數據結構
隊列的前面是隊頭
隊列的後面是隊尾
出隊從隊頭出
入隊從隊尾入
隊列的創建
和棧類似,這裡我就不就不啰嗦了
同樣需要實現一些功能
這裡我類比生活中的排隊上廁所
於是我們可以創建一個完整隊列實現,同樣是利用我們的數組實現
數組頭就是隊列頭
function Queue() { var items = []; this.enqueue = function (ele) { items.push(ele); };//入隊 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; };//隊列大小 this.clear = function () { items = []; };//清空隊列 this.print = function () { console.log(items.toString()); };//打印隊列 } var queue = new Queue(); //聲明隊列的實例
隊列的使用
下面我們就用這個隊列簡單模擬排隊
var queue = new Queue(); console.log("隊列是否為空: " + queue.isEmpty()); queue.enqueue('Mr.A'); queue.enqueue('Mr.B'); queue.enqueue('Mr.C'); console.log("當前隊列:"); queue.print(); console.log("出隊的人: " + queue.dequeue()); console.log("當前隊列:"); queue.print();
控制台打印:
優先隊列
在我們排隊上廁所的時候,來了一位擁有VIP會員卡的朋友,插到了隊伍的最前面
過了一會兒又來了一位擁有SVIP會員卡的朋友,插到了VIP的前面
雖然這個比喻可能不恰當,但是生活中可能存在有優先級的隊列
優先級高的人可以查到優先級低的人前面
這就是循環隊列
如果優先值小的元素放到隊列的前面,這叫做最小優先隊列
反之優先值大的元素放到隊列的前面,這叫做最大優先隊列
但其實他們兩個僅僅是一個判斷的改變,實現方式是一樣的
優先隊列較普通隊列的區別也就是入隊要判斷優先級,並且需要對我們的元素進行處理,其他方法不變
這處理也就是把元素包裝為一個擁有優先級的對象
既然所有對象都有著同樣的屬性,那我們毫無疑問就應該使用工廠構建
我們可以稍微修改一下我們的隊列類
來實現一個最小優先隊列
function PriorityQueue() { var items = []; function QueEle(ele, priority){ //封裝我們的元素為一個對象 this.ele = ele; //元素 this.priority = priority; //優先級 } this.enqueue = function (ele, priority) { var queObj = new QueEle(ele, priority); //創建隊列元素對象 if(this.isEmpty()){ //如果隊列是空的,直接插入 this.push(queObj); }else{ var bAdded = false; for(var i = 0, len = items.length; i < len; i++){ if(priority < items[i].priority){ items.splice(i, 0, queObj); // 循環隊列,如果優先級小於這個位置元素的優先級,插入 bAdded = true; break; } } if(!bAdded){ items.push(queObj); // 如果循環一圈都沒有找到能插隊的位置,直接插入隊列尾部 } } }; 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; }; this.clear = function () { items = []; }; this.print = function () { //這個地方稍微修改一下下 var temp = []; for(var i = 0, len = items.length; i < len; i++){ temp.push(items[i].ele); } console.log(temp.toString()); }; }
解釋我已經在代碼裡說的很明白
下面我們就用這個優先隊列同樣來模擬排隊上WC
var pQueue = new PriorityQueue(); pQueue.enqueue('Mr.A', 3); pQueue.enqueue('Mr.B', 3); pQueue.enqueue('Mr.C', 3); console.log("原隊列:"); pQueue.print(); pQueue.enqueue('VIP', 2); pQueue.enqueue('SVIP', 1); console.log("新隊列:"); pQueue.print();
控制台打印:
循環隊列
循環隊列典型的例子擊鼓傳花
還記得在我上高中的時候我們晚自習一停電就玩這個
拿一個東西當“花”,輪著傳,“鼓”一停,拿到花的同學就要站起來唱歌
可以把循環隊列當作是隊列的應用
下面我們來模擬實現循環隊列擊鼓傳花
function hotPotato(pepoleList, frequency){ //參數:表示人的數組,傳花的頻率 var queue = new Queue(); for(var i = 0, len = pepoleList.length; i < len; i++){ queue.enqueue(pepoleList[i]); //初始化,進入隊列 } var eliminated;//被淘汰的同學 while(queue.size() > 1){ //只要隊列至少還有兩個人,就一直循環 for(var i = 0; i < frequency; i++){//出隊入隊,模擬循環效果 queue.enqueue(queue.dequeue()); } eliminated = queue.dequeue();//清算 console.log(eliminated + '被淘汰'); } return queue.dequeue();//返回隊列中的最後一人 } var pepole = ['Mr.A','Mr.B','Mr.C','Mr.D','Mr.E','Mr.F']; var gameWinner = hotPotato(pepole, 12); console.log('全場最佳:' + gameWinner);
控制台輸出:
以上就是JavaScript下的隊列實現。
我們還簡單理解了兩個特殊的隊列:優先隊列與循環隊列。
以上就是本文的全部內容,希望對大家的學習有所幫助,也希望大家多多支持。