摘要:與堆棧區(qū)別隊(duì)列的操作方式和堆棧類似,唯一的區(qū)別在于隊(duì)列只允許新數(shù)據(jù)在后端進(jìn)行添加。移除隊(duì)列的第一項(xiàng),并返回被移除的元素。三使用隊(duì)列計(jì)算斐波那契數(shù)列的第項(xiàng)。前兩項(xiàng)固定為,后面的項(xiàng)為前兩項(xiàng)之和,依次向后。
這是第二周的練習(xí)題,這里補(bǔ)充下咯,五一節(jié)馬上就要到了,自己的計(jì)劃先安排上了,開發(fā)一個(gè)有趣的玩意兒。
下面是之前分享的鏈接:
1.每周一練 之 數(shù)據(jù)結(jié)構(gòu)與算法(Stack)
2.每周一練 之 數(shù)據(jù)結(jié)構(gòu)與算法(LinkedList)
歡迎關(guān)注我的 個(gè)人主頁 && 個(gè)人博客 && 個(gè)人知識(shí)庫 && 微信公眾號(hào)“前端自習(xí)課”
本周練習(xí)內(nèi)容:數(shù)據(jù)結(jié)構(gòu)與算法 —— Queue
這些都是數(shù)據(jù)結(jié)構(gòu)與算法,一部分方法是團(tuán)隊(duì)其他成員實(shí)現(xiàn)的,一部分我自己做的,有什么其他實(shí)現(xiàn)方法或錯(cuò)誤,歡迎各位大佬指點(diǎn),感謝。
一、隊(duì)列有什么特點(diǎn),生活中有什么例子?解題:
1.概念介紹
隊(duì)列,又稱為佇列(queue),是先進(jìn)先出(FIFO, First-In-First-Out)的線性表。在具體應(yīng)用中通常用鏈表或者數(shù)組來實(shí)現(xiàn)。隊(duì)列只允許在后端(稱為rear)進(jìn)行插入操作,在前端(稱為front)進(jìn)行刪除操作。 ——《維基百科》
隊(duì)列特點(diǎn):先進(jìn)先出操作。
生活中的案例:常見的排隊(duì),在電影院也好,排隊(duì)結(jié)賬也是,排在第一位的人會(huì)先接受服務(wù)。
2.與堆棧區(qū)別
隊(duì)列的操作方式和堆棧類似,唯一的區(qū)別在于隊(duì)列只允許新數(shù)據(jù)在后端進(jìn)行添加。
enqueue(element):向隊(duì)列尾部添加一個(gè)新的項(xiàng)。
dequeue():移除隊(duì)列的第一項(xiàng),并返回被移除的元素。
front():返回隊(duì)列中第一個(gè)元素 —— 最先被添加,也將是最先被移除的元素。隊(duì)列不做任何變動(dòng) (不移除元素,只返回元素信息 —— 與 Stack 類的 peek 方法類似)。
tail():返回隊(duì)列中的最后一個(gè)元素,隊(duì)列不做任何變動(dòng)。
isEmpty():如果棧沒有任何元素就返回 true,否則返回 false。
size():返回隊(duì)列包含的的元素個(gè)數(shù),與數(shù)組的 length 屬性類似。
print():打印隊(duì)列中的元素。
提示:Web 端優(yōu)先使用 ES6 以上的語法實(shí)現(xiàn)。
解題:
/** * 2. 實(shí)現(xiàn)一個(gè)隊(duì)列 */ class Queue { constructor (){ this.items = [] } // enqueue(element):向隊(duì)列尾部添加一個(gè)新的項(xiàng)。 enqueue( element ){ this.items.push(element) } // dequeue():移除隊(duì)列的第一項(xiàng),并返回被移除的元素。 dequeue (){ return this.items.shift() } // front():返回隊(duì)列中第一個(gè)元素 —— 最先被添加,也將是最先被移除的元素。隊(duì)列不做任何變動(dòng) (不移除元素,只返回元素信息 —— 與 Stack 類的 peek 方法類似)。 front (){ return this.items[0] } // tail():返回隊(duì)列中的最后一個(gè)元素,隊(duì)列不做任何變動(dòng)。 tail (){ return this.items[this.items.length] } // isEmpty():如果棧沒有任何元素就返回 true,否則返回 false。 isEmpty (){ return this.items.length === 0 } // size():返回隊(duì)列包含的的元素個(gè)數(shù),與數(shù)組的 length 屬性類似。 size (){ return this.items.length } // print():打印隊(duì)列中的元素。 print (){ console.log(this.items.toString()) } }三、使用隊(duì)列計(jì)算斐波那契數(shù)列的第 n 項(xiàng)。
斐波那契數(shù)列(Fibonacci sequence),又稱黃金分割數(shù)列、因數(shù)學(xué)家列昂納多·斐波那契(Leonardoda Fibonacci)以兔子繁殖為例子而引入,故又稱為“兔子數(shù)列”,指的是這樣一個(gè)數(shù)列:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377,610...
在數(shù)學(xué)上,斐波那契數(shù)列以如下被以遞推的方法定義:F(1)=1,F(xiàn)(2)=1, F(n)=F(n-1)+F(n-2)(n>=3,n∈N*),即前兩項(xiàng)固定為 1,后面的項(xiàng)為前兩項(xiàng)之和,依次向后。在現(xiàn)代物理、準(zhǔn)晶體結(jié)構(gòu)、化學(xué)等領(lǐng)域,斐波納契數(shù)列都有直接的應(yīng)用。
使用示例如下:
fibonacci(5); --> 5 fibonacci(9); --> 34 fibonacci(14); --> 377
解題:
解題方法1:
/** * 3. 使用隊(duì)列計(jì)算斐波那契數(shù)列的第 n 項(xiàng)。 * 前兩項(xiàng)固定為 1,后面的項(xiàng)為前兩項(xiàng)之和,依次向后。 * @param {Number} num */ function fibonacci (num){ if(isNaN(num) || num < 0 || num === 0) return 0 // // 1. 直接 // let n1 = 1, n2 = 1, sum // for(let i = 3; i <= num; i++){ // sum = n1 + n2 // n1 = n2 // n2 = sum // } // // 2. 隊(duì)列 考慮小于等于2 // let arr = [], sum // num === 1 && (arr = [1]) // num >= 2 && (arr = [1, 1]) // for(let i = 3; i <= num; i ++){ // sum = arr[i-2] + arr[i-3] // arr.push(sum) // } // // 3.隊(duì)列 進(jìn)出隊(duì)列 let queue = [], sum; for(let i = 1; i <= num; i ++){ if(i <=2 ){ queue.push(1) }else{ sum = queue[0] + queue[1] queue.push(sum) queue.shift() } } return sum }
解題方法2:
function fibonacci(n) { const queue = new Queue(); queue.enqueue(1); queue.enqueue(1); let index = 0; while(index < n - 2) { index += 1; // 出隊(duì)列一個(gè)元素 const delItem = queue.dequeue(); // 獲取頭部值 const headItem = queue.front(); const nextItem = delItem + headItem; queue.enqueue(nextItem); } return queue.tail(); } console.log(fibonacci(9)); // 34四、實(shí)現(xiàn)優(yōu)先隊(duì)列 PriorityQueue。
現(xiàn)實(shí)中優(yōu)先隊(duì)列的例子很多,比如機(jī)場(chǎng)登機(jī)的順序,頭等艙和商務(wù)艙乘客優(yōu)先級(jí)高于經(jīng)濟(jì)艙乘客。又如在銀行中辦理業(yè)務(wù)時(shí),VIP 客戶的優(yōu)先級(jí)高于普通客戶。要實(shí)現(xiàn)一個(gè)優(yōu)先隊(duì)列,有兩種方式:
設(shè)置優(yōu)先級(jí),然后在正確的位置添加元素。
用入列操作添加元素,然后按照優(yōu)先級(jí)移除它們。
本題要求使用第一種方式來實(shí)現(xiàn)優(yōu)先隊(duì)列,數(shù)值越小優(yōu)先級(jí)越高,若優(yōu)先級(jí)相同時(shí),先入隊(duì)的元素,排在前面。
使用示例如下:
let priorityQueue = new PriorityQueue(); priorityQueue.enqueue("leo", 2); priorityQueue.enqueue("pingan", 1); priorityQueue.enqueue("robin", 1); priorityQueue.print(); // pingan - 1 // robin - 1 // leo - 2
解題:
解題方法1:
class PriorityQueue { constructor() { this._items = []; } enqueue(element, priority) { let queueElement = { element priority }; if (this.isEmpty()) { this._items.push(queueElement); } else { let added = false; for (var i = 0; i < this.size(); i++) { if (queueElement.priority < this._items[i].priority) { this.items.splice(i, 0, queueElement); added = true; break ; } } if (!added) { this._items.push(queueElement); } } } print() { var strArr = []; strArr = this._items.map(function (item) { return `${item.element}->${item.priority}`; }); console.log(strArr.toString()); } }
解題方法2:
/** * 4. 實(shí)現(xiàn)優(yōu)先隊(duì)列 */ class PriorityQueue { constructor (){ this.items = [] } enqueue (element, priority){ let ele = {element, priority} let isAdded = false for(let i = 0; i < this.items.length; i++){ if(ele.priority < this.items[i].priority){ this.items.splice(i, 0, ele) isAdded = true break } } !isAdded && this.items.push(ele) } print (){ for(let i = 0; i < this.items.length; i++){ let {element, priority} = this.items[i] console.log(`${element} - ${priority}`) } } } let leo = new PriorityQueue() leo.enqueue("leo", 2); leo.enqueue("leo1", 1); leo.enqueue("leo2", 1); console.log(leo)五、用隊(duì)列實(shí)現(xiàn)棧。
利用兩個(gè)隊(duì)列實(shí)現(xiàn)棧,棧的特點(diǎn)是后進(jìn)先出,可以讓元素入隊(duì) q1,留下隊(duì)尾元素讓其他元素出隊(duì),暫存到 q2 中,再讓 q1 中剩下的元素出隊(duì),即最后進(jìn)的最先出來。
提示:入棧和出棧都在 q1 中完成,q2 只作為臨時(shí)中轉(zhuǎn)空間。
解題:
/** * 5. 隊(duì)列實(shí)現(xiàn)棧 */ class Myqueue { constructor (){ this.items = [] } enqueue (element){ this.items.push(element) } dequeue (){ return this.items.shift() } } class Mystack { constructor (){ this.q1 = new myQueue() this.q2 = new myQueue() } push (element){ this.q1.enqueue(element) this.q2.items = [] let len = this.q1.items.length while(len > 0){ this.q2.enqueue(this.q1.items[len-1]) len -- } } pop (){ let result = this.q2.dequeue() let len = this.q2.items.length this.q1.items = [] while(len > 0){ this.q1.enqueue(this.q2.items[len-1]) len -- } return result } print (){ console.log(this.q1.items.toString()) } }
這里也可以直接使用第二題定義的Queue來實(shí)現(xiàn):
class QueueStack { constructor() { this.queue = new Queue(); } push(item) { this.queue.enqueue(item); } pop() { // 向隊(duì)列末尾追加 隊(duì)列長度-1 次,后彈出隊(duì)列頭部 for(let i = 1; i < this.queue.size(); i += 1) { this.queue.enqueue(this.queue.dequeue()); } return this.queue.dequeue(); } peek() { return this.queue.tail(); } }下周預(yù)告
下周將練習(xí)集合(Set) 的題目,五一要到咯,也要好好做自己一個(gè)項(xiàng)目了。
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/103908.html
摘要:假設(shè)一個(gè)二叉搜索樹具有如下特征節(jié)點(diǎn)的左子樹只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。所有左子樹和右子樹自身必須也是二叉搜索樹。代碼實(shí)現(xiàn)二叉樹節(jié)點(diǎn)定義來源驗(yàn)證二叉搜索樹解析 showImg(https://segmentfault.com/img/remote/1460000019005270); 這是第六周的練習(xí)題,最近加班比較多,上周主要完成一篇 GraphQL入門教程 ,有興趣的小伙伴可以看下哈。 ...
摘要:假設(shè)一個(gè)二叉搜索樹具有如下特征節(jié)點(diǎn)的左子樹只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。所有左子樹和右子樹自身必須也是二叉搜索樹。代碼實(shí)現(xiàn)二叉樹節(jié)點(diǎn)定義來源驗(yàn)證二叉搜索樹解析這是第六周的練習(xí)題,最近加班比較多,上周主要完成一篇 GraphQL入門教程 ,有興趣的小伙伴可以看下哈。 下面是之前分享的鏈接: 1.每周一練 之 數(shù)據(jù)結(jié)構(gòu)與算法(Stack) 2.每周一練 之 數(shù)據(jù)結(jié)構(gòu)與算法(LinkedList) 3...
摘要:一集合是什么與它相關(guān)數(shù)學(xué)概念有哪些解題集合定義集合是一種包含不同元素的數(shù)據(jù)結(jié)構(gòu)。集合中的元素稱為成員,集合最重要的兩個(gè)特點(diǎn)集合中的成員是無序集合中不存在相同成員即無序且唯一。 showImg(https://segmentfault.com/img/remote/1460000019005270); 這是第四周的練習(xí)題,五一放假結(jié)束,該收拾好狀態(tài)啦。 下面是之前分享的鏈接: ...
摘要:二實(shí)現(xiàn)一個(gè)棧,并實(shí)現(xiàn)下面方法添加一個(gè)新元素到棧頂。移除棧頂?shù)脑兀瑫r(shí)返回被移除的元素。十進(jìn)制轉(zhuǎn)換為二進(jìn)制請(qǐng)輸入正確的數(shù)值方法簡(jiǎn)單實(shí)現(xiàn)下面這個(gè)方法,其實(shí)不太好,因?yàn)闆]有怎么用到這次要練習(xí)的棧方法,哈哈。 最近公司內(nèi)部在開始做前端技術(shù)的技術(shù)分享,每周一個(gè)主題的 每周一練,以基礎(chǔ)知識(shí)為主,感覺挺棒的,跟著團(tuán)隊(duì)的大佬們學(xué)習(xí)和復(fù)習(xí)一些知識(shí),新人也可以多學(xué)習(xí)一些知識(shí),也把團(tuán)隊(duì)內(nèi)部學(xué)習(xí)氛圍營造起來...
摘要:什么是散列表和散列函數(shù)哈希表,也叫散列表,是根據(jù)關(guān)鍵碼值而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。根據(jù)鍵值從散列表中移除值。請(qǐng)實(shí)現(xiàn)散列表將和存在一個(gè)對(duì)象中即可定義一個(gè)包含和屬性的類并分配到散列表。 showImg(https://segmentfault.com/img/remote/1460000019005270); 這是第五周的練習(xí)題,上周忘記發(fā)啦,這周是復(fù)習(xí) Dictionary 和 Hash...
閱讀 1768·2023-04-26 01:44
閱讀 1211·2021-11-12 10:34
閱讀 1578·2021-09-09 09:33
閱讀 1729·2019-08-30 15:44
閱讀 2892·2019-08-30 13:49
閱讀 2190·2019-08-29 15:26
閱讀 943·2019-08-26 13:30
閱讀 1409·2019-08-23 18:15