my canteen
登录       注册

您现在的位置是:网站首页 > 学无止境

数据结构之栈结构

王伟2020年8月11日175人围观
简介认识栈结构 使用ES6语法对栈结构进行封装

数据结构之栈结构

一. 认识栈结构

栈结构

栈(stack),它是一种运算受限的线性表,后进先出(LIFO)

  • 1.LIFO(last in first out)表示就是后进入的元素, 第一个弹出栈空间. 类似于自动餐托盘, 最后放上的托盘, 往往先把拿出去使用.
  • 2.其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。
  • 3.向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;
  • 4.从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。

生活中类似于栈的

  • 1.自助餐的托盘, 最新放上去的, 最先被客人拿走使用.
  • 2.收到很多的邮件(实体的), 从上往下依次处理这些邮件. (最新到的邮件, 最先处理)
  • 3.注意: 不允许改变邮件的次序, 比如从最小开始, 或者处于最紧急的邮件, 否则就不再是栈结构了. 而是队列或者优先级队列结构.

程序中什么是使用栈实现的呢?

  • 学了这么久的编程, 是否听说过, 函数调用栈呢?
  • 我们知道函数之间和相互调用: A调用B, B中又调用C, C中又调用D.
  • 那样在执行的过程中, 会先将A压入栈, A没有执行完, 所有不会弹出栈.
  • 在A执行的过程中调用了B, 会将B压入到栈, 这个时候B在栈顶, A在栈底.
  • 如果这个时候B可以执行完, 那么B会弹出栈. 但是B有执行完吗? 没有, 它调用了C.
  • 所以C会压栈, 并且在栈顶. 而C调用了D, D会压入到栈顶.
  • 所以当前的栈顺序是: 栈顶A->B->C->D栈顶
  • D执行完, 弹出栈. C/B/A依次弹出栈.
  • 所以我们有函数调用栈的称呼, 就来自于它们内部的实现机制. (通过栈来实现的)

函数调用栈图解:

栈面试题

题目答案: C

  • A答案: 65进栈, 5出栈, 4进栈出栈, 3进栈出栈, 6出栈, 21进栈,1出栈, 2出栈
  • B答案: 654进栈, 4出栈, 5出栈, 3进栈出栈, 2进栈出栈, 1进栈出栈, 6出栈
  • D答案: 65432进栈, 2出栈, 3出栈, 4出栈, 1进栈出栈, 5出栈, 6出栈

二. 栈结构实现

我们先来创建一个栈的类, 用于封装栈相关的操作

class Stack {
  constructor() {
    this.items = []
  }
}

栈的操作

栈常见有哪些操作呢?
  • push(element): 添加一个新元素到栈顶位置.
  • pop():移除栈顶的元素,同时返回被移除的元素。
  • peek():返回栈顶的元素,不对栈做任何修改(这个方法不会移除栈顶的元素,仅仅返回它)。
  • isEmpty():如果栈里没有任何元素就返回true,否则返回false
  • clear():移除栈里的所有元素。
  • size():返回栈里的元素个数。这个方法和数组的length属性很类似。
push方法
  • 注意: 我们的实现是将最新的元素放在了数组的末尾, 那么数组末尾的元素就是我们的栈顶元素
push(ele) {
    this.items.push(ele)
}
pop方法
  • 注意: 出栈操作应该是将栈顶的元素删除, 并且返回.
  • 因此, 我们这里直接从数组中删除最后一个元素, 并且将该元素返回就可以了
// 出栈操作
pop() {
    return this.items.pop()
}
peek方法
  • peek方法是一个比较常见的方法, 主要目的是看一眼栈顶的元素.
  • 注意: 和pop不同, peek仅仅的瞥一眼栈顶的元素, 并不需要将这个元素从栈顶弹出.
peek() {
    return this.items[this.items.length - 1]
 }
isEmpty方法
  • isEmpty方法用户判断栈中是否有元素.
  • 实现起来非常简单, 直接判断数组中的元素个数是为0, 为0返回true, 否则返回false
isEmpty() {
    return this.items.length == 0
 }
size方法
  • size方法是获取栈中元素的个数.
  • 因为我们使用的是数组来作为栈的底层实现的, 所以直接获取数组的长度即可.(也可以使用链表作为栈的顶层实现)
size() {
    return this.items.length
 }

完整代码

export class Stack {
  constructor() {
    this.items = []
  }
  push(ele) {
    this.items.push(ele)
  }
  pop() {
    return this.items.pop()
  }
  peek() {
    return this.items[this.items.length - 1]
  }
  isEmpty() {
    return this.items.length == 0
  }
  size() {
    return this.items.length
  }
}

栈的使用

我们来使用封装的栈, 模拟刚才的面试题
  • 我们做了一下A, 其他大家可以自己练习一下.
  • C是无法使用栈来模拟的, 因为不正确的是C
// 模拟面试题
var stack = new Stack()
// 情况下代码模拟
stack.push(6)
stack.push(5)
stack.pop()     // 5
stack.push(4)
stack.pop()     // 4
stack.push(3)
stack.pop()     // 3
stack.pop()     // 6
stack.push(2)
stack.push(1)
stack.pop()     // 1
stack.pop()     // 2

三. 栈结构应用

十进制转二进制

为什么需要十进制转二进制?

  • 现实生活中,我们主要使用十进制。
  • 但在计算科学中,二进制非常重要,因为计算机里的所有内容都是用二进制数字表示的(0和1)。
  • 没有十进制和二进制相互转化的能力,与计算机交流就很困难。

如何实现十进制转二进制?

  • 要把十进制转化成二进制,我们可以将该十进制数字和2整除(二进制是满二进一),直到结果是0为止。
  • 举个例子,把十进制的数字10转化成二进制的数字,过程大概是这样:

代码实现

function dec2bin(num) {
  const stack = new Stack()
  while (num > 0) {
    let remainder = num % 2;
    num = Math.floor(num / 2)
    stack.push(remainder)
  }
  let bin = ''
  while (!stack.isEmpty()) {
    bin += stack.pop()
  }
  console.log(bin)
  console.log(stack)
}
测试
console.log(dec2bin(100)) //1100100
console.log(dec2bin(1000)) //1111101000
console.log(dec2bin(50)) //110010

完美结束

路漫漫其修远兮 吾将上下而求索

原版链接:https://www.jianshu.com/p/eade026ffaf5

通过coderwhy老师的文章学习 使用ES6语法对代码进行重新封装


文章评论

来说句话吧.... 共有评论数:0条


微信二维码 博主微信 qq二维码 博主QQ
177****8743
7*24小时电话