JS中数据结构之栈

栈是一种高效的数据结构，因为数据只能在栈顶添加或删除，所以这样的操作很快，而且容易实现。

栈是一种特殊的列表，栈内的元素只能通过列表的一端访问，这一端称为栈顶。栈被称为一种后入先出（LIFO，last-in-first-out）的数据结构。由于栈具有后入先出的特点，所以任何不在栈顶的元素都无法访问。为了得到栈底的元 素，必须先拿掉上面的元素。

栈的实现

用数组 dataStore 保存栈内元素，构造函数将其初始化为一个空数组。变量 top 记录 栈顶位置，被构造函数初始化为 0，表示栈顶对应数组的起始位置 0。如果有元素被压入 栈，该变量的值将随之变化。

function Stack() {
  this.dataStore = [];
  this.top = 0;
  this.push = push;
  this.pop = pop;
  this.peek = peek;
}

push() 方法：当向栈中压入一个新元素时，需要将其保存在数组中变量 top 所对应的位置，然后将 top 值加 1，让其指向数组中下一个空位置。

function push(element) {
  this.dataStore[this.top++] = element;
}

pop() 方法：与 push() 方法相反——它返回栈顶元素，同时将变量 top 的值减 1

function pop() {
  return this.dataStore[--this.top];
}

peek() 方法：返回数组的第 top-1 个位置的元素，即栈顶元素。如果对一个空栈调用 peek() 方法，结果为 undefined。这是因为栈是空的，栈顶没有任何 元素。

pop() 方法虽然可以访问栈顶的元素，但是调用该方法后，栈顶元素也从栈中被永久性地删除了。peek() 方法则只返回栈顶元素，而不删除它。

function peek() {
  return this.dataStore[this.top-1];
}

length() 方法：通过返回变量 top 值的方式返回栈 内的元素个数

function length() {
  return this.top;
}

clear()方法：将变量 top 的值设为 0，清空栈

function clear() {
  this.top = 0;
}

使用栈解决问题举例：判断一个字符串是否是回文

赞 (0)

相关推荐

  • JavaScript数据结构与算法之栈详解

    JavaScript数据结构与算法之栈详解

    在上一篇博客介绍了下列表,列表是最简单的一种结构,但是如果要处理一些比较复杂的结构,列表显得太简陋了,所以我们需要某种和列表类似但是更复杂的数据结构---栈.栈是一种高效的数据结构,因为数据只能在栈顶添加或删除,所以这样操作很快,而且容易实现. 一:对栈的操作. 栈是一种特殊的列表,栈内的元素只能通过列表的一端访问,这一端陈为栈顶.比如餐馆里面洗盘子,只能先洗最上面的盘子,盘子洗完后,也只能螺到这一摞盘子的最上面.栈被称为 "后入先出"(LIFO)的数据结构. 由于栈具有后入先出的特点

  • JavaScript数据结构与算法之栈与队列

    学习起因 曾经有一次在逛V2EX时,碰到这么一个帖子. 数学完全还给老师了,想学回一些基础数学,大概是高中程度的,有什么书籍推荐? 发帖的楼主大学没有高数课程,出去工作时一直在从事前端的工作.感觉到数学知识的匮乏,所以想补一补数学. 看了看帖子,感觉和我很像,因为我的专业是不开高数的,我学的也是前端.也同样感觉到了数学知识匮乏所带来的困顿.同时因为自己的数学思维实在是不怎么好,所以决定努力补习数学与计算机基础知识. 当时也有人说:"前端需要什么数据结构与算法",但是对于这个事情我有自己

  • JavaScript数据结构学习之数组、栈与队列

    前言 数据结构就是关系,没错,就是数据元素相互之间存在的一种或多种特定关系的集合. 常用的数据结构有: 数组,队列(queue),堆(heap),栈(stack),链表(linked list ),树(tree),图(graph)和散列表(hash) 本文主要介绍的是数组.栈与队列,下面来一起看看详细的介绍吧. 一.数组 数组是平时使用最常用的数据结构,在JavaScript中数组是动态的分配大小,在这里我不会介绍JavaScript里面数组的所有的方法,而是针对数据结构这个方向谈谈所用到的方法

  • JavaScript数据结构之栈实例用法

    JavaScript数据结构之栈实例用法

    栈 先来看一道题 Leetcode 32 Longest Valid Parentheses (最长有效括号) 给定一个只包含 '(' 和 ')' 的字符串,找出最长的包含有效括号的子串的长度. 示例 1: 输入: "(()" 输出: 2 解释: 最长有效括号子串为 "()" 示例 2: 输入: ")()())" 输出: 4 解释: 最长有效括号子串为 "()()" 这道题可以用动态规划来做,也能用简洁明了的栈来解决. 什么是

  • JavaScript数组实现数据结构中的队列与堆栈

    JavaScript数组实现数据结构中的队列与堆栈

    一.队列和堆栈的简单介绍 1.1.队列的基本概念 队列:是一种支持先进先出(FIFO)的集合,即先被插入的数据,先被取出! 如下图所示: 1.2.堆栈的基本概念 堆栈:是一种支持后进先出(LIFO)的集合,即后被插入的数据,先被取出! 如下图所示: 二. 在JavaScript中实现队列和堆栈 在JavaScript中实现队列和数组主要是通过数组,js数组中提供了以下几个方法可以让我们很方便实现队列和堆栈: •shift:从数组中把第一个元素删除,并返回这个元素的值. •unshift: 在数组

  • JavaScript数据结构中栈的应用之表达式求值问题详解

    本文实例讲述了JavaScript数据结构中栈的应用之表达式求值问题.分享给大家供大家参考,具体如下: 下面来谈一个比较经典的表达式求值问题,这个问题主要是设计到操作符的优先级.我们通常看到的表达式都是中缀表达式,存在很多优先级差别,而后缀表达式则没有这些优先级问题.下面先看看两种表达式的区别. 中缀表达式:a*b+c*d-e/f      后缀表达式:ab*cd*+ef/- 从中缀表达式转换到后缀表示式是很难实现的,我们这里可以通过栈的思想来实现.下面进行详细的介绍是什么样的思想: 在对一个中

  • javascript编程实现栈的方法详解【经典数据结构】

    javascript编程实现栈的方法详解【经典数据结构】

    本文实例讲述了javascript编程实现栈的方法.分享给大家供大家参考,具体如下: 栈是限定仅在表尾进行插入或删除操作的线性表,栈是先进后出的.栈的表尾称为栈顶(top),而表头端称为栈底(bottom). 和线性表类似,栈也有两种存储表示方法,顺序栈和链栈. 这里讲一下顺序栈,设置指针top指示栈顶元素在顺序栈中的位置.通常的做法就是以top=0表示空栈.base为栈底指针,top为栈顶指针. 如果base为null,则表示栈结构不存在,如果top=base则表示空栈.每当插入一个新的元素,

  • JavaScript中数据结构与算法(一)：栈

    JavaScript中数据结构与算法(一)：栈

    序 数据结构与算法JavaScript这本书算是讲解得比较浅显的,优点就是用javascript语言把常用的数据结构给描述了下,书中很多例子来源于常见的一些面试题目,算是与时俱进,业余看了下就顺便记录下来吧 git代码下载:https://github.com/JsAaron/data_structure.git 栈结构 特殊的列表,栈内的元素只能通过列表的一端访问,栈顶 后入先出(LIFO,last-in-first-out)的数据结构 javascript提供可操作的方法, 入栈 push,

  • javascript数据结构中栈的应用之符号平衡问题

    本文实例讲述了javascript数据结构中栈的应用之符号平衡问题.分享给大家供大家参考,具体如下: 由于栈先进后出的结构,我们可以将其作为有用的工具,下面就介绍一下栈的应用. 首先是符号的平衡问题.有一串字符串,我们需要判断其中固定的字符是否成对出现,比如<> {} [] () 等.当然实现的方法有很多,但是采用栈的实现会相对更加简单. 实现上述算法的JavaScript代码如下 <!DOCTYPE html> <html> <head> <meta

  • 利用JavaScript实现栈的数据结构示例代码

    前言 本文主要给大家介绍的是关于JavaScript实现栈的数据结构的相关内容,分享出来供大家参考学习,话不多少,来一起看看详细的介绍: 堆栈(英语:stack),也可直接称栈,在计算机科学中,是一种特殊的串列形式的数据结构,它的特殊之处在于只能允许在链接串列或阵列的一端(称为堆叠顶端指标,英语:top)进行加入数据(push)和输出数据(pop)的运算.另外栈也可以用一维数组或连结串列的形式来完成. 由于堆叠数据结构只允许在一端进行操作,因而按照后进先出(LIFO, Last In First

  • JS中的算法与数据结构之栈(Stack)实例详解

    JS中的算法与数据结构之栈(Stack)实例详解

    本文实例讲述了JS中的算法与数据结构之栈(Stack).分享给大家供大家参考,具体如下: 栈(Stack) 上一篇我们说到了列表,它是一种最自然的数据组织方式,如果对数据的存储顺序要求不重要,那么列表就是一种非常适合的数据结构,但对于计算机其他的一些应用(比如后缀表达式),那么列表就显得有些无能为力, 所以,我们需要一种和列表功能相似但更复杂的数据结构. 栈,又叫堆栈,是和列表类似的一种数据结构,但是却更高效,因为栈内的元素只能通过列表的一端访问,称为栈顶,数据只能在栈顶添加或删除,遵循 先入后

随机推荐