栈结构 - wangshengliang

基础知识

栈，英语为 Stack，这是一种基本数据结构，也是属于线性的数据结构。其特点为：

FILO：first in last out，先进后出，最先进入栈的元素必须等到所有后进入的元素出栈之后才能被移除
LIFO：last in first out，后进先出，新元素总是被放到栈顶，元素的访问和移除也始终发生在栈顶。
栈的大小：栈的大小通常是动态的，它可以根据需要增长或缩小（取决于栈的实现，栈可以是基于数组或链表的）。

栈主要支持以下几种基本操作：

push：将一个元素添加到栈的顶端。
pop：移除并返回栈顶元素。
peek（或 top）：返回栈顶元素但不移除它。
isEmpty：检查栈是否为空。
size：返回栈中元素的数量。

代码实现

JS 中没有直接提供栈这种数据结构，因此只有我们自己进行模拟，可以基于数组或链表来实现栈结构。

class Stack {
  constructor(...args) {
    this.stack = [...args] // 栈内部使用数组来存储数据
  }
  push(...items) {
    return this.stack.push(...items)
  }
  pop() {
    return this.stack.pop()
  }
  size() {
    return this.stack.length
  }
  peak() {
    return this.isEmpty() ? undefined : this.stack[this.size() - 1]
  }
  isEmpty() {
    return this.size() === 0
  }
}

测试用例：

const stack = new Stack(1, 2, 3, 4, 5)
console.log(stack.pop()) // 5
console.log(stack.peak()) // 4
console.log(stack.isEmpty()) // false
console.log(stack.size()) // 4
console.log(stack.push(100, 200, 300)) // 7
console.log(stack.size()) // 7
console.log(stack.peak()) // 300
console.log(stack.pop()) // 300
console.log(stack.pop()) // 200
console.log(stack.pop()) // 100

栈应用场景

历史记录
撤销操作

-EOF-