基础篇——栈

我们身边的栈

浏览器前进后退功能

当你依次访问完一串页面 a-b-c 之后，点击浏览器的后退按钮，就可以查看之前浏览过的页面 b 和 a。当你后退到页面 a，点击前进按钮，就可以重新查看页面 b 和 c。但是，如果你后退到页面 b 后，点击了新的页面 d，那就无法再通过前进、后退功能查看页面 c 了。

​ 栈是一种“操作受限”的线性表，只允许一端插入和删除数据。

当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，这时我们就应该首选“栈”这种数据结构。

如何实现一个“栈”？

从刚才栈的定义里，我们可以看出，栈主要包含两个操作，入栈和出栈，也就是在栈顶插入一个数据和从栈顶删除一个数据。理解了栈的定义之后，我们来看一看如何用代码实现一个栈。

先看代码，👨‍👩‍👧‍👦

class Stack {
  constructor() {
    this.stack = []; // 使用数组来存储栈中的元素
  }

  // 压入元素到栈顶
  push(item) {
    this.stack.push(item);
  }

  // 弹出并返回栈顶元素
  pop() {
    if (!this.isEmpty()) {
      return this.stack.pop();
    }
    return null; // 栈为空时返回 null
  }

  // 返回栈顶元素，但不弹出
  peek() {
    if (!this.isEmpty()) {
      return this.stack[this.stack.length - 1];
    }
    return null; // 栈为空时返回 null
  }

  // 检查栈是否为空
  isEmpty() {
    return this.stack.length === 0;
  }

  // 返回栈中元素的个数
  size() {
    return this.stack.length;
  }
}

// 使用示例
const stack = new Stack();

stack.push(1);
stack.push(2);
stack.push(3);

console.log(stack.size()); // 输出 3

console.log(stack.peek()); // 输出 3

console.log(stack.pop()); // 输出 3

console.log(stack.size()); // 输出 2

• push(item): 将元素 item 压入栈顶。
• pop(): 弹出并返回栈顶元素。
• peek(): 返回栈顶元素，但不弹出。
• isEmpty(): 检查栈是否为空，返回布尔值。
• size(): 返回栈中元素的个数。

这个是用数组实现的栈

实际上，栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。