【前端数据结构基础】栈

peixn 发布于2019-08-26 12:00 / 2623人阅读

摘要：前言栈是一种高效的数据结构，因为数据只能在栈顶添加或删除，所以这样的操作很快且很容易实现。栈被称为一种后入先出，的数据结构。二构造栈数据结构我们将使用实现栈结构，各部分功能使用注释说明。参考资料数据结构与算法描述第章栈

前言

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

一、什么是栈

栈是一种特殊的列表，栈内的元素只能通过列表的一端访问，这一端称之为栈顶。
栈被称为一种后入先出（LIFO，last-in-first-out）的数据结构。
由于栈具有后入先出的特点，所以任何不在栈顶的元素都无法访问，我们必须先拿掉上面的元素才能访问其栈底的元素。
对栈的主要操作是将一个元素压入栈和将一个元素弹出栈，入栈使用push()方法，出栈使用pop()方法。

二、构造栈数据结构

我们将使用JavaScript实现栈结构，各部分功能使用注释说明。
存储数据我们使用的是数组。

/**
 * Stack 构造方法
 */
function Stack () {
  this.dataStore = []
  this.top = 0
  this.push = push
  this.pop = pop
  this.peek = peek
  this.clear = clear
  this.length = length
}

/**
 * push() 该方法用于向栈压入元素
 * 向栈中压入一个新元素，将其保存在数组中变量top所对应的位置
 * 然后将 top + 1 让其指向数组中下一个空位置
 * @param {*} element
 */
function push (element) {
  this.dataStore[this.top++] = element
}

/**
 * pop() 该方法用于从栈顶推出元素
 * 返回栈顶元素，同时将变量top - 1
 */
function pop () {
  return this.dataStore[--this.top]
}

/**
 * peek() 该方法用于返回数组的第 top - 1 个位置的元素
 */
function peek () {
  return this.dataStore[this.top - 1]
}

/**
 * length() 该方法用于获取栈的长度
 * 返回当前top值即可获得栈内元素个数
 */
function length () {
  return this.top
}

/**
 * clear() 该方法用于清空栈
 * 将top设为0
 */
function clear () {
  this.top = 0
}

三、栈的应用 数制间的相互转换

我们可以利用栈将一个数字从一种数制转换为另一种数制。
假设想将数字n转换为以b为基数的数字，实现的算法如下：

最高位为 n%b，将此位压入栈。

使用 n/b 代替n。

重复步骤1和2，直到n等于0，且没有余数。

持续将栈内元素弹出，直到栈空，依次将这些元素排列即可。

此算法只针对基数为2-9的情况
代码实现如下：

function mulBase (num, base) {
  let s = new Stack()
  do {
    s.push(num % base)
    num = Math.floor(num /= base)
  } while (num > 0) {
    let converted = ""
    while (s.length() > 0) {
      converted += s.pop()
    }
    return converted
  }
}

回文

使用栈，我们可以判断一个字符串是否为回文。
字符串完整压入栈内后，通过持续弹出栈中的每一个字母就可以得到一个新的字符串，该字符串刚好与原来的字符串顺序相反。我们只需要比较两个字符串即可。如果相等，就是一个回文。

function isPalindrome (word) {
  let s = new Stack()
  for (let i = 0; i < word.length; ++i) {
    s.push(word[i])
  }
  let rword = ""
  while (s.length() > 0) {
    rword += s.pop()
  }
  if (word == rword) {
    return true
  } else {
    return false  
  }
}

结束语

以上就是对JavaScript实现栈的介绍。

参考资料：数据结构与算法JavaScript描述 第4章 栈

GPU云服务器云服务器前端基础前端基础教程前端零基础零基础前端

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/108010.html

前端进击的巨人（二）：栈、堆、队列、内存空间

摘要：中有三种数据结构栈堆队列。前端进击的巨人一执行上下文与执行栈，变量对象中解释执行栈时，举了一个乒乓球盒子的例子，来演示栈的存取方式，这里再举个栗子搭积木。对于基本类型，栈中存储的就是它自身的值，所以新内存空间存储的也是一个值。面试经常遇到的深浅拷贝，事件轮询，函数调用栈，闭包等容易出错的题目，究其原因，都是跟JavaScript基础知识不牢固有关，下层地基没打好，上层就是豆腐渣工程，...

edgardeng 2019-08-23 14:43 评论0 收藏0
学习JavaScript数据结构与算法（一）：栈与队列

摘要：之数组操作接下来就是数据结构的第一部分，栈。以字符串显示栈中所有内容方法的实现说明需要往栈中添加新元素，元素位置在队列的末尾。的前端乐园原文链接寒假前端学习学习数据结构与算法，栈与队列本系列的第一篇文章: 学习JavaScript数据结构与算法（一），栈与队列第二篇文章：学习JavaScript数据结构与算法（二）：链表第三篇文章：学习JavaScript数据结构与算法（三）：集合第...

Flink_China 2019-08-19 17:23 评论0 收藏0
前端基础进阶（一）：内存空间详细图解

摘要：一栈数据结构与不同，中并没有严格意义上区分栈内存与堆内存。引用数据类型的值是保存在堆内存中的对象。不允许直接访问堆内存中的位置，因此我们不能直接操作对象的堆内存空间。为了更好的搞懂变量对象与堆内存，我们可以结合以下例子与图解进行理解。 showImg(https://segmentfault.com/img/remote/1460000009784102?w=1240&h=683); ...

_Suqin 2019-08-21 18:30 评论0 收藏0
【进阶1-3期】JavaScript深入之内存空间详细图解

摘要：进阶期理解中的执行上下文和执行栈进阶期深入之执行上下文栈和变量对象但是今天补充一个知识点某些情况下，调用堆栈中函数调用的数量超出了调用堆栈的实际大小，浏览器会抛出一个错误终止运行。（关注福利，关注本公众号回复[资料]领取优质前端视频，包括Vue、React、Node源码和实战、面试指导）本周正式开始前端进阶的第一期，本周的主题是调用堆栈，今天是第3天。本计划一共28期，每期重点攻...

coordinate35 2019-08-23 13:47 评论0 收藏0
Meteor——以NodeJS为基础环境，MongoDB为数据环境的全栈开发平台！

摘要：当一个应用启动时，会自动加载这些库，为应用提供了一个基础环境。也就是说，模板文件只能包含以这三种标签为顶层标签的片段。在中，我们需要判断当前的具体运行环境，以便执行相应的代码。一、全栈开发平台 - 不仅仅是前端 Meteor和那些名声如雷贯耳的前端框架，比如Angular, React等都不一样，它是一个采用单一开发语言的全栈开发的平台：开发者可以使用JavaScript同时进...

chenatu 2019-06-26 16:55 评论0 收藏0