JavaScript栈数据结构详解：原理、实现与阶乘应用

栈的基本概念与操作

前文已介绍列表，作为最基础的数据结构，其功能较为单一。面对更复杂的应用场景，列表显得力不从心，因此需要引入一种类似列表但功能更强大的数据结构——栈。栈是一种高效的数据结构，其特点是数据只能在栈顶进行添加或删除操作，这种机制使得操作速度极快且易于实现。

一：栈的基本操作。

栈是一种特殊的列表，其元素仅能通过列表的一端进行访问，该端被称为栈顶。以餐馆洗盘子为例，清洗时只能处理最上面的盘子，洗净后的盘子也只能叠放在这一摞盘子的最上方。栈因此被称为“后入先出”（LIFO）的数据结构。

由于栈具备后入先出的特性，非栈顶的元素无法直接访问。若要获取栈底的元素，必须先移除其上方的所有元素。栈的两种核心操作为“入栈”和“出栈”。入栈通过 push() 方法实现，出栈通过 pop() 方法实现。pop() 方法不仅能访问栈顶元素，还会将其从栈中永久移除。另一个常用方法是 peek()，它仅返回栈顶元素而不执行删除操作。

入栈与出栈的示例图示如下：

push()、pop() 和 peek() 是栈的三个主要方法，但栈还包含其他方法和属性，具体如下：

clear()：用于清除栈内的所有元素。

length()：用于记录栈内元素的个数。

栈的JavaScript实现

二：栈的具体实现如下：

我们可以从实现栈类的方法开始，具体步骤如下：

function Stack() {
this.dataStore = [];
this.top = 0;
  }
 

如上所示，dataStore 用于保存栈内的所有元素。变量 top 用于记录栈顶的位置，初始值设为 0，表示栈顶对应数组的起始索引。当有元素被压入栈时，该变量的值会随之更新。

我们还定义了以下方法：push()、pop()、peek()、clear() 和 length()；

1. push() 方法：当向栈内压入新元素时，需将其保存在数组中变量 top 所对应的位置，随后将 top 值加 1，使其指向数组中的下一个位置。代码如下：

function push(element) {
this.dataStore[this.top++] = element;
}

2. pop() 方法与 push() 方法相反，它返回栈顶元素，同时将 top 值减 1。代码如下：

function pop(){
return this.dataStore[--this.top];
   }

3. peek() 方法返回数组中第 top-1 个位置的元素，即栈顶元素；

function peek(){
return this.dataStore[this.top - 1];
    }

4. length() 方法：有时我们需要知道栈内元素的数量，可以通过返回变量 top 的值来实现，代码如下：

function length(){
return this.top;
     }

5. clear()：有时需要清空栈，我们将变量 top 的值设为 0；代码如下：

function clear() {
this.top = 0;
    }

以下是所有代码的汇总：

function Stack() {
this.dataStore = [];
this.top = 0;
}
Stack.prototype = {
 
 // 向栈中压入一个新元素
 push: function(element) {
 this.dataStore[this.top++] = element;
 },
 // 访问栈顶元素，栈顶元素永久的被删除了
 pop: function(){
 return this.dataStore[--this.top];
 },
 // 返回数组中的 top-1 个位置的元素，即栈顶元素
 peek: function(){
 return this.dataStore[this.top - 1];
 },
 // 栈内存储了多少个元素
 length: function(){
 return this.top;
 },
 // 清空栈
 clear: function(){
 this.top = 0;
 }
};
Demo 实例如下：
var stack = new Stack();
stack.push("a");
stack.push("b");
stack.push("c");
console.log(stack.length()); // 3
console.log(stack.peek()); // c
var popped = stack.pop();
console.log(popped); // c
console.log(stack.peek()); // b
stack.push("d");
console.log(stack.peek()); // d
stack.clear();
console.log(stack.length()); // 0
console.log(stack.peek()); // undefined

栈在阶乘计算中的应用

接下来我们可以实现一个基于栈的阶乘函数递归定义；例如 5 的阶乘，即 5！= 5 * 4 * 3 * 2 * 1；

代码如下：

function fact(n) {
var s = new Stack();
while(n > 1) {
s.push(n--);
    }
var product = 1;
while(s.length() > 0) {
product *= s.pop();
    }
return product;
}
console.log(fact(5));

上述代码的含义是：首先将数字 5 传入函数，使用 while 循环，在每次自减 1 之前，利用栈的 push() 方法将当前值压入栈内，直到变量 n 小于或等于 1 为止。随后定义变量 product；通过栈的 length() 方法判断栈是否为空，每次执行 product *= s.pop()；pop() 方法返回栈顶元素并将其从栈中移除。因此，每次执行都会删除一个元素，直到 s.length() <= 0 为止。最终 product = 5*4*3*2*1 的计算结果。