JavaScript数据结构与算法之栈详解
（福利推荐：你还在原价购买阿里云服务器？现在阿里云0.8折限时抢购活动来啦！4核8G企业云服务器仅2998元/3年，立即抢购>>>：9i0i.cn/aliyun）
在上一篇博客介绍了下列表，列表是最简单的一种结构，但是如果要处理一些比较复杂的结构，列表显得太简陋了，所以我们需要某种和列表类似但是更复杂的数据结构---栈。栈是一种高效的数据结构，因为数据只能在栈顶添加或删除，所以这样操作很快，而且容易实现。
一：对栈的操作。
栈是一种特殊的列表，栈内的元素只能通过列表的一端访问，这一端陈为栈顶。比如餐馆里面洗盘子，只能先洗最上面的盘子，盘子洗完后，也只能螺到这一摞盘子的最上面。栈被称为 "后入先出"（LIFO）的数据结构。
由于栈具有后入先出的特点，所以任何不在栈顶的元素都无法访问，为了得到栈低的元素，必须先拿掉上面的元素。我们可以对栈的两种主要操作是将一个元素 压入栈 和 将一个元素 弹出栈。入栈我们可以使用方法push（）方法，出栈我们使用pop（）方法。pop（）方法虽然可以访问栈顶的元素，但是调用该方法后，栈顶元素也就从栈中被永久性的删除了。另一个我们很常用的方法是peek（），该方法只返回栈顶元素，而不删除它。
入栈和出栈的实列图如下：
push(),pop()和peek（）是栈的三个主要方法，但是栈还有其他方法和属性。如下：
clear（）：清除栈内的所有元素。
length(): 记录栈内元素的个数。
二：对栈的实现如下：
我们可以先实现栈类的方法开始；如下：
function Stack() {
this.dataStore = [];
this.top = 0;
}
如上：dataStore 是保存栈内的所有元素。变量top记录栈顶的位置，初始化为0. 表示栈顶对应数组的起始位置为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()的方法判断是否大于0 且每次执行 product* = s.pop(); pop()方法返回栈顶元素，且从栈中删掉该元素。所以每次执行一次，就删掉一个元素，直到s.length() <= 0 为止。所以 product = 5*4*3*2*1 .等操作。
相关文章
这篇文章主要为大家详细介绍了js实现简单日历效果，文中示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下2021-05-05
下面小编就为大家带来一篇js中获取时间new Date()的全面介绍。小编觉得挺不错的，现在就分享给大家，也给大家做个参考。一起跟随小编过来看看吧2016-06-06
这篇文章主要给大家介绍了关于echarts同一页面中四个图表切换的js数据交互的相关资料，文中给出了完整的示例代码供大家参考学习，对大家的学习或者工作具有一定的帮助，需要的朋友们下面随着小编来一起学习学习吧2018-07-07
springMVC + easyui + $.ajaxFileUpload实现文件上传注意事项
在使用easyUI做前端样式展示时，遇到了文件上传的问题，而且是在弹出层中提交表单，想做到不刷新页面，所以选择了使用ajaxFileUpload插件。下面通过本文给大家分享springMVC + easyui + $.ajaxFileUpload实现文件上传注意事项，需要的朋友参考下吧2017-04-04
这篇文章主要介绍了探究一道价值25k的蚂蚁金服异步串行面试题，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧2020-08-08
JavaScript+html5 canvas绘制渐变区域完整实例
这篇文章主要介绍了JavaScript+html5 canvas绘制渐变区域的方法,结合完整实例形式分析了canvas颜色调用与图形绘制的相关技巧,需要的朋友可以参考下2016-01-01
浅谈监听单选框radio改变事件(和layui中单选按钮改变事件)
今天小编就为大家分享一篇浅谈监听单选框radio改变事件(和layui中单选按钮改变事件)，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧2019-09-09
兼容最新firefox、chrome和IE的javascript图片预览实现代码
这篇文章主要介绍了兼容最新firefox、chrome和IE的javascript图片预览实现代码,测试了浏览器firefox6、firefox12、chrome 25.0.1364.172 m、IE6-IE10 都兼容,需要的朋友可以参考下2014-08-08
最近使用到了jstree，感觉是一款灵活的、可多项定制的tree插件。下面通过本文给大家详细介绍下jstree的简单实例,需要的朋友可以参考下2016-12-12
这篇文章主要介绍了JS获取子、父、兄节点方法总结及JS获取兄弟节点的两种方法,需要的朋友可以参考下2017-08-08
最新评论