栈

在计算机科学中, 一个 栈(stack) 是一种抽象数据类型,用作表示元素的集合,具有两种主要操作:

• push, 添加元素到栈的顶端(末尾);
• pop, 移除栈最顶端(末尾)的元素.

以上两种操作可以简单概括为“后进先出(LIFO = last in, first out)”。

此外,应有一个 peek 操作用于访问栈当前顶端(末尾)的元素。

"栈"这个名称,可类比于一组物体的堆叠(一摞书,一摞盘子之类的)。

栈的 push 和 pop 操作的示意

Stack

实现栈

class Stack {
  constructor() {
    this.items = [];
  }

  // 入栈操作
  push(element) {
    this.items.push(element);
  }

  // 出栈操作
  pop() {
    if (this.isEmpty()) {
      throw new Error("Stack is empty");
    }
    return this.items.pop();
  }

  // 返回栈顶元素
  peek() {
    if (this.isEmpty()) {
      throw new Error("Stack is empty");
    }
    return this.items[this.items.length - 1];
  }

  // 判断栈是否为空
  isEmpty() {
    return this.items.length === 0;
  }

  // 返回栈的大小
  size() {
    return this.items.length;
  }

  // 清空栈
  clear() {
    this.items = [];
  }
}

const stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
console.log(stack.peek()); // 输出: 30
console.log(stack.size()); // 输出: 3
console.log(stack.isEmpty()); // 输出: false
stack.pop();
console.log(stack.size()); // 输出: 2
stack.clear();
console.log(stack.isEmpty()); // 输出: true

参考

• Wikipedia
• YouTube