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