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

曾經(jīng)有一次在逛V2EX時(shí)，碰到這么一個(gè)帖子。
數(shù)學(xué)完全還給老師了，想學(xué)回一些基礎(chǔ)數(shù)學(xué)，大概是高中程度的，有什么書籍推薦？
發(fā)帖的樓主大學(xué)沒有高數(shù)課程，出去工作時(shí)一直在從事前端的工作。感覺到數(shù)學(xué)知識(shí)的匱乏，所以想補(bǔ)一補(bǔ)數(shù)學(xué)。
看了看帖子，感覺和我很像，因?yàn)槲业膶I(yè)是不開高數(shù)的，我學(xué)的也是前端。也同樣感覺到了數(shù)學(xué)知識(shí)匱乏所帶來的困頓。同時(shí)因?yàn)樽约旱臄?shù)學(xué)思維實(shí)在是不怎么好，所以決定努力補(bǔ)習(xí)數(shù)學(xué)與計(jì)算機(jī)基礎(chǔ)知識(shí)。
當(dāng)時(shí)也有人說:”前端需要什么數(shù)據(jù)結(jié)構(gòu)與算法”，但是對(duì)于這個(gè)事情我有自己的看法。
我并不認(rèn)為前端不需要算法之類的知識(shí)，在我看來前端具備堅(jiān)實(shí)的計(jì)算機(jī)基礎(chǔ)，對(duì)自身發(fā)展是極其有利的。我想做程序員。而不是一輩子的初級(jí)前端和碼農(nóng)。
也算是給自己的勉勵(lì)吧。畢竟基礎(chǔ)決定上限，再加上自己對(duì)計(jì)算機(jī)真的很感興趣，所以學(xué)起來就算很累，但也是很幸福的。于是去網(wǎng)上選購(gòu)了《學(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,全稱為L(zhǎng)ast In First Out)的有序集合。棧頂永遠(yuǎn)是最新的元素。
舉個(gè)例子就是:棧就像放在箱子里的一疊書 你要拿下面的書先要把上面的書拿開。(當(dāng)然，你不能先拿下面的書。)

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

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

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

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

實(shí)現(xiàn):

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

pop方法的實(shí)現(xiàn)

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

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

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

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

其余方法的實(shí)現(xiàn)
說明: 前三個(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í)際應(yīng)用比較多，書中有個(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ì)列

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

JavaScipt中隊(duì)列的實(shí)現(xiàn)

隊(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ì)列相同

enqueue方法的實(shí)現(xiàn)

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

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

dequeue方法的實(shí)現(xiàn)

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

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

front方法的實(shí)現(xiàn)

說明: 返回隊(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í)際應(yīng)用
書上的是個(gè)擊鼓傳花的小游戲。原理就是循環(huán)到相應(yīng)位置時(shí)，隊(duì)列彈出那個(gè)元素。最后留下的就是贏家。
源代碼如下:

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

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

感想

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

最新評(píng)論