栈
基本概念
是一种只能在一端进行插入和删除操作的特殊线性表。具有以下特点:
- 先进后出(FILO)
- 数组或链表实现
名词解释：
- 栈顶(top)：允许进行插入和删除操作的一端称为栈顶
- 栈底(bottom)：不允许操作。栈底固定，栈顶浮动
- 进栈(push)：插入操作
- 退栈(pop)：删除
- 空栈：没有任何元素
备注
JS 中没有栈，用数组进行模拟
实现
数组模拟栈
class Stack {
construct(n) {
this.arr = new Array(n);
this.top = -1;
}
// 进栈
push() {
this.arr[++this.top] = value;
}
// 出栈
pop() {
if (this.empty()) return;
return this.arr[this.top--];
}
// 查看栈顶
peek() {
if (this.empty()) return;
return this.arr[this.top];
}
// 栈是否为空
empty() {
return this.top === -1;
}
// 查看栈的大小
size() {
return this.top + 1;
}
}