JavaScript資料結構與演算法之棧與佇列_基礎知識

學起因

曾經有一次在逛V2EX時，碰到這麼一個貼文。
數學完全還給老師了，想學回一些基礎數學，大概是高中程度的，有什麼書籍推薦？
發文的樓主大學沒有高數課程，出去工作時一直在從事前端的工作。感覺到數學知識的匱乏，所以想補一補數學。
看了看帖子，感覺跟我很像，因為我的專業是不開高數的，我學的也是前端。也同樣感覺到了數學知識匱乏所帶來的困頓。同時因為自己的數學思維實在是不怎麼好，所以決定努力補習數學與電腦基礎。
當時也有人說:”前端需要什麼資料結構與演算法”，但是對於這個事情我有自己的看法。
我並不認為前端不需要演算法之類的知識，在我看來前端具備堅實的電腦基礎，對自身發展是極為有利的。我想做程式設計師。而不是一輩子的初級前端和碼農。
也算是給自己的勉勵吧。畢竟基礎決定上限，再加上自己對計算機真的很有興趣，所以學起來就算很累，但也是很幸福的。於是上網選購了《學習JavaScript資料結構與演算法》這本書，配合到圖書館借閱的《大話資料結構》，開始了資料結構與演算法的初步學習。

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()
}

队列的学习到此就告一段落了。下一期将讲述另外一种数据结构: 链表。

感想

很多时候看书，直接看算法导论或者一些数据结构的书，都是很迷糊的。后来才发现，看书从自己能看懂的开始，由浅入深才是适合自己的学习方式。