栈是一种遵从后进先出(LIFO)原则的有序集合。新添加的或是待删除的元素都保存在栈的末尾。我们称作栈顶,而另一端我们称作栈底。
在现实生活中就有很多栈的例子,比如下图的书本,这一摞书如果要取肯定是先去最上面的那一本,但它是最后一个放上去的,也就是栈顶的元素都是待添加或是待删除的。这就是后进先出的实际例子。
首先我们先创建一个类:
function Stack(){
//各种属性和方法的声明
}
然后我们需要一种数据结构来保存栈里面的数据:
var items=[];
接下来,我们需要给栈声明一些方法:
push(element):添加一个或是几个新元素到栈顶。
pop():移除栈顶的元素,同时返回被移除元素。
peek():返回栈顶的元素,但并不对栈顶的元素做出任何的修改。
isEmpty():检查栈内是否有元素,如果有返回true,没有返回false。
clear():清除栈里的元素。
size():返回栈的元素个数。
print():打印栈里的元素。
我们通过javascript提供的api,实现栈如下:
function Stack() {
var 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());
};
this.toString = function(){
return items.toString();
};
}
创建完了栈,也给他了方法,然后我们来实例化一个对象:
var stack=new Stack();
console.log(stack.isEmpty());
//true
stack.push(1);
stack.push(3);
//添加元素
console.log(stack.peek());
//输出栈顶元素3
console.log(stack.size());
//2
//输出元素个数