寒假前端學習(3) - 學習JavaScript數據結構與算法，棧與隊列
曾經有一次在逛V2EX時，碰到這么一個帖子。
發帖的樓主大學沒有高數課程，出去工作時一直在從事前端的工作。感覺到數學知識的匱乏，所以想補一補數學。看了看帖子，感覺和我很像，因為我的專業是不開高數的，我學的也是前端。也同樣感覺到了數學知識匱乏所帶來的困頓。同時因為自己的數學思維實在是不怎么好，所以決定努力補習數學與計算機基礎知識。
當時也有人說:”前端需要什么數據結構與算法”，但是對于這個事情我有自己的看法。
我并不認為前端不需要算法之類的知識，在我看來前端具備堅實的計算機基礎，對自身發展是極其有利的。我想做程序員。而不是一輩子的初級前端和碼農。
也算是給自己的勉勵吧。畢竟基礎決定上限，再加上自己對計算機真的很感興趣，所以學起來就算很累，但也是很幸福的。于是去網上選購了《學習JavaScript數據結構與算法》這本書，配合著去圖書館借閱的《大話數據結構》，開始了數據結構與算法的初步學習。
這本書講的內容很是不錯，清晰易懂。同時用JavaScipt語言實現，學起來的難度低。值得一看呢。
棧
書中前兩章是對JavaScipt基礎與數組常用操作的講解，如果不清楚的話,推薦去看看下面這篇博客。
接下來就是數據結構的第一部分，棧。
棧是一種遵從后進先出原則(LIFO,全稱為Last In First Out)的有序集合。棧頂永遠是最新的元素。
舉個例子就是:棧就像放在箱子里的一疊書 你要拿下面的書先要把上面的書拿開。(當然，你不能先拿下面的書。)
看圖示也可明白。
JavaScipt中棧的實現
首先，創建一個構造函數。
/**
* 棧的構造函數
*/
function Stack() {
// 用數組來模擬棧
var item = [];
}棧需要有如下的方法:
- push(element(s)): 添加幾個元素到棧頂
- pop(): 移除并返回棧頂元素
- peek(): 返回棧頂元素
- isAmpty: 檢查棧是否為空，為空則返回true
- clear: 移除棧中所有元素
- size: 返回棧中元素個數。
- print: 以字符串顯示棧中所有內容
push方法的實現
說明: 需要往棧中添加新元素，元素位置在隊列的末尾。也就是說，我們可以用數組的push方法來模擬實現。
實現:
/**
* 將元素送入棧，放置于數組的最后一位
* @param {Any} element 接受的元素，不限制類型
*/
this.push = function(element) {
items.push(element);
};pop方法的實現
說明: 需要把棧頂元素彈出，同時返回被彈出的值。可以用數組的pop方法來模擬實現。
實現:
/**
* 彈出棧頂元素
* @return {Any} 返回被彈出的值
*/
this.pop = function() {
return items.pop();
};peek方法的實現
說明: 查看棧頂元素，可以用數組長度來實現。
實現:
/**
* 查看棧頂元素
* @return {Any} 返回棧頂元素
*/
this.peek = function() {
return items[items.length - 1];
}其余方法的實現
說明: 前三個是棧方法的核心，其余方法則在此一次性列出。因為下文要講的隊列，會與這部分有很大重合。
實現:
/**
* 確定棧是否為空
* @return {Boolean} 若棧為空則返回true,不為空則返回false
*/
this.isAmpty = function() {
return items.length === 0
};
/**
* 清空棧中所有內容
*/
this.clear = function() {
items = [];
};
/**
* 返回棧的長度
* @return {Number} 棧的長度
*/
this.size = function() {
return items.length;
};
/**
* 以字符串顯示棧中所有內容
*/
this.print = function() {
console.log(items.toString());
};實際應用
棧的實際應用比較多，書中有個十進制轉二進制的函數。(不懂二進制怎么算的話可以百度)下面是函數的源代碼。
原理就是輸入要轉換的數字，不斷的除以二并取整。并且最后運用while循環，將棧中所有數字拼接成字符串輸出。
/**
* 將10進制數字轉為2進制數字
* @param {Number} decNumber 要轉換的10進制數字
* @return {Number} 轉換后的2進制數字
*/
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;
};到此而言，棧的學習就告一段落了。因為源代碼中注釋較多，所以這兒就不貼出源代碼的內容了。有興趣的可以自己下載查看。
隊列
隊列與棧是很相像的數據結構，不同之處在于隊列是是先進先出(FIFO:First In First Out)的。舉個例子: 火車站排隊買票，先到的先買。(插隊的不算)，是不是很好理解了~
JavaScipt中隊列的實現
隊列的實現和棧很像。首先依然是構造函數:
/**
* 隊列構造函數
*/
function Queue() {
var items = [];
}隊列需要有如下的方法:
- enqueue(element(s)): 向隊列尾部添加幾個項
- dequeue(): 移除隊列的第一項(也就是排在最前面的項)
- front(): 返回隊列的第一個元素，也就是最新添加的那個
其余方法與隊列相同
enqueue方法的實現
說明: 向隊列尾部添加幾個項。
實現:
/**
* 將元素推入隊列尾部
* @param {Any} ele 要推入隊列的元素
*/
this.enqueue = function(ele) {
items.push(ele);
};dequeue方法的實現
說明: 移除隊列的第一項。
實現:
/**
* 將隊列中第一個元素彈出
* @return {Any} 返回被彈出的元素
*/
this.dequeue = function() {
return items.shift()
};front方法的實現
說明: 返回隊列的第一個元素，也就是最新添加的那個。
實現:
/**
* 查看隊列的第一個元素
* @return {Any} 返回隊列中第一個元素
*/
this.front = function() {
return items[0];
};以上的三個方法，就是隊列這種數據結構的核心方法了。其實很好理解的。
實際應用
書上的是個擊鼓傳花的小游戲。原理就是循環到相應位置時，隊列彈出那個元素。最后留下的就是贏家。
源代碼如下:
/**
* 擊鼓傳花的小游戲
* @param {Array} nameList 參與人員列表
* @param {Number} num 在循環中要被彈出的位置
* @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()
}具體實現，有興趣的同學可以自己下載源代碼，試一試。
隊列的學習到此就告一段落了。下一期將講述另外一種數據結構: 鏈表。
感想
很多時候看書，直接看算法導論或者一些數據結構的書，都是很迷糊的。后來才發現，看書從自己能看懂的開始，由淺入深才是適合自己的學習方式。
前端路漫漫，且行且歌~
來自： http://www.lxxyx.win/2016/01/14/寒假前端學習-3-JavaScript實現棧與隊列/