详细讲解JavaScript数据结构和算法栈

在上一篇博客中，我介绍了以下列表，这是最简单的结构。然而，如果我们想处理一些复杂的结构，列表太简单了，所以我们需要一个类似于列表但更复杂的数据结构——堆栈。堆栈是一种高效的数据结构，因为数据只能在堆栈顶部添加或删除，所以这个操作快速且易于实现。

1.堆栈上的操作。

栈是一个特殊的列表，栈中的元素只能通过列表的一端访问，即栈顶。比如在餐厅洗碗，只能先洗顶板。洗碗后，你只能拧到盘子堆的顶部。堆栈是一种称为后进先出的数据结构。

因为堆栈具有后进先出的特性，所以不在堆栈顶部的任何元素都无法访问。为了获得低堆叠的元素，必须首先移除上面的元素。我们可以对堆栈执行的两个主要操作是将一个元素推入堆栈和将一个元素弹出堆栈。我们可以在堆栈中使用push()方法，在堆栈中使用pop()方法。虽然pop()方法可以访问堆栈顶部的元素，但调用此方法后，堆栈顶部的元素将从堆栈中永久删除。另一个常用的方法是peek()，它只返回堆栈的顶部元素，但不删除它。

栈入口和栈出口的实际列图如下：

Push()、pop()和peek()是stack的三种主要方法，但是stack还有其他方法和属性。如下所示：

Clear():清除堆栈中的所有元素。

Length():记录堆栈中的元素数量。

其次，堆栈实现如下：

我们可以从实现堆栈类的方法开始。以下是复制代码： function stack(){ this . datastore=[]；this . top=0；}

如上：dataStore是保存堆栈中的所有元素。变量top记录堆栈顶部的位置，该位置被初始化为0。这意味着，如果有任何元素被推入堆栈，则对应于堆栈顶部的数组的起始位置为0。变量值将相应改变。

我们还有以下方法：push()、pop()、peek()、clear()、length()；

1.push()方法；当一个新元素被压入堆栈时，需要保存在数组中变量top对应的位置，然后top值增加1指向数组中的下一个位置。以下代码：复制代码如下：函数push(element){ this . datastore[this . top]=element；} 2.pop()方法与push()方法相反——它返回堆栈的顶部元素，并将顶部值减少1。以下代码：复制代码如下： Function pop(){ Return this . datastore[-this . top]；} 3.peek()方法返回数组top-1位置的元素，即堆栈的顶部元素；复制代码如下：函数peek(){ return this . datastore[this . top-1]；}4.length()方法有时我们需要知道堆栈中有多少元素。我们可以通过返回变量的顶值来返回堆栈中的元素数量，如下所示：复制代码如下： Function length(){ Return this。顶部；}5.clear()；有时候我们想清空栈，我们把变量顶值设置为0；以下代码：复制代码如下：函数clear() {。

this . top=0；

}以下所有代码：复制代码如下： function stack(){ this . datastore=[]；this . top=0；}

Stack.prototype={//将新元素推入堆栈，Push : function(element){ this . datastore[this . top]=element；}，//访问栈顶元素，已被永久删除。POP:函数(){ return this . datastore[-this . top]；}，//返回数组中的top-1元素，即top元素peek : function(){ return this . datastore[this . top-1]；}，//堆栈中存储了多少个元素length : function(){ returnthis . top；}，//清除堆栈clear : function(){ this . top=0；}};

演示示例如下：

var Stack=new Stack()；stack . push(' a ')；stack . push(' b ')；stack . push(' c ')；console . log(stack . length())；//3 con sole . log(stack . peek())；//c

var popd=stack . pop()；console.log(已弹出)；//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())；//未定义

我们可以在下面实现阶乘函数的递归定义。比如5！阶乘5！=5 * 4 * 3 * 2 * 1;

代码：复制代码如下：函数fact(n){ var s=newstack()；while(n1){ s . push(n-)；} var乘积=1；while(s . length)(0){ product *=s . pop()；}退回产品；} console . log(fact(5))；

以上代码的意思是：先把数字5传入函数，使用while循环，按自己栈的函数push()进入栈，直到变量n小于1。然后定义一个变量乘积；判断是否大于0，每次用栈长()的方法执行乘积*=s . pop()；pop()方法返回堆栈的顶部元素，并将其从堆栈中删除。因此，每次执行时，都会删除一个元素，直到s.length()=0。因此，乘积=5*4*3*2*1。