JavaScript隊(duì)列數(shù)據(jù)結(jié)構(gòu)詳解
寫(xiě)在前面:
在上一篇文章中介紹了棧這個(gè)數(shù)據(jù)結(jié)構(gòu),這篇文章介紹一下隊(duì)列。
什么是隊(duì)列?
隊(duì)列是一種先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu),隊(duì)列中允許兩種基礎(chǔ)操作,也就是插入和刪除,也就是入隊(duì)和出隊(duì);我們將隊(duì)列中允許插入的一端稱(chēng)為隊(duì)尾、允許刪除的一端稱(chēng)為隊(duì)頭;
如下圖展示了棧這個(gè)數(shù)據(jù)結(jié)構(gòu):
JavaScript中的隊(duì)列
JavaScript并沒(méi)有隊(duì)列這個(gè)數(shù)據(jù)類(lèi)型,但是可以通過(guò)數(shù)組進(jìn)行模擬,而且數(shù)組中提供的push()
和shift()
選項(xiàng),正好實(shí)現(xiàn)先入后出的的操作,
示例代碼如下:
const queue = [] // 入隊(duì) stack.push(1) stack.push(2) // 出隊(duì) const v1 = stack.shift() // 1 const v2 = stack.shift() // 2
JavaScript中的應(yīng)用場(chǎng)景
隊(duì)列和棧一樣,是算法和程序中最常用的輔助結(jié)構(gòu),其的應(yīng)用十分廣泛,比如以下場(chǎng)景:
- 現(xiàn)實(shí)生活中的排隊(duì),就比如說(shuō)買(mǎi)飯排隊(duì),先去的先買(mǎi),也就是先進(jìn)先出;
- 銀行、營(yíng)業(yè)廳等號(hào)叫號(hào),例如:到了營(yíng)業(yè)廳先去排號(hào)機(jī)哪里排號(hào),然后等待叫號(hào),叫號(hào)會(huì)依次叫號(hào);
- JavaScript中的異步任務(wù)隊(duì)列,異步任務(wù)隊(duì)列是一個(gè)典型的應(yīng)用隊(duì)列的例子。
最近的請(qǐng)求次數(shù)
現(xiàn)在我們來(lái)做一個(gè)力扣的題來(lái)熟悉一下隊(duì)列這個(gè)數(shù)據(jù)結(jié)構(gòu),這個(gè)題是【933. 最近的請(qǐng)求次數(shù)】,主要題目描述是寫(xiě)一個(gè) **** 類(lèi)來(lái)計(jì)算特定時(shí)間范圍內(nèi)最近的請(qǐng)求。
解題思路如下:
- 在類(lèi)中創(chuàng)建一個(gè)隊(duì)列,用于保存最近請(qǐng)求;
- ping時(shí)保存請(qǐng)求;
- 判斷隊(duì)頭請(qǐng)求時(shí)間是否比
t-3000
的時(shí)間少,如果是則出隊(duì),并繼續(xù)判斷,如果不是則返回隊(duì)列長(zhǎng)度。
實(shí)現(xiàn)代碼如下:
var RecentCounter = function() { this.q = [] }; /** * @param {number} t * @return {number} */ RecentCounter.prototype.ping = function(t) { this.q.push(t) while(this.q[0] < t - 3000) { this.q.shift() } return this.q.length };
補(bǔ)充
概念和結(jié)構(gòu):
- 隊(duì)列是一種先進(jìn)先出(FIFO)的數(shù)據(jù)結(jié)構(gòu)。
- 隊(duì)列的第一個(gè)元素所在位置稱(chēng)為隊(duì)頭,最后一個(gè)元素所在位置稱(chēng)為隊(duì)尾。
- 不包含任何元素的隊(duì)列稱(chēng)為空隊(duì)列。
隊(duì)列的操作:隊(duì)列有五種常用操作,分別為:
- 入隊(duì) enqueue(element)
- 出隊(duì) dequeue()
- 檢查隊(duì)頭元素 front()
- 檢查隊(duì)列是否為空 isEmpty()
- 獲取隊(duì)列的長(zhǎng)度 size()
JS實(shí)現(xiàn):
JS里面的隊(duì)列結(jié)構(gòu)也是通過(guò)數(shù)組(Array)來(lái)實(shí)現(xiàn)的。
function Queue(){ ? ? //私有變量不被外界獲取 ? ? let queue = []; ? ? //入隊(duì) ? ? this.enqueue = function(element){ ? ? ? ? queue.push(element); ? ? } ? ? //出隊(duì) ? ? this.dequeue = function(){ ? ? ? ? return queue.shift(); ? ? } ? ? //檢查隊(duì)頭元素 ? ? this.front = function(){ ? ? ? ? return queue[0]; ? ? } ? ? //檢查隊(duì)列是否為空 ? ? this.isEmpty = function(){ ? ? ? ? return queue.length === 0; ? ? } ? ? //獲取隊(duì)列長(zhǎng)度 ? ? this.size = function(){ ? ? ? ? return queue.length; ? ? } }
總結(jié)
文本介紹了什么是隊(duì)列以及JavaScript中可以使用數(shù)組模擬隊(duì)列,在最后還講解一個(gè)力扣中的算法題目。
到此這篇關(guān)于JavaScript隊(duì)列數(shù)據(jù)結(jié)構(gòu)詳解的文章就介紹到這了,更多相關(guān)JS隊(duì)列數(shù)據(jù)結(jié)構(gòu)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
- JavaScript樹(shù)形數(shù)據(jù)結(jié)構(gòu)處理
- JavaScript數(shù)據(jù)結(jié)構(gòu)與算法
- JavaScript數(shù)據(jù)結(jié)構(gòu)與算法之棧詳解
- Javascript數(shù)據(jù)結(jié)構(gòu)之棧和隊(duì)列詳解
- ?JavaScript?數(shù)據(jù)結(jié)構(gòu)之散列表的創(chuàng)建(2)
- JavaScript?數(shù)據(jù)結(jié)構(gòu)之字典方法
- JavaScript?數(shù)據(jù)結(jié)構(gòu)之集合創(chuàng)建(2)
- JavaScript?數(shù)據(jù)結(jié)構(gòu)之集合創(chuàng)建(1)
- JavaScript數(shù)據(jù)結(jié)構(gòu)常見(jiàn)面試問(wèn)題整理
相關(guān)文章
webpack的tree shaking的實(shí)現(xiàn)方法
這篇文章主要介紹了webpack的tree shaking的實(shí)現(xiàn)方法,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-09-09原生js實(shí)現(xiàn)tab選項(xiàng)卡切換
這篇文章主要為大家詳細(xì)介紹了原生js實(shí)現(xiàn)tab選項(xiàng)卡,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2016-08-08javascript 函數(shù)參數(shù)限制說(shuō)明
我依稀記得哪本書(shū)上有說(shuō)過(guò),實(shí)參數(shù)限制是32個(gè)? 現(xiàn)在想想估計(jì)是我記錯(cuò)了..他也許說(shuō)的是32位.2010-11-11JavaScript 動(dòng)態(tài)創(chuàng)建VML的方法
JavaScript 動(dòng)態(tài)創(chuàng)建VML的方法,需要的朋友可以參考下。2009-10-10解決Webpack 熱部署檢測(cè)不到文件變化的問(wèn)題
下面小編就為大家分享一篇解決Webpack 熱部署檢測(cè)不到文件變化的問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2018-02-02Js為表單動(dòng)態(tài)添加節(jié)點(diǎn)內(nèi)容的方法
這篇文章主要介紹了Js為表單動(dòng)態(tài)添加節(jié)點(diǎn)內(nèi)容的方法,實(shí)例分析了js針對(duì)表單節(jié)點(diǎn)進(jìn)行添加操作的常用技巧,需要的朋友可以參考下2015-02-02出現(xiàn)“不能執(zhí)行已釋放的Script代碼”錯(cuò)誤的原因及解決辦法
出現(xiàn)“不能執(zhí)行已釋放的Script代碼”錯(cuò)誤的原因及解決辦法...2007-08-08理解javascript定時(shí)器中的setTimeout與setInterval
這篇文章主要幫助大家學(xué)習(xí)理解javascript定時(shí)器中的setTimeout與setInterval,從實(shí)例出發(fā)進(jìn)行深入探討,感興趣的小伙伴們可以參考一下2016-02-02JavaScript數(shù)組去重和扁平化函數(shù)介紹
這篇文章主要介紹了JavaScript數(shù)組去重和扁平化函數(shù),數(shù)組扁平化又稱(chēng)數(shù)組降維,下面文章圍繞數(shù)組去重和扁平化函數(shù)得相關(guān)資料展開(kāi)內(nèi)容,需要的朋友可以參考一下2021-12-12arcgis for js柵格圖層疊加(Raster Layer)問(wèn)題
這篇文章主要介紹了arcgis for js柵格圖層疊加(Raster Layer)的相關(guān)資料,非常不錯(cuò),具有參考借鑒價(jià)值,需要的朋友可以參考下2017-11-11