栈是一种按照后进先出(LIFO, Last In First Out)的原理运作的有序集合,新添加的或待删除的元素都保存在栈的末尾,称作「栈顶」,另一端为「栈底」。
在栈里,新元素都靠近栈顶,旧元素都接近栈底。
栈数据结构使用两种基本操作:推入(压栈,push)和弹出(弹栈,pop)。推入是将数据放入栈的顶端;弹出是将顶端数据数据输出(回传)。
特点
栈的基本特点:
- 先入后出,后入先出;
- 除头尾节点之外,每个元素有一个前驱和一个后继。
定义
interface IStack<E> { public push(el: E): void; public pop(): E; public peak(): E; public size(): number; public clear(): void; }
|
实现
在 JS 中,Array
已经自带用于推入与弹出的 .push()
和 .pop()
,因而数组也可被看作是栈。
下面的实现代码中除了 .splice()
不用任何数组的原生方法:
class Stack<E> implement IStack<E> { private elements: E[] = [];
public push(el: E): void { this.elements[this.size()] = el; }
public pop(): E { return this.elements.splice(-1, 1)[0]; }
public peak(): E { return this.elements[this.size() - 1]; }
public size(): number { return this.elements.length; }
public clear(): void { this.elements = []; } }
|
更多