曾經在逛論壇時看到一個帖子:數學完全還給老師了,想學回一些基礎數學,有什麼書籍推薦?發帖的樓主大學沒有高數課程,一直從事前端工作,感覺到知識的匱乏。看著這個帖子,我感覺和自己很像——我的專業不開高數,學的也是前端,也同樣感受到數學知識匱乏所帶來的困頓。當時也有人說「前端需要什麼資料結構與算法」,但我並不這麼認為。在我看來,前端具備扎實的計算機基礎,對自身發展極為有利。於是開始了資料結構與算法的初步學習。
接下來是資料結構的第一部分:棧。棧是一種遵從「後進先出」(LIFO,Last In First Out)原則的有序集合,棧頂永遠是最新的元素。舉個例子:棧就像放在箱子裡的一疊書,你要拿下面的書,得先把上面的書拿開。
首先建立構造函式,用陣列來模擬棧:
function Stack() {
var item = [];
}
棧需要具備 push、pop、peek、isEmpty、clear、size、print 等方法。
push 方法:往棧中添加新元素,位置在陣列末尾,可用陣列的 push 模擬:
this.push = function(element) {
items.push(element);
};
pop 方法:把棧頂元素彈出並返回:
this.pop = function() {
return items.pop();
};
peek 方法:查看棧頂元素,可用陣列長度實現:
this.peek = function() {
return items[items.length - 1];
}
其餘方法:
this.isAmpty = function() {
return items.length === 0;
};
this.clear = function() {
items = [];
};
this.size = function() {
return items.length;
};
this.print = function() {
console.log(items.toString());
};
實際應用:書中有個十進位轉二進位的函式,原理是輸入要轉換的數字,不斷除以二並取整,最後用 while 循環把棧中所有數字拼接成字串輸出。
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)的。舉個例子:火車站排隊買票,先到的先買(插隊的不算)。
首先建立構造函式:
function Queue() {
var items = [];
}
enqueue 方法:向佇列尾部添加元素:
this.enqueue = function(ele) {
items.push(ele);
};
dequeue 方法:移除佇列的第一項:
this.dequeue = function() {
return items.shift();
};
front 方法:返回佇列的第一個元素:
this.front = function() {
return items[0];
};
實際應用:書上是個「擊鼓傳花」的小遊戲,原理是循環到相應位置時把該元素彈出,最後留下的就是贏家:
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()
}
很多時候直接看算法導論或資料結構的書都會很迷糊,後來才發現,從自己能看懂的開始、由淺入深,才是適合自己的學習方式。