js 实现栈
栈的基本概念
栈是一种遵循后进先出（LIFO）原则的数据结构。主要操作包括压栈（push）和弹栈（pop），其他常见操作有查看栈顶元素（peek）和判断栈是否为空（isEmpty）。
基于数组的实现
使用数组可以快速实现栈的核心功能。数组的尾部作为栈顶，操作效率较高。
class Stack {
constructor() {
this.items = [];
}
push(element) {
this.items.push(element);
}
pop() {
if (this.isEmpty()) return undefined;
return this.items.pop();
}
peek() {
if (this.isEmpty()) return undefined;
return this.items[this.items.length - 1];
}
isEmpty() {
return this.items.length === 0;
}
size() {
return this.items.length;
}
clear() {
this.items = [];
}
}基于对象的实现
对于需要更严格封装或性能优化的场景，可以使用对象存储栈元素，并通过变量跟踪栈顶位置。
class Stack {
constructor() {
this.count = 0;
this.items = {};
}
push(element) {
this.items[this.count] = element;
this.count++;
}
pop() {
if (this.isEmpty()) return undefined;
this.count--;
const result = this.items[this.count];
delete this.items[this.count];
return result;
}
peek() {
if (this.isEmpty()) return undefined;
return this.items[this.count - 1];
}
isEmpty() {
return this.count === 0;
}
size() {
return this.count;
}
clear() {
this.items = {};
this.count = 0;
}
}时间复杂度分析
- push/pop操作：两种实现方式均为 $O(1)$ 时间复杂度。
- peek/size/isEmpty操作：同样保持 $O(1)$ 时间复杂度。
实际应用示例
实现十进制转二进制是栈的典型应用场景：
function decimalToBinary(decimal) {
const stack = new Stack();
let num = decimal;
let binaryString = '';
while (num > 0) {
stack.push(num % 2);
num = Math.floor(num / 2);
}
while (!stack.isEmpty()) {
binaryString += stack.pop().toString();
}
return binaryString || '0';
}注意事项
- 数组实现方式简单直观，但可能涉及动态扩容。
- 对象实现方式避免了数组的动态扩容开销，适合对性能要求较高的场景。
- 实际开发中可根据需求选择合适的方式，现代JavaScript引擎对数组优化较好，通常数组实现已足够高效。
