栈是限定仅在表尾进行插入和删除操作的线性表。
栈
允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何数据元素称为空栈。栈是后进先出的线性表，称为 LIFO 结构。
栈的插入操作，叫作进栈(压栈或入栈)，栈的删除操作，叫作出栈(弹栈)。
栈的顺序存储结构
js 代码
class SqStack {
constructor() {
this.data = [];
this.top = 0;
}
}
function push(sqStack, e) {
sqStack.top += 1
sqStack.data.push(e);
}
function pop(sqStack, e) {
if (sqStack.top === 0) {
throw new Error('已经到栈底')
}
sqStack.top-=1;
return sqStack.data.pop();
}
push 和 pop 的时间复杂度都是 O(1)。
栈的链式存储结构
栈的链式存储结构，简称为链栈。
js 代码
class StackNode {
constructor(data, next) {
this.data = data;
this.next = next;
}
}
class LinkStack {
constructor(top) {
this.top;
this.count = 0;
}
}
function createLinkStack() {
let linkStack = new LinkStack(null);
return linkStack;
}
function push(linkStack, e) {
let newNode = new StackNode(e);
newNode.next = linkStack.top;
linkStack.top = newNode;
linkStack.count += 1;
}
function pop(linkStack) {
if (linkStack.count === 0) {
throw new Error('已经到栈底');
}
let data = linkStack.top.data;
linkStack.top = linkStack.top.next;
linkStack.count-=1;
return data;
}
let linkStack = createLinkStack();
push(linkStack, 10);
push(linkStack, 5);
console.log(pop(linkStack));
console.log(pop(linkStack));
链栈的 push 和 pop 的事件复杂度都是 O(1)。
如果栈的使用过程中元素变化不可预测，有时很小，有时非常大，那么最好是用链栈，反之，如果它的变化在可控范围内，建议是用顺序栈。
栈的应用－－递归
一个直接调动自己或通过一系列的调用语句间接地调用自己的函数，称为递归函数。
每个递归定义必须有一个条件，满足时递归不再进行，即不再引用自身而是返回值退出。
