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依次递减并压入栈中，随后再次利用while循环，依据栈后进先出的原则，通过pop方法依次取出栈顶元素并与product变量相乘叠加，最终得到结果。