栈基础
- 栈的定义：栈是一个 后进先出 的线性表，要求只在栈顶进行删除和插入操作；所谓的栈，其实就是一个特殊的线性表（顺序表、链表），对于栈来说，这个表尾称为栈的 栈顶 ，相应的表头称为 栈底；
- 插入操作（Push）：叫做进栈，也称为压栈，入栈；
- 删除操作（Pop）：叫做出栈，也称为弹栈；
- 栈的存储结构
- 「顺序」存储结构（数组实现）
![]( "「顺序」存储结构")
- 「链式」存储结构（链表实现）
![]( "「顺序」存储结构")
- 「顺序」存储结构（数组实现）
栈的实现
class Stack {
constructor() {
// 存储栈的数据
this.data = {}
// 记录栈的数据个数（相当于数组的 length）
this.count = 0
}
// push() 入栈方法
push(item) {
// 方式1：数组方法 push 添加（不推荐）
// this.data.push(item)
// 方式2：利用数组长度（不推荐）
// this.data[this.data.length] = item
// 方式3：计数方式（建议使用）
this.data[this.count] = item
// 入栈后，count 自增
this.count++
}
// pop() 出栈方法
pop() {
// 出栈的前提是栈中存在元素，应先行检测
if (this.isEmpty()) {
console.log('栈为空！')
return
}
// 移除栈顶数据
// 方式1：数组方法 pop 移除
// return this.data.pop()
// 方式2：计数方式
const temp = this.data[this.count - 1]
delete this.data[--this.count]
return temp
}
// isEmpty() 检测栈是否为空
isEmpty() {
return this.count === 0
}
// top() 用于获取栈顶值
top() {
if (this.isEmpty()) {
console.log('栈为空！')
return
}
return this.data[this.count - 1]
}
// size() 获取元素个数
size() {
return this.count
}
// clear() 清空栈
clear() {
this.data = {}
this.count = 0
}
}
const s = new Stack()
s.push('a')
s.push('b')
s.push('c')
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
算法基础🔮 KMP 算法
上一篇
评论
