在上一篇博客介绍了下列表,列表是最简单的一种结构,但是如果要处理一些比较复杂的结构,列表显得太简陋了,所以我们需要某种和列表类似但是更复杂的数据结构---栈。栈是一种高效的数据结构,因为数据只能在栈顶添加或删除,所以这样操作很快,而且容易实现。
一:对栈的操作。
栈是一种特殊的列表,栈内的元素只能通过列表的一端访问,这一端陈为栈顶。比如餐馆里面洗盘子,只能先洗最上面的盘子,盘子洗完后,也只能螺到这一摞盘子的最上面。栈被称为 "后入先出"(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 .等操作。
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
P70系列延期,华为新旗舰将在下月发布
3月20日消息,近期博主@数码闲聊站 透露,原定三月份发布的华为新旗舰P70系列延期发布,预计4月份上市。
而博主@定焦数码 爆料,华为的P70系列在定位上已经超过了Mate60,成为了重要的旗舰系列之一。它肩负着重返影像领域顶尖的使命。那么这次P70会带来哪些令人惊艳的创新呢?
根据目前爆料的消息来看,华为P70系列将推出三个版本,其中P70和P70 Pro采用了三角形的摄像头模组设计,而P70 Art则采用了与上一代P60 Art相似的不规则形状设计。这样的外观是否好看见仁见智,但辨识度绝对拉满。