您好,登錄后才能下訂單哦!
這篇文章主要講解了“JavaScript如何實現(xiàn)隊列結(jié)構(gòu)”,文中的講解內(nèi)容簡單清晰,易于學(xué)習(xí)與理解,下面請大家跟著小編的思路慢慢深入,一起來研究和學(xué)習(xí)“JavaScript如何實現(xiàn)隊列結(jié)構(gòu)”吧!
前面的博客已經(jīng)講了受限的數(shù)據(jù)結(jié)構(gòu)—棧,現(xiàn)在,我們再來看看隊列(Queue
)。
它是受限的線性表,先進先出(FIFO
),即first in first out
。
受限之處在于它只允許在表的前端(front)進行刪除操作。
而在表的后端(rear
)進行插入操作。
其結(jié)構(gòu)圖可以表示為:
生活中類似于隊列的:例如:當(dāng)我們在排隊買東西的時候,先到先買一樣。
這里也采用數(shù)組的方式實現(xiàn)隊列結(jié)構(gòu),首先,創(chuàng)建一個類。
function Queue(){ }
在其內(nèi)部添加屬性和方法,將數(shù)組通過屬性的方法添加給該類。然后采用原型的方法添加常用的操作。
隊列常用的操作有:
enqueue
(element):向隊列尾部添加一個(或多個)新的項
dequeue()
:移除隊列的第一(即排在隊列最前面的)項,并且返回被移除的元素
front()
:返回隊列中第一個元素----最先被添加,也將是最先被移除的元素
isEmpty()
:如果隊列中不包含任何元素,返回true,否則,返回false
size()
:返回隊列包含的元素個數(shù)
toString()
:將隊列中的內(nèi)容,轉(zhuǎn)化成字符串形式
現(xiàn)在就來具體實現(xiàn):
function Queue(){ this.items = []; //向隊列尾部添加一個(或多個)新的項 enqueue() Queue.prototype.enqueue = function(element){ this.items.push(element); } //移除隊列的第一(即排在隊列最前面的)項dequeue() Queue.prototype.dequeue = function(){ return this.items.shift(); } //返回隊列中第一個元素 front() Queue.prototype.front = function() { return this.items[0]; } //判斷棧是否空isEmpty() Queue.prototype.isEmpty = function(){ return this.items.length == 0; } //返回隊列包含的元素個數(shù) size() Queue.prototype.size = function(){ return this.items.length; } //將隊列中的內(nèi)容,轉(zhuǎn)化成字符串形式 toString() Queue.prototype.toString = function(){ var str = ''; for(var i =0;i<this.items.length;i++){ str += this.items[i] + ' '; } return str; } }
以上就是隊列的封裝,現(xiàn)在進行驗證:
var queue = new Queue(); queue.enqueue(10); queue.enqueue(20); queue.enqueue(30); queue.enqueue(40); queue.enqueue(50); console.log(queue); console.log('移除的第一項是:'+queue.dequeue()); console.log('隊列中的第一個元素是:'+queue.front()); console.log('棧是否為空:'+queue.isEmpty()); console.log('棧結(jié)構(gòu)的內(nèi)容為:'); console.log(queue.toString());
輸出的結(jié)果為:
構(gòu)建成功。
來看一個擊鼓傳花的案例吧!
原游戲規(guī)則:
班級中玩一個游戲,所有學(xué)生圍成一圈,從某位同學(xué)手里開始像旁邊的同學(xué)傳一束花
此時一個人在擊鼓,當(dāng)鼓聲停下的時候,花落在誰手里,誰就被懲罰。
修改游戲規(guī)則:
幾個朋友一起玩游戲,圍成一圈,開始數(shù)數(shù),數(shù)到某個數(shù)字的人自動淘汰
最后剩下的這個人獲得勝利,判斷最后剩下的是原來在哪一個位置上的人?
封裝一個基于隊列的函數(shù):
參數(shù):所有參與人的姓名,基于的數(shù)字
結(jié)果:最終剩下的人的姓名
代碼如下:
// 封裝隊列 function Queue(){ this.items = []; //末尾添加元素 Queue.prototype.enqueue = function(element){ this.items.push(element); } //移除第一個元素 Queue.prototype.dequeue = function(){ return this.items.shift(); } //返回第一個元素 Queue.prototype.front = function(){ return this.items[0]; } //返回隊列包含的元素個數(shù) Queue.prototype.size = function(){ return this.items.length; } } function passGame(nameList,num){ // 創(chuàng)建隊列 var queue = new Queue(); //將所有的人添加到隊列 for(var i = 0;i<nameList.length;i++){ queue.enqueue(nameList[i]); } //進行游戲 while(queue.size() > 1){ //num數(shù)字之前的人重新添加到隊列末尾 for(var i =1;i<num;i++){ queue.enqueue(queue.dequeue()); } //num數(shù)字的人直接移除 queue.dequeue(); } //獲取獲勝者信息 var endName = queue.front(); console.log('最終剩下的人是:'+endName); return nameList.indexOf(endName); } //進行測試 var nameList = ['a','b','c','d','e']; var g = passGame(nameList,5); console.log('這個人的位置是:'+g);
輸出結(jié)果為:
感謝各位的閱讀,以上就是“JavaScript如何實現(xiàn)隊列結(jié)構(gòu)”的內(nèi)容了,經(jīng)過本文的學(xué)習(xí)后,相信大家對JavaScript如何實現(xiàn)隊列結(jié)構(gòu)這一問題有了更深刻的體會,具體使用情況還需要大家實踐驗證。這里是億速云,小編將為大家推送更多相關(guān)知識點的文章,歡迎關(guān)注!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。