野生前端的數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)練習(xí)（2）——隊(duì)列

網(wǎng)上的相關(guān)教程非常多，基礎(chǔ)知識(shí)自行搜索即可。

習(xí)題主要選自O(shè)relly出版的《數(shù)據(jù)結(jié)構(gòu)與算法javascript描述》一書(shū)。

參考代碼可見(jiàn):https://github.com/dashnowords/blogs/tree/master/Structure/Queue

隊(duì)列的基本知識(shí)

• 特點(diǎn)：

  先進(jìn)先出。

• 用途：

  模擬流程或其他帶有抽象排隊(duì)屬性的事物或邏輯，例如時(shí)間循環(huán)隊(duì)列，發(fā)布訂閱模式的回調(diào)隊(duì)列等等。

• 基本方法

  • enqueue()在隊(duì)尾插入一個(gè)元素
  • dequeue()從隊(duì)頭刪除一個(gè)元素
  • getHeader()獲取隊(duì)頭的元素
  • getTail()獲取隊(duì)尾的元素
  • getLength()獲取隊(duì)列的長(zhǎng)度
  • isEmpty()判斷隊(duì)列是否為空隊(duì)列

• 需要留意的問(wèn)題

  使用javascript語(yǔ)言來(lái)理解數(shù)據(jù)結(jié)構(gòu)只能夠幫助我們理解結(jié)構(gòu)的基本特性，由于不涉及底層的原理，所以無(wú)法深入到算法細(xì)節(jié)的時(shí)間復(fù)雜度的話題上，對(duì)此感興趣的同學(xué)建議在學(xué)習(xí)完數(shù)據(jù)結(jié)構(gòu)入門后再去學(xué)習(xí)C語(yǔ)言描述版的數(shù)據(jù)結(jié)構(gòu)資料。

基本練習(xí)

1. 根據(jù)棧的特性實(shí)現(xiàn)一個(gè)Queue類，并在后續(xù)題目中需要用隊(duì)列時(shí)使用它。
2. 編寫(xiě)一個(gè)函數(shù)dancingQueue(str),str中記錄著前來(lái)參加舞會(huì)的人的性別，以空格分割，函數(shù)中需要實(shí)現(xiàn)將前來(lái)跳舞的人按性別分成兩隊(duì)，每當(dāng)舞池中有空位時(shí)，男隊(duì)和女隊(duì)的排在最前面的人組成舞伴進(jìn)入，如果某一隊(duì)為空時(shí)，需要返回對(duì)應(yīng)的消息。
3. 實(shí)現(xiàn)一個(gè)PriorityQueue類，實(shí)現(xiàn)優(yōu)先隊(duì)列的功能，優(yōu)先隊(duì)列的元素帶有權(quán)重，權(quán)重越高（一般認(rèn)為數(shù)字越小權(quán)重越高）的越早出隊(duì)。

課后習(xí)題（書(shū)中第五節(jié)習(xí)題）

1. 修改Queue類，生成一個(gè)Deque類，允許從隊(duì)列兩端添加和刪除元素，因此也叫雙向隊(duì)列。
2. 使用Deque類判斷一個(gè)單詞是否是回文。
3. 題目3和題目4比較簡(jiǎn)單，不再贅述。

習(xí)題思路

1. javascript中的數(shù)組就符合雙向隊(duì)列的特性，試著自己去實(shí)現(xiàn)幾個(gè)特征方法即可。

2. Deque類可以從隊(duì)列兩端出隊(duì)，每次從兩端各出隊(duì)一個(gè)元素進(jìn)行比較即可。

擴(kuò)展- 循環(huán)隊(duì)列

循環(huán)隊(duì)列書(shū)中并沒(méi)有提及，它是一種特殊的隊(duì)列。簡(jiǎn)單理解就是將基本隊(duì)列只當(dāng)做存儲(chǔ)結(jié)構(gòu)，而使用front和rear兩個(gè)指針?lè)謩e代表隊(duì)列的頭和尾，實(shí)際對(duì)外表現(xiàn)的隊(duì)列是front和rear所指向的元素構(gòu)成的。為了復(fù)用存儲(chǔ)空間，循環(huán)隊(duì)列在存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)上是首位相連的。

• 基本要素
  • front指針指向隊(duì)頭
  • rear指針指向隊(duì)尾
  • size隊(duì)列的長(zhǎng)度
  • length存儲(chǔ)空間的大小
• 基本方法
  • enqueue()元素入隊(duì)
  • dequeue()元素出隊(duì)
  • isEmpty()判斷隊(duì)空
  • isFull()判斷隊(duì)滿
  • getSize()獲取隊(duì)列長(zhǎng)度
  • getLength()獲取存儲(chǔ)空間長(zhǎng)度
  • clear()清空隊(duì)列

基本練習(xí)

實(shí)現(xiàn)一個(gè)CircularQueue類，并添加一個(gè)擴(kuò)展方法resize(),當(dāng)存儲(chǔ)空間已滿且有元素入隊(duì)時(shí)，自動(dòng)將存儲(chǔ)空間擴(kuò)充一倍，當(dāng)元素出隊(duì)造成隊(duì)列長(zhǎng)度不足存儲(chǔ)空間的1/4時(shí)，將存儲(chǔ)空間減半以釋放空間。