這篇文章主要介紹了JavaScript中數據結構與算法(一)：棧,本文講解了棧的結構、什麼是回文以及遞歸等內容,講解的不錯,通俗易懂,需要的朋友可以參考下
序
數據結構與算法JavaScript這本書算是講解得比較淺顯的，優點就是用javascript語言把常用的數據結構給描述了下，書中很多例子來源於常見的一些面試題目，算是與時俱進，業余看了下就順便記錄下來吧
git代碼下載：https://github.com/JsAaron/data_structure.git
棧結構
特殊的列表，棧內的元素只能通過列表的一端訪問，棧頂
後入先出(LIFO,last-in-first-out)的數據結構
javascript提供可操作的方法, 入棧 push, 出棧 pop，但是pop會移掉棧中的數據
實現一個棧的實現類
底層存數數據結構采用 數組
因為pop是刪除棧中數據，所以需要實現一個查找方法 peek
實現一個清理方法 clear
棧內元素總量查找 length
查找是否還存在元素 empty
代碼如下:
function Stack(){
this.dataStore = []
this.top = 0;
this.push = push
this.pop = pop
this.peek = peek
this.length = length;
}
function push(element){
this.dataStore[this.top++] = element;
}
function peek(element){
return this.dataStore[this.top-1];
}
function pop(){
return this.dataStore[--this.top];
}
function clear(){
this.top = 0
}
function length(){
return this.top
}
回文
回文就是指一個單詞，數組，短語，從前往後從後往前都是一樣的 12321.abcba
回文最簡單的思路就是, 把元素反轉後如果與原始的元素相等，那麼就意味著這就是一個回文了
這裡可以用到這個棧類來操作
代碼如下:
function isPalindrome(word) {
var s = new Stack()
for (var i = 0; i < word.length; i++) {
s.push(word[i])
}
var rword = "";
while (s.length() > 0) {
rword += s.pop();
}
if (word == rword) {
return true;
} else {
return false;
}
}
isPalindrome("aarra") //false
isPalindrome("aaraa") //true
看看這個isPalindrome函數，其實就是通過調用Stack類，然後把傳遞進來的word這個元素給分解後的每一個組成單元給壓入到棧了，根據棧的原理，後入先出的原則，通過pop的方法在反組裝這個元素，最後比較下之前與組裝後的，如果相等就是回文了
遞歸
用遞歸實現一個階乘算法
5! = 5 * 4 * 3 * 2 * 1 = 120
用遞歸
代碼如下:
function factorial(n) {
if (n === 0) {
return 1;
} else {
return n * factorial(n - 1);
}
}
用棧操作
代碼如下:
function fact(n) {
var s = new Stack()
while (n > 1) {
//[5,4,3,2]
s.push(n--);
}
var product = 1;
while (s.length() > 0) {
product *= s.pop();
}
return product;
}
fact(5) //120
通過while把n = 5 遞減壓入棧，然後再通過一個循環還是根據棧的後入先出的原則，通過pop方法把最前面的取出來與product疊加