JS中数据结构之栈

接下来我将为大家讲解JS中数据结构之栈的完整攻略。

一、栈的定义

栈是一种受限的线性数据结构,它具有先进后出(Last In First Out, LIFO)的特点,即后进入的元素先出来。栈主要有两个操作:入栈和出栈,同时还需要考虑栈空和栈满两种特殊情况。

二、栈的实现

在JS中,可以通过数组来实现栈的功能。下面是一个实现栈的类:

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;
  }
  size() { // 返回栈的大小
    return this.items.length;
  }
  clear() { // 清空栈
    this.items = [];
  }
}

三、栈的应用

1. 判断括号是否匹配

栈可以用来判断括号是否匹配。例如给定一个字符串,其中包含一些括号,判断这些括号是否匹配。

function isMatchingBrackets(str) {
  const stack = new Stack();
  for (let i = 0; i < str.length; i++) {
    if (str[i] === '(' || str[i] === '[' || str[i] === '{') {
      stack.push(str[i]);
    } else if (str[i] === ')' && stack.peek() === '(') {
      stack.pop();
    } else if (str[i] === ']' && stack.peek() === '[') {
      stack.pop();
    } else if (str[i] === '}' && stack.peek() === '{') {
      stack.pop();
    } else {
      return false;
    }
  }
  return stack.isEmpty();
}

console.log(isMatchingBrackets('([]{})')); // true
console.log(isMatchingBrackets('([]{})}')); // false

2. 函数调用栈

栈被广泛应用于函数调用过程中的“调用栈”中。当一个函数被调用时,它的返回地址和参数等信息被压入栈中,当函数执行完毕时,这些信息又被弹出栈。

下面是一个递归函数的示例:

function factorial(n) {
  if (n <= 1) {
    return 1;
  }
  return n * factorial(n - 1);
}

console.log(factorial(5)); // 输出 120

这个函数用到了递归,每次调用时都会将当前的n值压入栈中,当递归结束时才开始弹出栈中保存的信息,计算阶乘的值。

四、总结

本文介绍了JS中数据结构之栈,包括栈的定义、实现以及两个示例应用,希望对大家有所帮助。

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:JS中数据结构之栈 - Python技术站

(0)
上一篇 2023年5月17日
下一篇 2023年5月17日

相关文章

  • C语言数据结构之单链表的查找和建立

    C语言数据结构之单链表的查找和建立 什么是单链表? 单链表是一种常见的数据结构,是由若干个节点(Node)组成的链式结构,每个节点存储着链表中的元素和指向下一个节点的指针。 单链表的优点是插入、删除元素简单,但是查找元素比较困难。 在C语言中,我们可以使用结构体来定义一个节点: struct ListNode { int val; struct ListNo…

    数据结构 2023年5月17日
    00
  • Go 数据结构之堆排序示例详解

    Go 数据结构之堆排序示例详解 什么是堆? 堆(Heap)是一种特殊的树形数据结构,它满足下列性质: 堆中每个节点的关键字都不大于(或不小于)其子节点的关键字。 堆中,根节点(顶端)是最小或最大元素。 堆实际上是一个完全二叉树,因此可以用数组实现。对于下标为i的节点,其左子节点为2i,右子节点为2i+1,父节点为i/2。 堆分为最大堆和最小堆。在最大堆中,父…

    数据结构 2023年5月17日
    00
  • Java数据结构专题解析之栈和队列的实现

    Java数据结构专题解析之栈和队列的实现 什么是栈和队列? 在计算机科学中,栈(Stack)和队列(Queue)都是常见的数据结构,用于解决许多问题。它们都是线性数据结构,但它们的元素访问顺序不同。 栈是先进后出(Last In First Out,LIFO)的结构,即最后放入栈中的元素最先被访问。 队列是先进先出(First In First Out,FI…

    数据结构 2023年5月17日
    00
  • Java数据结构之实现哈希表的分离链接法

    Java数据结构之实现哈希表的分离链接法 哈希表是一种非常常用的数据结构,它将数据存储在一个数组中,每个数组元素都存储着链表中的一个节点,这样可以实现高效的数据存储和查找操作。在哈希表中,我们可以通过哈希函数将关键字映射到数组中的特定位置。 但是,当哈希表的负载因子过高时,就会造成哈希冲突,这意味着两个或更多的关键字映射到了同一个数组位置。一种常见的解决方案…

    数据结构 2023年5月17日
    00
  • Java矢量队列Vector使用示例

    Java矢量队列Vector使用示例 Java中的Vector是一个可调整大小的数组实现,与ArrayList类似,但是可以支持同步。在需要线程安全时,可以使用Vector代替ArrayList。 Vector的创建 使用Vector需要先导入Java.util.Vector类,然后可以使用以下代码创建一个Vector: Vector<Object&g…

    数据结构 2023年5月17日
    00
  • mosn基于延迟负载均衡算法 — 走得更快,期待走得更稳

    前言 这篇文章主要是介绍mosn在v1.5.0中新引入的基于延迟的负载均衡算法。 对分布式系统中延迟出现的原因进行剖析 介绍mosn都通过哪些方法来降低延迟 构建来与生产环境性能分布相近的测试用例来对算法进行验证 地址:https://github.com/mosn/mosn/pull/2253 在开始聊基于延迟的负载均衡算法之前,先介绍下什么是负载均衡——…

    算法与数据结构 2023年5月8日
    00
  • C语言数据结构之vector底层实现机制解析

    C语言数据结构之vector底层实现机制解析 什么是vector? vector是C++标准库中的一种容器,可以动态调整大小,用于存储数据。 vector的底层实现机制 vector实际上是通过数组实现的,当需要添加元素时,如果当前数组已满,就会重新创建一个更大的数组,并将原数组中的元素复制到新数组中。这样,内存空间得到了增加,同时操作后的元素仍然是顺序存储…

    数据结构 2023年5月17日
    00
  • Java数据结构之常见排序算法(上)

    Java数据结构之常见排序算法(上) 本篇文章将介绍常见的排序算法,包括冒泡排序、选择排序、插入排序、快速排序和归并排序。这些排序算法既是学习算法和数据结构的入门知识,也是在实际工作中常用的基础算法。 冒泡排序 冒泡排序是一种简单的排序算法,它的基本思想是从前往后依次比较相邻的两个元素,如果前面的元素比后面的元素大,则交换它们的位置,重复这个过程,每一轮比较…

    数据结构 2023年5月17日
    00
合作推广
合作推广
分享本页
返回顶部