在 JavaScript 中实现栈

栈是一种按照后进先出(LIFO, Last In First Out)的原理运作的有序集合,新添加的或待删除的元素都保存在栈的末尾,称作「栈顶」,另一端为「栈底」。

在栈里,新元素都靠近栈顶,旧元素都接近栈底。

栈数据结构使用两种基本操作:推入(压栈,push)和弹出(弹栈,pop)。推入是将数据放入栈的顶端;弹出是将顶端数据数据输出(回传)。

特点

栈的基本特点:

  1. 先入后出,后入先出;
  2. 除头尾节点之外,每个元素有一个前驱和一个后继。

定义

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 = [];
}
}

更多