JS数据结构学习：栈

Alfred 发布于2019-08-26 13:28 / 1265人阅读

摘要：栈的应用前面介绍了那么多栈相关的知识，最后也是介绍栈的应用场景的时候了，栈的实际应用非常广泛，例如用来存储访问过的任务或路径撤销的操作。

栈的定义

什么是栈？栈是一种遵循后进先出原则的有序集合，新添加的或者待删除的元素都保存在栈的同一端，称为栈顶，另一端称为栈底，在栈里，新元素靠近栈顶，旧元素靠近栈底，用个图来看大概这样式的：

用一个更形象的例子来说明：上网的时候，每点击一个超链接，浏览器都会打开一个新的页面，并且压入到一个访问历史栈中，你可以不断的点击打开新的页面，但总是可以通过回退重新访问以前的页面，从浏览器的访问历史栈中弹出历史网页地址，从栈顶弹出，总是最新的最先弹出

栈的创建

首先创建一个类用来表示栈，接着声明一个数组用来保存栈里的元素：

function Stack() {
  let items = []
  // 方法声明
}

创建好栈之后，需要为栈声明一些方法，栈一般会包含以下几个方法：

push(): 添加新元素到栈顶

pop(): 移除栈顶的元素，同时返回被移除的元素

peek(): 返回栈顶的元素，不对栈做任何修改

isEmpty(): 如果栈里没有任何元素就返回true，否则返回false

clear(): 移除栈里的所有元素

size(): 返回栈里的元素个数

具体实现：

function Stack() {
  let items = []
  // 添加元素到栈顶，也就是栈的末尾
  this.push = function (element) {
    items.push(element)
  }
  // 栈的后进先出原则，从栈顶出栈
  this.pop = function () {
    return items.pop()
  }
  // 查看栈顶的元素，访问数组最后一个元素
  this.peek = function () {
    return items[items.length - 1]
  }
  // 检查栈是否为空
  this.isEmpty = function () {
    return items.length == 0
  }
  // 返回栈的长度，栈的长度就是数组的长度
  this.size = function () {
    return items.length
  }
  // 清空栈 
  this.clear = function () {
    items = []
  }
  // 打印栈元素
  this.print = function () {
    console.log(items.toString())
  }
}

栈的使用

现在我们来看如何使用栈：

let stack = new Stack()
stack.push(1)
stack.push(2)
stack.push(3)
console.log(stack.peek()) // 3
console.log(stack.isEmpty()) // false
console.log(stack.size()) // 3

先向栈中加入三个元素1，2，3，接下来用一张图来看一下入栈的过程：

入栈过程都是在栈顶依次入栈，接着调用peek方法返回栈顶元素3，isEmpty返回false，size返回栈的长度3，然后在继续调用pop来看看出栈的过程：

stack.pop()
stack.print() // 1,2

出栈也是和入栈相同，都是从栈顶开始出栈，保证栈的后入先出原则

es6声明Stack类

上面创建了一个Stack函数来充当类，并且在里面声明了一个私有变量，但是在es6里面是有类的语法的，可以直接用es6新语法来声明，代码大概是这样事的：

class Stack {
  constructor () {
    this.items = []
  }
  push (element) {
    this.items.push(element)
  }
  pop () {
    return this.items.pop()
  }
  peek () {
    return this.items[items.length - 1]
  }
  isEmpty () {
    return this.items.length == 0
  }
  size () {
    return this.items.length
  }
  clear () {
    this.items = []
  }
  print () {
    console.log(this.items.toString())
  }
}
let stack = new Stack()
stack.push(1)
console.log(stack.isEmpty())
stack.print()

看起来似乎不错，比之前要简单，关键是看起来更加合理，使用的是类的语法，调用也没有什么问题，但是如果这么执行呢？

console.log(stack.items)

会发现一个问题，在stack类外面可以直接访问类里面的属性，按照设计items应该是Stack类的私有属性才对，就像之前Stack函数里面的私有变量，是不能在外部访问的，如何才能将items变成私有属性呢？应该会有和我一样想法的人，使用闭包，在闭包里面里面定义私有属性，然后再将stack类返回回来，代码实现大概是这样的：

let Stack = (function () {
  let items = new WeakMap()
  class Stack {
    constructor () {
      items.set(this, [])
    }
    push (element) {
      let s = items.get(this)
      s.push(element)
    }
    pop () {
      let s = items.get(this)
      return s.pop()
    }
    peek () {
      let s = items.get(this)
      return s[s.length - 1]
    }
    isEmpty () {
      let s = items.get(this)
      return s.length == 0
    }
    size () {
      let s = items.get(this)
      return s.length
    }
    clear () {
      let s = items.get(this)
      s = []
    }
    print () {
      let s = items.get(this)
      console.log(s.toString())
    }
  }
  return Stack
})()

可能有人会问为什么这里要把items定义成一个WeakMap对象，先简单介绍一下WeakMap对象的用法，WeakMap对象是一对键/值对的集合，其键必须是对象，值可以是任意的，定义成WeakMap就是为了将items属性变成私有属性，在外部调用Stack对象的时候无法访问到items属性。

栈的应用

前面介绍了那么多栈相关的知识，最后也是介绍栈的应用场景的时候了，栈的实际应用非常广泛，例如用来存储访问过的任务或路径、撤销的操作。为了有一个更直观的应用了解，下面会介绍如何用来解决计算机中的进制转换问题，将10进制转换为其他进制数，可能不少人已经忘了如何进行进制转换了，下面先来看一个简单的10进制转2进制的过程:

上面的图中展示将一个10进制8转化为2进制数的过程，接下来看看用栈是如何实现的：

function conver(num, radix) {
  let stack = new Stack()
  let binaryString = ""
  let digits = "0123456789ABCDEF"
  while (num > 0) {
    stack.push(num % radix)
    num = parseInt(num / radix)
  }
  while (!stack.isEmpty()) {
    binaryString += digits[stack.pop()]
  }
  console.log(binaryString)
}
conver(8, 2) // 1000

总结

这篇文章主要对栈做了简单介绍，动手实践了栈的实现，以及用栈实现了一个简单进制转换的功能。如果有错误或不严谨的地方，欢迎批评指正，如果喜欢，欢迎点赞。

GPU云服务器云服务器 js技术栈 JS调用栈 js递归栈溢出 js数组栈方法

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

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

我对JS栈的简单学习

摘要：我对栈的学习因为是个新手，所以都是最简单的知识学习梳理。栈是一种遵从后进先出原则的有序集合，新添加的或者待删除的元素都保留在栈的末尾，称作栈顶，另一端叫做栈底。栈的学习栈的创建创建一个类来表示栈。对于栈来说只能用和方法来进行添加和删除元素。我对栈的学习因为是个新手，所以都是最简单的知识学习梳理。什么是栈数组是计算机科学中最常用的数据结构，是数据元素的集合。有时候我们需要一种添加...

Cobub 2019-08-21 11:36 评论0 收藏0
JS 栈

摘要：栈学习数据结构与算法读书笔记。栈又名堆栈，是一种遵循后进先出原则的有序集合。新添加或待删除的元素都保存在栈的末尾，称作栈顶，另一端称作栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。栈《学习JavaScript数据结构与算法》读书笔记。栈（stack）又名堆栈，是一种遵循后进先出（LIFO）原则的有序集合。新添加或待删除的元素都保存在栈的末尾，称作栈顶，另一端称作栈底。在栈里，...

Lin_R 2019-08-22 10:35 评论0 收藏0
全栈开发：2017年你最好的选择[翻译]

摘要：全栈开发是一个学习实现提高的过程。解除对开发人员的限制所有的职业都在持续的进化。哪怕是爆炸和拥挤的印度招聘市场，全栈工程师在年也非常的抢手。印度的创业公司已经开发意识到全栈工程师的重要意义，全栈会越来越重要。在不断壮大的招聘市场上，最需要的是有非常广泛技术栈的人。前言敬爱的读者，大家好。大家经常讨论的话题是作为一个软件工程师是一个持续学习的过程。因为现有的趋势和技术在软件领域会很...

fireflow 2019-07-25 11:32 评论0 收藏0
全栈开发：2017年你最好的选择[翻译]

摘要：全栈开发是一个学习实现提高的过程。解除对开发人员的限制所有的职业都在持续的进化。哪怕是爆炸和拥挤的印度招聘市场，全栈工程师在年也非常的抢手。印度的创业公司已经开发意识到全栈工程师的重要意义，全栈会越来越重要。在不断壮大的招聘市场上，最需要的是有非常广泛技术栈的人。前言敬爱的读者，大家好。大家经常讨论的话题是作为一个软件工程师是一个持续学习的过程。因为现有的趋势和技术在软件领域会很...

aisuhua 2019-08-20 14:32 评论0 收藏0
全栈开发：2017年你最好的选择[翻译]

摘要：全栈开发是一个学习实现提高的过程。解除对开发人员的限制所有的职业都在持续的进化。哪怕是爆炸和拥挤的印度招聘市场，全栈工程师在年也非常的抢手。印度的创业公司已经开发意识到全栈工程师的重要意义，全栈会越来越重要。在不断壮大的招聘市场上，最需要的是有非常广泛技术栈的人。前言敬爱的读者，大家好。大家经常讨论的话题是作为一个软件工程师是一个持续学习的过程。因为现有的趋势和技术在软件领域会很...

selfimpr 2019-07-25 13:51 评论0 收藏0