學(xué)習(xí)起因

曾經(jīng)有一次在逛V2EX時，碰到這么一個帖子。
數(shù)學(xué)完全還給老師了，想學(xué)回一些基礎(chǔ)數(shù)學(xué)，大概是高中程度的，有什么書籍推薦？
發(fā)帖的樓主大學(xué)沒有高數(shù)課程，出去工作時一直在從事前端的工作。感覺到數(shù)學(xué)知識的匱乏，所以想補一補數(shù)學(xué)。
看了看帖子，感覺和我很像，因為我的專業(yè)是不開高數(shù)的，我學(xué)的也是前端。也同樣感覺到了數(shù)學(xué)知識匱乏所帶來的困頓。同時因為自己的數(shù)學(xué)思維實在是不怎么好，所以決定努力補習(xí)數(shù)學(xué)與計算機(jī)基礎(chǔ)知識。
當(dāng)時也有人說:”前端需要什么數(shù)據(jù)結(jié)構(gòu)與算法”，但是對于這個事情我有自己的看法。
我并不認(rèn)為前端不需要算法之類的知識，在我看來前端具備堅實的計算機(jī)基礎(chǔ)，對自身發(fā)展是極其有利的。我想做程序員。而不是一輩子的初級前端和碼農(nóng)。
也算是給自己的勉勵吧。畢竟基礎(chǔ)決定上限，再加上自己對計算機(jī)真的很感興趣，所以學(xué)起來就算很累，但也是很幸福的。于是去網(wǎng)上選購了《學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法》這本書，配合著去圖書館借閱的《大話數(shù)據(jù)結(jié)構(gòu)》，開始了數(shù)據(jù)結(jié)構(gòu)與算法的初步學(xué)習(xí)。

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

接下來就是數(shù)據(jù)結(jié)構(gòu)的第一部分，棧。
棧是一種遵從后進(jìn)先出原則(LIFO,全稱為Last In First Out)的有序集合。棧頂永遠(yuǎn)是最新的元素。
舉個例子就是:棧就像放在箱子里的一疊書 你要拿下面的書先要把上面的書拿開。(當(dāng)然，你不能先拿下面的書。)

JavaScipt中棧的實現(xiàn)
首先，創(chuàng)建一個構(gòu)造函數(shù)。

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

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

棧需要有如下的方法:
push(element(s)): 添加幾個元素到棧頂
pop(): 移除并返回棧頂元素
peek(): 返回棧頂元素
isAmpty: 檢查棧是否為空，為空則返回true
clear: 移除棧中所有元素
size: 返回棧中元素個數(shù)。
print: 以字符串顯示棧中所有內(nèi)容
push方法的實現(xiàn)
說明: 需要往棧中添加新元素，元素位置在隊列的末尾。也就是說，我們可以用數(shù)組的push方法來模擬實現(xiàn)。

實現(xiàn):

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

pop方法的實現(xiàn)

說明: 需要把棧頂元素彈出，同時返回被彈出的值?？梢杂脭?shù)組的pop方法來模擬實現(xiàn)。
實現(xiàn):

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

peek方法的實現(xiàn)
說明: 查看棧頂元素，可以用數(shù)組長度來實現(xiàn)。
實現(xiàn):

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

其余方法的實現(xiàn)
說明: 前三個是棧方法的核心，其余方法則在此一次性列出。因為下文要講的隊列，會與這部分有很大重合。
實現(xiàn):

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

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

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

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

實際應(yīng)用

棧的實際應(yīng)用比較多，書中有個十進(jìn)制轉(zhuǎn)二進(jìn)制的函數(shù)。(不懂二進(jìn)制怎么算的話可以百度)下面是函數(shù)的源代碼。
原理就是輸入要轉(zhuǎn)換的數(shù)字，不斷的除以二并取整。并且最后運用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í)就告一段落了。因為源代碼中注釋較多，所以這兒就不貼出源代碼的內(nèi)容了。

隊列

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

JavaScipt中隊列的實現(xiàn)

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

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

隊列需要有如下的方法:
enqueue(element(s)): 向隊列尾部添加幾個項
dequeue(): 移除隊列的第一項(也就是排在最前面的項)
front(): 返回隊列的第一個元素，也就是最新添加的那個
其余方法與隊列相同

enqueue方法的實現(xiàn)

說明: 向隊列尾部添加幾個項。
實現(xiàn):

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

dequeue方法的實現(xiàn)

說明: 移除隊列的第一項。
實現(xiàn):

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

front方法的實現(xiàn)

說明: 返回隊列的第一個元素，也就是最新添加的那個。
實現(xiàn):

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

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

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

/**
 * 擊鼓傳花的小游戲
 * @param {Array} nameList 參與人員列表
 * @param {Number} num   在循環(huán)中要被彈出的位置
 * @return {String}     返回贏家(也就是最后活下來的那個)
 */
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()
}

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

感想

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

最新評論