摘要：于是翻出了機(jī)房里的這本學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法開(kāi)始學(xué)習(xí)程序員的基礎(chǔ)知識(shí)。這本書用了我最熟悉的來(lái)實(shí)現(xiàn)各種數(shù)據(jù)結(jié)構(gòu)和算法，而且書很薄，可以說(shuō)是一本不錯(cuò)的入門教程。隊(duì)列在頭部刪除元素，尾部添加元素。

本系列所有文章：
第一篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之棧與隊(duì)列
第二篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之鏈表
第三篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之集合
第四篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之字典和散列表
第五篇文章：學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法之二叉搜索樹(shù)

最近要準(zhǔn)備校招，打開(kāi)某網(wǎng)站準(zhǔn)備開(kāi)始刷題，發(fā)現(xiàn)算法題根本無(wú)法動(dòng)手，于是覺(jué)得這塊需要惡補(bǔ)。(⊙v⊙)嗯，至少得先知道概念吧。于是翻出了機(jī)房里的這本《學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法》開(kāi)始學(xué)習(xí)程序員的基礎(chǔ)知識(shí)。這本書用了我最熟悉的JS來(lái)實(shí)現(xiàn)各種數(shù)據(jù)結(jié)構(gòu)和算法，而且書很薄，可以說(shuō)是一本不錯(cuò)的入門教程。雖然我是個(gè)前端，但是計(jì)算機(jī)基礎(chǔ)不能丟下。

?？梢岳斫鉃橐环N特殊的數(shù)組。遵循后進(jìn)先出(LIFO)的原則，元素在棧頂添加和刪除。生活中常用來(lái)比作棧的例子主要是一疊盤子或一堆書，但是我覺(jué)得不夠形象，因?yàn)楸P子或書可以從中間被抽走。所以我一般把?？闯蓮椣?，想象一下子彈被一個(gè)個(gè)推進(jìn)彈匣中，比如下圖：

(圖片來(lái)自谷歌搜索，侵刪)

聲明一個(gè)構(gòu)造函數(shù)：

function Stack () {
  // 使用數(shù)組來(lái)保存棧元素
  var items = []
}

為棧聲明一些方法：

push(elements(s))：添加一個(gè)或多個(gè)元素到棧頂

pop()：刪除位于棧頂?shù)脑兀⒎祷卦撛?/p>

peek()：返回棧頂元素

isEmpty()：當(dāng)前棧為空則返回true，否則為false

size()：返回棧的元素個(gè)數(shù)

clear()：清空棧

用數(shù)組的push方法向數(shù)組末尾添加新元素，實(shí)現(xiàn)元素入棧

// 棧頂添加
this.push = function (element) {
  items.push(element)
}

用數(shù)組的pop方法在數(shù)組末尾刪除一個(gè)元素，并返回刪除元素，實(shí)現(xiàn)元素出棧

// 棧頂刪除并返回刪除元素
this.pop = function () {
  return items.pop()
}

棧頂就是數(shù)組最后一個(gè)元素，使用Array[Array.length - 1]獲得

// 返回棧頂元素
this.peek = function () {
  return items[items.length - 1]
}

隊(duì)列里面也用了這些方法，為避免重復(fù)，就先多帶帶拿出來(lái)了。

// 棧是否為空
this.isEmpty = function () {
  return items.length === 0
}

// 返回棧里的元素個(gè)數(shù)
this.size = function () {
  return items.length
}

// 清空棧
this.clear = function () {
  items = []
}

// 打印棧
this.print = function () {
  console.log(items.toString())
}

書上的例子有將十進(jìn)制轉(zhuǎn)二進(jìn)制，這里我把后面那個(gè)十進(jìn)制轉(zhuǎn)任意進(jìn)制的代碼貼出來(lái)。

十進(jìn)制轉(zhuǎn)二進(jìn)制原理很簡(jiǎn)單：把十進(jìn)制數(shù)不斷除以2直到為0，然后把每次的余數(shù)拼接到一起就是二進(jìn)制數(shù)。

轉(zhuǎn)其他進(jìn)制也是類似的方法，只不過(guò)是把除以2換成其他數(shù)而已。代碼如下：

// 把十進(jìn)制轉(zhuǎn)成任何進(jìn)制
function BaseConverter (decNumber, base) {
  var remStack = new Stack(),
      rem,
      binaryString = "",
      digits = "0123456789ABCDEF"

  // 判斷十進(jìn)制數(shù)是否為0，把余數(shù)推入棧中
  while (decNumber > 0) {
    rem = Math.floor(decNumber % base)
    remStack.push(rem)
    decNumber = Math.floor(decNumber / base)
  }

  // 把棧中的元素拼接打印出來(lái)
  while (!remStack.isEmpty()) {
    binaryString += digits[remStack.pop()]
  }

  // 返回轉(zhuǎn)換的二進(jìn)制數(shù)
  return binaryString
}

這里的decNumber是要轉(zhuǎn)換的十進(jìn)制數(shù)，base是要轉(zhuǎn)換的進(jìn)制，remStack是上面Stack的實(shí)例，在remStack中操作棧的方法。這里的digits是對(duì)打印出來(lái)的數(shù)做一個(gè)處理，比如十六進(jìn)制的數(shù)余數(shù)會(huì)大于9，那么就要用A、B、C、D、E、sF來(lái)表示10～15。

棧的學(xué)習(xí)暫時(shí)就這樣了，這里貼上代碼地址，有興趣的可以看看：

棧的實(shí)現(xiàn)-源代碼

和棧很類似，只是原則不同，隊(duì)列是先進(jìn)先出（FIFO），又稱先來(lái)先服務(wù)。隊(duì)列在頭部刪除元素，尾部添加元素。生活中隊(duì)列的例子就是排隊(duì)了，這也很容易理解。

同樣聲明構(gòu)造函數(shù)：

function Queue () {
  var items = []
}

隊(duì)列的方法：

enqueue(elements(s))：向隊(duì)列尾部添加一個(gè)或多個(gè)元素

dequeue()：移除隊(duì)列頭部的元素并返回

front()：返回隊(duì)列頭部的元素

其他的和棧一樣。

用push方法推入元素

// 向隊(duì)列尾部添加元素
this.enqueue = function (element) {
  items.push(element)
}

用shift方法刪除第一個(gè)數(shù)組元素，并返回刪除的元素

// 刪除隊(duì)列頭部的元素并返回刪除元素
this.dequeue = function () {
  return items.shift()
}

直接返回第一個(gè)數(shù)組元素

// 返回隊(duì)列頭部的元素
this.front = function () {
  return items[0]
}

書上有講優(yōu)先隊(duì)列和循環(huán)隊(duì)列的應(yīng)用，這里就簡(jiǎn)單講一下優(yōu)先隊(duì)列的原理：

要實(shí)現(xiàn)優(yōu)先隊(duì)列有兩種思路：一是將元素按正確的位置添加到隊(duì)列中，然后元素正常在隊(duì)列頭部被刪除；二是元素在隊(duì)列尾部不按優(yōu)先級(jí)正常入列，然后按優(yōu)先級(jí)刪除對(duì)應(yīng)元素。

書上是按第一種思路實(shí)現(xiàn)的優(yōu)先隊(duì)列，這里限于篇幅就貼上代碼地址：

隊(duì)列的實(shí)現(xiàn)-源代碼

接下來(lái)談?wù)勓h(huán)隊(duì)列的應(yīng)用——擊鼓傳花游戲

function hotPotato (nameList, num) {
  var queue = new Queue()

  // 參與者的名字入列
  for (var i = 0; i < nameList.length; i++) {
    queue.enqueue(nameList[i])
  }

  var eliminated = ""

  // 隊(duì)列中的最后一個(gè)人為勝者
  while (queue.size() > 1) {
    // 按設(shè)定的擊鼓次數(shù)，每個(gè)人都從隊(duì)列頭部出列轉(zhuǎn)到隊(duì)列尾部（模擬傳花）
    for (var i = 0; i < num; i++) {
      queue.enqueue(queue.dequeue())
    }
    // 到了規(guī)定次數(shù)后，在隊(duì)列頭部的人（相當(dāng)于拿到花）被淘汰
    eliminated = queue.dequeue()
    console.log(eliminated + "在擊鼓傳花游戲中被淘汰")
  }

  // 勝者出列并被返回
  return queue.dequeue()
}

其中nameList是參與游戲的名字列表，num是擊鼓次數(shù)。

隊(duì)列學(xué)習(xí)就暫時(shí)到這里，明天繼續(xù)學(xué)習(xí)鏈表。