数据结构与算法（JS版）—— 栈
2021-06-12 本文已影响0人
小牧羊爱吃瓜
1. 概念
- 类似于数组，但在添加和删除元素时更为可控
- 是遵从后进先出原则（LIFO）的有序集合
- 新元素或待删除的元素都靠近栈顶
- 旧元素都接近栈底
- 现实生活中，类似于一摞书或者一叠盘子
- 应用：编译器内存中保存变量、方法调用等；浏览器历史记录
2. 创建一个基于数组的栈
-
需要实现的方法：
- push(element(s))：添加一个或几个新元素到栈顶
- pop()：移除栈顶的元素，同时返回被移除的元素
- peek()：返回栈顶元素，不改变栈
- isEmpty()：是否为空栈，返回布尔值
- clear()：清空栈
- size()：返回栈的元素个数
- toString()：将栈元素变成字符串输出
-
代码实现 stack-array.js
class Stack {
constructor() {
this.items = [];
}
push(i) {
this.items.push(i);
}
pop() {
// 注意要有返回值
return this.items.pop();
}
peek() {
// 返回栈顶元素
return this.items[this.items.length - 1];
}
isEmpty() {
return this.items.length === 0;
}
clear() {
this.items = [];
}
size() {
return this.items.length;
}
toString() {
return this.items.toString();
}
}
// 使用
const stack = new Stack();
console.log(stack.isEmpty());
stack.push(5);
stack.push(8);
stack.push(1);
console.log(stack.pop());
console.log(stack.peek());
console.log(stack.size())
console.log(stack.toString());
补充
- 在使用数组时，大部分方法的时间复杂度是O(n)。
- O(n)的意思是，我们需要迭代整个数组直到找到要找的那个元素，最坏的情况下需要迭代数组的所有位置，其中n代表数组的长度。
- 数组是元素的一个有序集合，为了保证元素排列有序，它会占用更多的内存空间。
3. 创建一个基于对象的栈
- 为了占用较少内存，且降低时间复杂度，可以基于对象创建Stack类
- 类中需要一个count属性辅助记录
- 除了toString方法，时间复杂度均为O(1)
class Stack {
constructor() {
this.items = {};
this.count = 0;
}
push(i) {
this.items[this.count] = i;
this.count++;
}
pop() {
// 不要忘记为空判断
if (this.isEmpty()) {
return undefined;
}
this.count--;
// 需要先用变量保存一下this.items[this.count]值，否则返回undefined
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;
}
clear() {
this.items = {};
// 计数不要忘记归0
this.count = 0;
}
size() {
return this.count;
}
toString() {
if (this.isEmpty()) {
return '';
}
return Object.values(this.items).toString();
}
}
