在JavaScript中的栈数据结构（Stack ）

2023-06-26 17:31:07 浏览数 (1)

导文

JavaScript 中可以通过数组实现栈数据结构。栈是一种遵循后进先出（LIFO）原则的数据结构，它只允许在栈顶进行插入和删除操作。什么是Stack 类？

栈是一种遵从后进先出（LIFO）原则的有序集合。新添加的或待删除的元素都保存在栈的

同一端，称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。

注：LIFO：last in first out

图例：

在这里插入图片描述在这里插入图片描述
在这里插入图片描述在这里插入图片描述

如何创建一个Stack

先将创建一个类来表示栈。先声明这个类：

代码语言：javascript复制
function Stack() { 
 //各种属性和方法的声明
}

选择一种数据结构来保存栈里的元素。可以选择数组：

代码语言：javascript复制
function Stack() { 
  //保存栈里的元素
  let items = []; 
 //各种属性和方法的声明
}

<hr/>

如何修改Stack中的值

栈声明方法举例

  • push(element(s))：添加一个（或几个）新元素到栈顶。
  • pop()：移除栈顶的元素，同时返回被移除的元素。
  • peek()：返回栈顶的元素，不对栈做任何修改（这个方法不会移除栈顶的元素，仅仅返 回它）。
  • isEmpty()：如果栈里没有任何元素就返回true，否则返回false。
  • clear()：移除栈里的所有元素。
  • size()：返回栈里的元素个数。这个方法和数组的length属性很类似。添加实现添加的可以使用push。这个方法负责往栈里添加新元素，有一点很重要：该方法只添加元素到栈顶，也就是栈的末尾。 push方法可以这样写：
代码语言：javascript复制
this.push = function(element){ 
 items.push(element); 
};

整体函数：

代码语言：javascript复制
function Stack() { 
  //保存栈里的元素
  let items = []; 
   //添加新元素
  this.push = function(element){ 
   items.push(element); 
 }; 
 //各种属性和方法的声明
}

移除

接着来实现移除，主要用来移除栈里的元素，使用的是pop方法。

栈遵从LIFO原则，因此移出的是最后添加进去的元素。

栈的pop方法可以这样写：

代码语言：javascript复制
this.pop = function(){ 
 return items.pop(); 
};

整体函数：

代码语言：javascript复制
function Stack() { 
  //保存栈里的元素
  let items = []; 
   //添加新元素
  this.push = function(element){ 
   items.push(element); 
  }; 
  //移除元素
 this.pop = function(){ 
  return items.pop(); 
 }; 
 //各种属性和方法的声明
}

查看

查看栈顶元素

因为栈顶就是最后进入的元素，类内部是用数组保存元素的，所以访问数组的最后一个元素可以用 length - 1。

图例：

在这里插入图片描述在这里插入图片描述

所以，如果想知道栈里最后添加的元素是什么，可以用peek方法。这个方法将返回栈顶的元素：

代码语言：javascript复制
this.peek = function(){ 
 return items[items.length-1]; 
};
检查栈是否为空

可以直接使用length == 0判断，如果栈为空的话将返回true，否则就返回false：

代码语言：javascript复制
this.isEmpty = function(){ 
 return items.length == 0; 
};
检查栈的长度

类似于数组的length属性，我们也能实现栈的length。对于集合，最好用size代替length。

因为栈的内部使用数组保存元素，所以能简单地返回栈的长度：

代码语言：javascript复制
this.size = function(){ 
 return items.length; 
};

整体函数：

代码语言：javascript复制
function Stack() { 
  //保存栈里的元素
  let items = []; 
   //添加新元素
  this.push = function(element){ 
   items.push(element); 
  }; 
  //移除元素
 this.pop = function(){ 
  return items.pop(); 
 }; 
 //查看栈顶元素
 this.peek = function(){ 
   return items[items.length-1]; 
 }; 
 //检查栈是否为空
 this.isEmpty = function(){ 
   return items.length == 0; 
 }; 
 //检查栈的长度
 this.size = function(){ 
   return items.length; 
 };
 //各种属性和方法的声明
}

清空栈元素

clear方法用来移除栈里所有的元素，把栈清空。实现这个方法最简单的方式是：

代码语言：javascript复制
this.clear = function(){ 
 items = []; 
};

另外也可以多次调用pop方法，把数组中的元素全部移除，这样也能实现clear方法。

打印栈元素

为了检查栈里的内容，实现一个辅助方法print。把栈里的元素都输出到控制台：

代码语言：javascript复制
this.print = function(){ 
 console.log(items.toString()); 
};

完整的Stack函数：

代码语言：javascript复制
function Stack() { 
  //保存栈里的元素
  let items = []; 
   //添加新元素
  this.push = function(element){ 
   items.push(element); 
  }; 
  //移除元素
 this.pop = function(){ 
  return items.pop(); 
 }; 
 //查看栈顶元素
 this.peek = function(){ 
   return items[items.length-1]; 
 }; 
 //检查栈是否为空
 this.isEmpty = function(){ 
   return items.length == 0; 
 }; 
 //检查栈的长度
 this.size = function(){ 
   return items.length; 
 };
 //清空栈元素
 this.clear = function(){ 
  items = []; 
 }; 
 // 打印栈元素
 this.print = function(){ 
  console.log(items.toString()); 
 }; 
}

这样，我们就完整创建了栈！

<hr/>

创建Stack的其他方法-用 ES6 语法声明 Stack 类

代码语言：javascript复制
class Stack { 
 constructor () { 
 this.items = []; //{1} 
 } 
 push(element){ 
 this.items.push(element); 
 } 
 //其他方法
}

<hr/>

使用Stack类

先初始化Stack类。再验证一下栈是否为空（输出是true，因为还没有往

栈里添加元素）。

代码语言：javascript复制
let stack = new Stack(); 
console.log(stack.isEmpty()); //输出为true

往栈里添加一些元素（这里我们添加数字1和2）:

代码语言：javascript复制
stack.push(1); 
stack.push(2);

如果调用peek方法，将会输出2，因为它是往栈里添加的最后一个元素：

代码语言：javascript复制
console.log(stack.peek()); //输出2

再添加一个元素：

代码语言：javascript复制
stack.push(11); 
console.log(stack.size()); //输出3 
console.log(stack.isEmpty()); //输出false

往栈里添加了11。如果调用size方法，输出为3，因为栈里有三个元素（1、2和11）。

再调用isEmpty方法，会看到输出了false。因为栈里有三个元素，不是空栈。

代码语言：javascript复制
console.log(stack.isEmpty()); //输出为false

然后，调用两次pop方法从栈里移除1个元素：

代码语言：javascript复制
stack.pop(); 
console.log(stack.size()); //输出2 
stack.print(); //输出[1, 2]

<hr/>

在 JavaScript 中使用栈数据结构的好处

实现递归调用：函数调用过程中，每次函数调用都会将新的函数帧（frame）压入栈中，待函数返回时再从栈中弹出。这就是递归调用所依赖的栈结构。

实现浏览器的前进后退功能：浏览器的前进后退功能依赖于两个栈，分别用来维护已经访问过的网页和下一个要访问的网页；用户点击“后退”时，将当前网页从已访问网页的栈中弹出，并将其压入下一个要访问的网页栈中。

对表达式求值：使用栈可以方便地对表达式进行求值，例如判断表达式中括号是否匹配、转换中缀表达式为后缀表达式等。

实现回溯算法：在搜索算法中，一般使用栈数据结构来保存路径信息，当搜索到某一层无解时，直接从栈中弹出该状态并回溯到上一层。

javascript

0 人点赞