摘要：之?dāng)?shù)組操作接下來(lái)就是數(shù)據(jù)結(jié)構(gòu)的第一部分，棧。以字符串顯示棧中所有內(nèi)容方法的實(shí)現(xiàn)說(shuō)明需要往棧中添加新元素，元素位置在隊(duì)列的末尾。的前端樂(lè)園原文鏈接寒假前端學(xué)習(xí)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法，棧與隊(duì)列

本系列的第一篇文章: 學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（一），棧與隊(duì)列
第二篇文章：學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（二）：鏈表
第三篇文章：學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（三）：集合
第四篇文章：學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（四）：二叉搜索樹(shù)

曾經(jīng)有一次在逛V2EX時(shí)，碰到這么一個(gè)帖子。

數(shù)學(xué)完全還給老師了，想學(xué)回一些基礎(chǔ)數(shù)學(xué)，大概是高中程度的，有什么書(shū)籍推薦？

發(fā)帖的樓主大學(xué)沒(méi)有高數(shù)課程，出去工作時(shí)一直在從事前端的工作。感覺(jué)到數(shù)學(xué)知識(shí)的匱乏，所以想補(bǔ)一補(bǔ)數(shù)學(xué)。
看了看帖子，感覺(jué)和我很像，因?yàn)槲业膶I(yè)是不開(kāi)高數(shù)的，我學(xué)的也是前端。也同樣感覺(jué)到了數(shù)學(xué)知識(shí)匱乏所帶來(lái)的困頓。同時(shí)因?yàn)樽约旱臄?shù)學(xué)思維實(shí)在是不怎么好，所以決定努力補(bǔ)習(xí)數(shù)學(xué)與計(jì)算機(jī)基礎(chǔ)知識(shí)。

當(dāng)時(shí)也有人說(shuō):"前端需要什么數(shù)據(jù)結(jié)構(gòu)與算法"，但是對(duì)于這個(gè)事情我有自己的看法。

我并不認(rèn)為前端不需要算法之類的知識(shí)，在我看來(lái)前端具備堅(jiān)實(shí)的計(jì)算機(jī)基礎(chǔ)，對(duì)自身發(fā)展是極其有利的。我想做程序員。而不是一輩子的初級(jí)前端和碼農(nóng)。

也算是給自己的勉勵(lì)吧。畢竟基礎(chǔ)決定上限，再加上自己對(duì)計(jì)算機(jī)真的很感興趣，所以學(xué)起來(lái)就算很累，但也是很幸福的。于是去網(wǎng)上選購(gòu)了《學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法》這本書(shū)，配合著去圖書(shū)館借閱的《大話數(shù)據(jù)結(jié)構(gòu)》，開(kāi)始了數(shù)據(jù)結(jié)構(gòu)與算法的初步學(xué)習(xí)。

這本書(shū)講的內(nèi)容很是不錯(cuò)，清晰易懂。同時(shí)用JavaScipt語(yǔ)言實(shí)現(xiàn)，學(xué)起來(lái)的難度低。值得一看呢。

書(shū)中前兩章是對(duì)JavaScipt基礎(chǔ)與數(shù)組常用操作的講解，如果不清楚的話,推薦去看看下面這篇博客。

JavaScipt之?dāng)?shù)組操作

接下來(lái)就是數(shù)據(jù)結(jié)構(gòu)的第一部分，棧。

棧是一種遵從后進(jìn)先出原則(LIFO,全稱為L(zhǎng)ast In First Out)的有序集合。棧頂永遠(yuǎn)是最新的元素。
舉個(gè)例子就是:棧就像放在箱子里的一疊書(shū) 你要拿下面的書(shū)先要把上面的書(shū)拿開(kāi)。(當(dāng)然，你不能先拿下面的書(shū)。)
看圖示也可明白。

首先，創(chuàng)建一個(gè)構(gòu)造函數(shù)。

/**
 * 棧的構(gòu)造函數(shù)
 */
function Stack() {

  // 用數(shù)組來(lái)模擬棧
  var item = [];
}

棧需要有如下的方法:

push(element(s)): 添加幾個(gè)元素到棧頂

pop(): 移除并返回棧頂元素

peek(): 返回棧頂元素

isAmpty: 檢查棧是否為空，為空則返回true

clear: 移除棧中所有元素

size: 返回棧中元素個(gè)數(shù)。

print: 以字符串顯示棧中所有內(nèi)容

說(shuō)明: 需要往棧中添加新元素，元素位置在隊(duì)列的末尾。也就是說(shuō)，我們可以用數(shù)組的push方法來(lái)模擬實(shí)現(xiàn)。
實(shí)現(xiàn):

/**
 * 將元素送入棧，放置于數(shù)組的最后一位
 * @param  {Any} element 接受的元素，不限制類型
 */
this.push = function(element) {
  items.push(element);
};

說(shuō)明: 需要把棧頂元素彈出，同時(shí)返回被彈出的值。可以用數(shù)組的pop方法來(lái)模擬實(shí)現(xiàn)。
實(shí)現(xiàn):

/**
 * 彈出棧頂元素
 * @return {Any} 返回被彈出的值
 */
this.pop = function() {
  return items.pop();
};

說(shuō)明: 查看棧頂元素，可以用數(shù)組長(zhǎng)度來(lái)實(shí)現(xiàn)。
實(shí)現(xiàn):

/**
 * 查看棧頂元素
 * @return {Any} 返回棧頂元素
 */
this.peek = function() {
  return items[items.length - 1];
}

說(shuō)明: 前三個(gè)是棧方法的核心，其余方法則在此一次性列出。因?yàn)橄挛囊v的隊(duì)列，會(huì)與這部分有很大重合。
實(shí)現(xiàn):

/**
 * 確定棧是否為空
 * @return {Boolean} 若棧為空則返回true,不為空則返回false
 */
this.isAmpty = function() {
  return items.length === 0
};

/**
 * 清空棧中所有內(nèi)容
 */
this.clear = function() {
  items = [];
};

/**
 * 返回棧的長(zhǎng)度
 * @return {Number} 棧的長(zhǎng)度
 */
this.size = function() {
  return items.length;
};

/**
 * 以字符串顯示棧中所有內(nèi)容
 */
this.print = function() {
  console.log(items.toString());
};

棧的實(shí)際應(yīng)用比較多，書(shū)中有個(gè)十進(jìn)制轉(zhuǎn)二進(jìn)制的函數(shù)。(不懂二進(jìn)制怎么算的話可以百度)下面是函數(shù)的源代碼。
原理就是輸入要轉(zhuǎn)換的數(shù)字，不斷的除以二并取整。并且最后運(yùn)用while循環(huán)，將棧中所有數(shù)字拼接成字符串輸出。

/**
 * 將10進(jìn)制數(shù)字轉(zhuǎn)為2進(jìn)制數(shù)字
 * @param  {Number} decNumber 要轉(zhuǎn)換的10進(jìn)制數(shù)字
 * @return {Number}           轉(zhuǎn)換后的2進(jìn)制數(shù)字
 */
function divideBy2(decNumber) {

  var remStack = new Stack(),
    rem,
    binaryString = "";

  while (decNumber > 0) {
    rem = Math.floor(decNumber % 2);
    remStack.push(rem);
    decNumber = Math.floor(decNumber / 2);
  }

  while (!remStack.isAmpty()) {
    binaryString += remStack.pop().toString();
  }

  return binaryString;
};

到此而言，棧的學(xué)習(xí)就告一段落了。因?yàn)樵创a中注釋較多，所以這兒就不貼出源代碼的內(nèi)容了。有興趣的可以自己下載查看。

源代碼

隊(duì)列與棧是很相像的數(shù)據(jù)結(jié)構(gòu)，不同之處在于隊(duì)列是是先進(jìn)先出(FIFO:First In First Out)的。
舉個(gè)例子: 火車站排隊(duì)買票，先到的先買。(插隊(duì)的不算)，是不是很好理解了~

隊(duì)列的實(shí)現(xiàn)和棧很像。首先依然是構(gòu)造函數(shù):

/**
 * 隊(duì)列構(gòu)造函數(shù)
 */
function Queue() {
  var items = [];
}

隊(duì)列需要有如下的方法:

enqueue(element(s)): 向隊(duì)列尾部添加幾個(gè)項(xiàng)

dequeue(): 移除隊(duì)列的第一項(xiàng)(也就是排在最前面的項(xiàng))

front(): 返回隊(duì)列的第一個(gè)元素，也就是最新添加的那個(gè)

其余方法與隊(duì)列相同

說(shuō)明: 向隊(duì)列尾部添加幾個(gè)項(xiàng)。
實(shí)現(xiàn):

/**
 * 將元素推入隊(duì)列尾部
 * @param  {Any} ele 要推入隊(duì)列的元素
 */
this.enqueue = function(ele) {
  items.push(ele);
};

說(shuō)明: 移除隊(duì)列的第一項(xiàng)。
實(shí)現(xiàn):

/**
 * 將隊(duì)列中第一個(gè)元素彈出
 * @return {Any} 返回被彈出的元素
 */
this.dequeue = function() {
  return items.shift()
};

說(shuō)明: 返回隊(duì)列的第一個(gè)元素，也就是最新添加的那個(gè)。
實(shí)現(xiàn):

/**
 * 查看隊(duì)列的第一個(gè)元素
 * @return {Any} 返回隊(duì)列中第一個(gè)元素
 */
this.front = function() {
  return items[0];
};

以上的三個(gè)方法，就是隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)的核心方法了。其實(shí)很好理解的。

書(shū)上的是個(gè)擊鼓傳花的小游戲。原理就是循環(huán)到相應(yīng)位置時(shí)，隊(duì)列彈出那個(gè)元素。最后留下的就是贏家。
源代碼如下:

/**
 * 擊鼓傳花的小游戲
 * @param  {Array}  nameList 參與人員列表
 * @param  {Number} num      在循環(huán)中要被彈出的位置
 * @return {String}          返回贏家(也就是最后活下來(lái)的那個(gè))
 */
function hotPotato(nameList, num) {
  var queue = new Queue();

  for (var i = 0; i < nameList.length; i++) {
    queue.enqueue(nameList[i]);
  }

  var eliminated = "";

  while (queue.size() > 1) {
    for (var i = 0; i < num; i++) {
      queue.enqueue(queue.dequeue());
    }

    eliminated = queue.dequeue();
    console.log(eliminated + " Get out!")
  }

  return queue.dequeue()
}

具體實(shí)現(xiàn)，有興趣的同學(xué)可以自己下載源代碼，試一試。

源代碼

隊(duì)列的學(xué)習(xí)到此就告一段落了。下一期將講述另外一種數(shù)據(jù)結(jié)構(gòu): 鏈表。

很多時(shí)候看書(shū)，直接看算法導(dǎo)論或者一些數(shù)據(jù)結(jié)構(gòu)的書(shū)，都是很迷糊的。后來(lái)才發(fā)現(xiàn)，看書(shū)從自己能看懂的開(kāi)始，由淺入深才是適合自己的學(xué)習(xí)方式。

前端路漫漫，且行且歌~

最后附上本人博客地址和原文鏈接，希望能與各位多多交流。

Lxxyx的前端樂(lè)園
原文鏈接：寒假前端學(xué)習(xí)(3)——學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法，棧與隊(duì)列