js实现栈

实现栈的基本结构

在JavaScript中，栈可以通过数组或链表实现。数组实现更简单直观，适合大多数场景。

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

核心方法实现

push方法：添加元素到栈顶

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

pop方法：移除并返回栈顶元素

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

peek方法：查看栈顶元素但不移除

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

辅助方法实现

isEmpty方法：检查栈是否为空

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

size方法：获取栈中元素数量

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

clear方法：清空栈

clear() {
  this.items = [];
}

完整实现示例

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

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

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

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

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

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

  clear() {
    this.items = [];
  }

  print() {
    console.log(this.items.toString());
  }
}

使用示例

const stack = new Stack();
stack.push(10);
stack.push(20);
stack.push(30);
stack.print(); // 10,20,30
console.log(stack.pop()); // 30
console.log(stack.peek()); // 20
console.log(stack.size()); // 2
stack.clear();
console.log(stack.isEmpty()); // true

时间复杂度分析

• push操作：O(1)
• pop操作：O(1)
• peek操作：O(1)
• size操作：O(1)
• isEmpty操作：O(1)

链表实现方案

对于需要频繁动态扩容的场景，可以考虑链表实现：

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class LinkedListStack {
  constructor() {
    this.top = null;
    this.length = 0;
  }

  push(value) {
    const newNode = new Node(value);
    newNode.next = this.top;
    this.top = newNode;
    this.length++;
  }

  pop() {
    if (this.isEmpty()) return null;
    const value = this.top.value;
    this.top = this.top.next;
    this.length--;
    return value;
  }

  peek() {
    if (this.isEmpty()) return null;
    return this.top.value;
  }

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

  size() {
    return this.length;
  }
}