通过前面一节《JavaScript数据结构01 - 数组》我们知道,可以在数组的任意位置上删除或添加元素。然而,有时候我们还需要一种在添加或删除元素时有更多控制的数据结构。
有两种数据结构类似于数组,但在添加和删除元素时更为可控。
它们就是栈和队列。
栈是一种遵循后进先出(LIFO)原则的有序集合。新添加的或待删除的元素都保存在栈的末尾,称作栈顶,另一端就叫栈底。
在栈里,新元素都靠近栈顶,旧元素都接近栈底。
栈也被用在编程语言的编译器和内存中保存变量、方法调用等,比如函数的调用栈。
这里我还是用构造函数的形式来书写,大家有兴趣可以用ES6的Class来重写一遍。
// Stack类
function Stack () {
this.items = [];
this.push = push;
this.pop = pop;
this.peek = peek;
this.isEmpty = isEmpty;
this.clear = clear;
this.size = size;
this.print = print;
}
复制代码
栈里面有一些声明的方法:
// 添加新元素到栈顶
function push (element) {
this.items.push(element);
}
// 移除栈顶元素,同时返回被移除的元素
function pop () {
return this.items.pop();
}
// 查看栈顶元素
function peek () {
return this.items[this.items.length - 1];
}
// 判断是否为空栈
function isEmpty () {
return this.items.length === 0;
}
// 清空栈
function clear () {
this.items = [];
}
// 查询栈的长度
function size () {
return this.items.length;
}
// 打印栈里的元素
function print () {
console.log(this.items.toString());
}
复制代码
// 创建Stack实例
var stack = new Stack();
console.log(stack.isEmpty()); // true
stack.push(5); // undefined
stack.push(8); // undefined
console.log(stack.peek()); // 8
stack.push(11); // undefined
console.log(stack.size()); // 3
console.log(stack.isEmpty()); // false
stack.push(15); // undefined
stack.pop(); // 15
console.log(stack.size()); // 3
stack.print(); // 5,8,11
stack.clear(); // undefined
console.log(stack.size()); // 0
复制代码