栈

栈是一种后进先出（LIFO）的数据结构，它只允许在表的一端进行插入和删除操作。栈中没有元素时，称为空栈。

基本操作

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

• push(element): 在栈顶添加一个元素
• pop(): 移除栈顶的元素并返回
• peek(): 查看栈顶的元素但不移除
• isEmpty(): 检查栈是否为空
• size(): 获取栈中元素的数量

实现

栈可以使用数组或链表来实现。使用数组实现的栈称为顺序栈，使用链表实现的栈称为链式栈。

顺序栈

使用数组实现的栈称为顺序栈。

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

  push(element) {
    this.items.push(element);
  }

  pop() {
    if (this.isEmpty()) {
      return null;
    }
    return this.items.pop();
  }

  peek() {
    if (this.isEmpty()) {
      return null;
    }
    return this.items[this.items.length - 1];
  }

  isEmpty() {
    return this.items.length === 0;
  }

  size() {
    return this.items.length;
  }
}

链式栈

使用链表实现的栈称为链式栈。

// 先定义链表节点
class Node {
  constructor(element) {
    this.element = element;
    this.next = null;
  }
}

// 使用链表实现栈
class LinkedStack {
  constructor() {
    this.top = null; // 栈顶指针
    this.count = 0;  // 元素计数
  }

  // 入栈操作
  push(element) {
    const newNode = new Node(element);
    if (this.isEmpty()) {
      this.top = newNode;
    } else {
      // 新节点指向当前栈顶
      newNode.next = this.top;
      // 更新栈顶为新节点
      this.top = newNode;
    }
    this.count++;
  }

  // 出栈操作
  pop() {
    if (this.isEmpty()) {
      return null;
    }
    
    const removedElement = this.top.element;
    this.top = this.top.next;
    this.count--;
    
    return removedElement;
  }

  // 查看栈顶元素
  peek() {
    if (this.isEmpty()) {
      return null;
    }
    return this.top.element;
  }

  // 检查栈是否为空
  isEmpty() {
    return this.top === null;
  }

  // 获取栈的大小
  size() {
    return this.count;
  }
}