野生前端的數據結構基礎練習（2）——隊列

網上的相關教程非常多，基礎知識自行搜索即可。

習題主要選自Orelly出版的《數據結構與算法javascript描述》一書。

參考代碼可見:https://github.com/dashnowords/blogs/tree/master/Structure/Queue

隊列的基本知識

• 特點：

  先進先出。

• 用途：

  模擬流程或其他帶有抽象排隊屬性的事物或邏輯，例如時間循環隊列，發布訂閱模式的回調隊列等等。

• 基本方法

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

• 需要留意的問題

  使用javascript語言來理解數據結構只能夠幫助我們理解結構的基本特性，由于不涉及底層的原理，所以無法深入到算法細節的時間復雜度的話題上，對此感興趣的同學建議在學習完數據結構入門后再去學習C語言描述版的數據結構資料。

基本練習

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

課后習題（書中第五節習題）

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

習題思路

1. javascript中的數組就符合雙向隊列的特性，試著自己去實現幾個特征方法即可。

2. Deque類可以從隊列兩端出隊，每次從兩端各出隊一個元素進行比較即可。

擴展- 循環隊列

循環隊列書中并沒有提及，它是一種特殊的隊列。簡單理解就是將基本隊列只當做存儲結構，而使用front和rear兩個指針分別代表隊列的頭和尾，實際對外表現的隊列是front和rear所指向的元素構成的。為了復用存儲空間，循環隊列在存儲結構的實現上是首位相連的。

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

基本練習

實現一個CircularQueue類，并添加一個擴展方法resize(),當存儲空間已滿且有元素入隊時，自動將存儲空間擴充一倍，當元素出隊造成隊列長度不足存儲空間的1/4時，將存儲空間減半以釋放空間。