开发者社区> 一只空气猪> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

JavaScript 讲述数据结构 - 栈结构

简介: JavaScript 讲述数据结构 - 栈结构
+关注继续查看

什么是栈结构 ? 🤔


栈是一种非常常见的数据结构-并且在程序中的应用非常的广泛


我们可以用数组来做一个对比


数组

数组是一种线性结构,并且可以在数组的任意位置插入和删除数据


但是有时候我们为了实现某一种功能,必须对这种任意性加以限制


而队列和栈就是比较常见的受限制的线性结构


栈结构

栈结构只能在一端(栈顶【另一端叫做栈底】)


添加(进栈)和删除(出栈)元素(新元素进栈的过程叫做进栈操作)


LIFO(last in first out)后进先出(最后进栈的元素将会被第一个弹出栈空间)


什么是函数调用栈?

我们知道函数之间的相互调用:A 调用 B,B 调用 C,接着 C 又调用 D,这样的话,在执行过程中,先会将 A 压入栈,此时 A 是没有执行完毕的,所以不会弹出栈


在 A 执行过程中调用了 B,将 B 压入到栈,这个时候 B 在栈顶,A 在栈底


如果 B 执行完毕,那么 B 先弹出栈,A 再弹出栈,但是 B 没有执行完,B 又去调用了 C,C 没执行完又去调用了 D


那么栈顶到栈底现在为:A–>B–>C–>D–>

D 执行完先弹出栈,接着就是 C–>B–>A


我们经常会听到递归这个计算机名词,其实递归就是不断的自己调用自己,不会弹出栈,所以会有一个栈溢出的情况


栈结构练习


有六个元素 6、5、4、3、2、1 的顺序进栈,那么下面哪一个不是合法的出栈顺序


A. 5 4 3 6 1 2

B. 4 5 3 2 1 6

C. 3 4 6 5 2 1

D. 2 3 4 1 5 6

分析 A :


5 先出栈,那么必然 6 压栈了 --> 5 出去之后,4 进栈再出栈 --> 3 进栈再出栈 --> 然后 6 出栈 --> 接着就是 1 出栈,那么意味着 2 被压栈,所以 1 先出栈 2 再出栈,【正确】

分析 B :


4 先出栈,那么意味着 6,5 被压栈 --> 接着 5 出栈 --> 3 进栈,3 出栈 --> 2 进栈,2 出栈 --> 1 进栈,1 出栈 --> 6 出栈 【正确】

分析 C :


3 先出栈,那么意味着 6,5,4 被压栈 --> 然后 4 出栈 --> 接着 6 出栈,但是现在 6 被压栈,进栈时后进栈的 5 还没有出去,所以这就造成了错误 【错误】

分析 D :


2 先出栈,那么意味着 6,5,4,3 都被压栈 – 3 出栈 --> 4 出栈 --> 然后 1 进栈,1 出栈 --> 5 出栈 --> 6 出栈 【正确】


堆栈结构


'use strict'
// 封装栈类
function Stack() {
  // 栈中的属性
  this.items = []
  // 栈的常见操作
  // push(element):添加一个新元素到栈顶位置
  Stack.prototype.push = function (element) {
    this.items.push(element)
  }
  // pop():移除栈顶元素,同时返回被移除元素
  Stack.prototype.pop = function () {
    return this.items.pop()
  }
  // peek():返回栈顶元素,不对栈做任何修改
  Stack.prototype.peek = function () {
    return this.items[this.items.length - 1]
  }
  // isEmpty():如果栈里面没有任何元素就返回true
  Stack.prototype.isEmpty = function () {
    return this.items.length === 0
  }
  // size():返回栈里的元素个数
  Stack.prototype.size = function () {
    return this.items.length
  }
  // toString():将栈结构的内容以字符串的形式返回
  Stack.prototype.toString = function () {
    let resultString = ''
    for (let i = 0; i < this.items.length; i++) {
      resultString += this.items[i] + ' '
    }
    return resultString
  }
}
// 栈的使用
let s = new Stack()
// 验证
s.push(10)
s.push(9)
s.push(8)
s.push(7)
s.push(6)
s.push(5)
console.log(s.items)
// [ 10, 9, 8, 7, 6, 5 ]
s.pop()
s.pop()
console.log(s.items)
// [ 10, 9, 8, 7 ]
console.log(s.peek())
// 7
console.log(s.isEmpty())
// false
console.log(s.size())
// 4


计算机基础知识补充 – 基于栈理念理解十进制转二进制


在计算机中,二进制非常的重要,因为计算机里面所有的内容都是用二进制数字表示的


把十进制转换为二进制,我们可以将该十进制数字与 2 整除(二进制满二进一),知道结果为 0 为止


然后翻转取出余数,就是一个二进制数了


就像这样:


十进制数:100


100 / 2 = 50 …0


50 / 2 = 25 … 0


25 / 2 = 12 … 1


12 / 2 = 6 … 0


6 / 2 = 3 … 0


3 / 2 = 1 … 1


1 / 2 = 0 … 1


二进制:1100100


这就与栈有些类似了,依次得出元素,接着将最后存储的数字第一个拿出来进行排序,形成一个进栈出栈的原理


封装进制转换方法


function DecToBin(decNumber) {
  let stack = new Stack()
  while (decNumber > 0) {
    stack.push(decNumber % 2)
    decNumber = Math.floor(decNumber / 2)
  }
  let binString = ''
  while (!stack.isEmpty()) {
    binString += stack.pop()
  }
  return binString
}
console.log(DecToBin(100))
console.log(DecToBin(128))
console.log(DecToBin(800))
console.log(DecToBin(10))
// 1100100
// 10000000
// 1100100000
// 1010

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
【数据结构】树的概念与结构 | 树的几种常见表示方法
本章将正式开启数据结构中 “树” 部分的讲解,本章将介绍树的概念和结构,以及树的表示方法。
0 0
数据结构(初阶)—— 二叉树② ---链式结构(2)
数据结构(初阶)—— 二叉树② ---链式结构(2)
0 0
数据结构(初阶)—— 二叉树② ---链式结构(1)
数据结构(初阶)—— 二叉树② ---链式结构(1)
0 0
【数据结构和算法】图的各类概念与图的存储结构(还有十字链表与邻接多重表的介绍)
【数据结构和算法】图的各类概念与图的存储结构(还有十字链表与邻接多重表的介绍)
0 0
数据结构学习笔记——图的存储结构(邻接矩阵和邻接表)
数据结构学习笔记——图的存储结构(邻接矩阵和邻接表)
0 0
《数据结构》c语言版学习笔记——单链表结构(线性表的链式存储结构Part1)
《数据结构》c语言版学习笔记——单链表结构(线性表的链式存储结构Part1)
0 0
【数据结构】图的存储结构—邻接表
【数据结构】图的存储结构—邻接表
0 0
【数据结构】图的存储结构—邻接矩阵
【数据结构】图的存储结构—邻接矩阵
0 0
最最容易实现的链表结构——双向链表(数据结构C语言实现4)
最最容易实现的链表结构——双向链表(数据结构C语言实现4)
0 0
C语言 | 数据结构——数据类型与算法
一个有限指令集接受一些输入(有些情况下不需要输入)产生输出一定在有限步骤之后终止每一条指令必须有充分明确的目标,不能有歧义在计算机能处理的范围只能描述应不依赖于任何一种计算机语言以及具体的实现手段。
0 0
文章
问答
文章排行榜
最热
最新
相关电子书
更多
Apache Flink 流式应用中状态的数据结构定义升级
立即下载
如何使用Tair增强数据结构构建丰富在线实时场景
立即下载
JavaScript 语言在引擎级别的执行过程
立即下载