"这篇文档介绍了如何在JavaScript中实现栈数据结构,通过两种不同的方式:基于数组和基于对象。栈是一种后进先出(LIFO)的数据结构,常用于算法和程序设计中。"
在JavaScript中,栈数据结构的实现可以通过数组或者对象来完成。下面是这两种实现方式的详细说明:
### 1. 基于数组实现
```javaScript
class Stack {
constructor() {
this.items = []; // 利用数组存储栈内元素
}
// 添加一个(或几个)新元素到栈顶
push(element) {
this.items.push(element);
}
// 移除栈顶的元素,同时返回被移除的元素
pop() {
return this.items.pop();
}
// 返回栈顶的元素,不对栈做任何修改
peek() {
return this.items[this.items.length - 1];
}
// 如果栈里没有任何元素就返回true,否则返回false
isEmpty() {
return this.items.length === 0;
}
// 移除栈里的所有元素
clear() {
this.items = [];
}
// 返回栈里的元素个数
size() {
return this.items.length;
}
}
const stack = new Stack();
console.log(stack.isEmpty()); // true
stack.push(7);
stack.push(5);
console.log(stack.peek()); // 5
stack.push(10);
console.log(stack.size()); // 3
console.log(stack.isEmpty()); // false
stack.push(3);
stack.pop();
stack.pop();
console.log(stack.size()); // 2
```
在这个实现中,`items`数组是存储栈元素的核心,`push()`方法用于将元素添加到数组末尾(即栈顶),`pop()`方法使用数组的`pop()`方法移除并返回栈顶元素,`peek()`方法返回栈顶元素但不移除,`isEmpty()`检查数组长度是否为0,`clear()`清空数组,`size()`返回数组长度。
### 2. 基于对象实现
```javaScript
class Stack {
constructor() {
this.items = {};
this.count = 0; // 用来记录对象中栈的长度,帮助我们实现添加和删除元素
}
// 往对象中添加元素
push(element) {
// 用count变量作为items对象的键名,插入的元素则是它的值
this.items[this.count] = element;
this.count++;
}
// 往对象中删除元素
pop() {
// 校验栈是否为空
if (this.isEmpty()) {
return undefined;
}
this.count--;
return this.items[this.count];
}
// ...其他方法与数组实现相同
}
```
在这个实现中,`items`对象的属性作为栈的位置,`count`变量跟踪栈的深度。`push()`方法使用`count`作为键将元素存入对象,`pop()`方法通过减小`count`并返回对应的对象属性值来模拟栈顶元素的移除。其他的`peek()`、`isEmpty()`、`clear()`和`size()`方法与数组实现类似。
这两种实现方式各有优缺点。数组实现更直观,操作效率高,因为JavaScript数组的`push()`和`pop()`方法是原生支持的;而对象实现则可以避免在大型栈中数组长度过大导致的问题,但其操作复杂度相对较高,且可能受到JavaScript引擎的性能限制。
在实际开发中,选择哪种实现取决于具体的需求和场景,例如对内存使用、性能以及代码可读性的考虑。在前端开发中,由于JavaScript引擎优化,通常数组实现更为常见和高效。