前端需要掌握的数据结构之-栈

栈（Stack）是一种基于后进先出（LIFO）原则的数据结构，常常用于程序中函数调用、表达式求值、括号匹配等场景。本文将介绍栈的基本概念、常见操作和使用场景，并用 JavaScript 语言举例实现栈的基本功能。

基本概念

栈是一种线性数据结构，它包含两个基本操作：压入（push）和弹出（pop）。压入操作将一个元素添加到栈的顶部，弹出操作则将栈顶元素移除并返回它。另外，栈还具有一个重要的特性，即只能在栈顶进行操作，也就是说，最后一个压入栈中的元素会成为第一个被弹出的元素。

常见操作

• push(element)：将元素压入栈中；

• pop()：从栈中弹出栈顶元素，并返回它；

• peek()：返回栈顶元素，但不对栈进行修改；

• isEmpty()：判断栈是否为空；

• clear()：清空栈中的所有元素；

• size()：返回栈中元素的个数。

使用场景

栈在程序中有着广泛的应用，其中一些典型的场景包括：

• 函数调用：在程序中，每个函数都有一个独立的执行环境，包含参数、局部变量等信息。当一个函数被调用时，系统会为其创建一个栈帧（Stack Frame），用于存储这些信息。当函数执行完成后，对应的栈帧会被弹出，控制权会返回到上一个函数。

• 表达式求值：在表达式求值过程中，通常需要考虑运算符的优先级和括号的匹配。可以使用栈来存储运算符和括号，以便按正确的顺序执行运算。

• 浏览器前进、后退功能：浏览器的前进和后退功能是基于栈实现的。当用户访问一个新的页面时，浏览器会将该页面的 URL 压入一个历史栈中。当用户点击前进或后退按钮时，浏览器会从历史栈中取出相应的 URL，并加载该页面。

使用 JavaScript 实现栈

在 JavaScript 中，可以使用数组来实现栈的基本功能。具体实现代码如下：

class Stack {
  constructor() {
    this.items = [];
  }
  //入栈
  push(element) {
    this.items.push(element);
  }
  // 出栈
  pop() {
    return this.items.pop();
  }
  // 返回栈顶元素
  peek() {
    return this.items[this.items.length - 1];
  }
  // 栈是否为空
  isEmpty() {
    return this.items.length === 0;
  }
  // 清空栈中所有元素
  clear() {
    this.items = [];
  }
  // 返回栈中元素的个数
  size() {
    return this.items.length;
  }

}

上述代码定义了一个 Stack 类，包含了栈的常见操作。其中，构造函数用于初始化栈，push 和 pop 方法用于压入和弹出元素，peek 方法用于返回栈顶元素，isEmpty 方法用于判断栈是否为空，clear 方法用于清空栈中所有元素，size 方法用于返回栈中元素的个数。

下面是一个使用 Stack 类的例子：

const stack = new Stack();

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

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

stack.pop();
console.log(stack.peek()); // 2

console.log(stack.isEmpty()); // false
console.log(stack.size()); // 2

stack.clear();
console.log(stack.isEmpty()); // true
console.log(stack.size()); // 0

在上述例子中，首先创建了一个 Stack 类的实例 stack，然后通过 push 方法向栈中添加了三个元素。接着，使用 peek 方法返回了栈顶元素，并使用 pop 方法弹出了该元素。最后，使用 isEmpty 和 size 方法分别判断了栈是否为空和栈中元素的个数，并使用 clear 方法清空了栈中所有元素。

总结

总的来说，栈作为一种重要的数据结构，在程序中有着广泛的应用，能够帮助我们更加高效地解决很多问题。在 JavaScript 中，使用数组来实现栈是一种简单而有效的方式。

关注我不迷路