周亚博的个人博客

  • 首页
  • 盛夏光年
  • 陪风去荡
  • 布响丸啦
我频繁记录着 因为生活值得
  1. 首页
  2. 陪风去荡
  3. 正文

数据结构——栈

2022-08-11 61点热度 0人点赞 0条评论

一、什么是栈结构

1、栈是一种非常常见的数据结构,应用十分广泛

  • 数组是一种线性结构,可以在任意位置添加和删除元素
  • 栈和队列则是一种受限的线性结构,没有数组的任意性

2、结构示意图

image-20220809213925881

栈结构只能从一端(栈顶)添加和删除元素,遵从后进先出的原则

二、栈的应用

函数调用栈

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依次弹出栈.

所以我们有函数调用栈的称呼, 就来自于它们内部的实现机制(通过栈来实现的)

三、栈结构面试题

题目:6个元素6、5、4、3、2、1顺序进栈(不是一次性进栈),哪个是不合法的出栈序列(C)

  • 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

四、栈的常见操作

push(element): 添加一个新元素到栈顶位置.

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

peek():返回栈顶的元素,不对栈做任何修改(这个方法不会移除栈顶的元素,仅仅返回它)。

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

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

size():返回栈里的元素个数。这个方法和数组的length属性很类似。

toString():将栈结构内容以字符串形式返回

五、栈结构的实现

实现栈结构有两种是实现方式:

  • 基于数组实现
  • 基于链表实现
// 封装一个栈类
function Stack() {
  // 栈中的属性
  this.items = []
  /**
  *  相关操作
  */
  // 1、压栈
  Stack.prototype.push = function (element) {
    this.items.push(element)
  }
  // 2、弹栈
  Stack.prototype.pop = function () {
    return this.items.pop()
  }
  // 3、查看栈顶元素
  Stack.prototype.peek = function () {
    return this.items[this.items.length - 1]
  }
  // 4、判断栈是否为空
  Stack.prototype.isEmpty = function () {
    return this.items.length == 0
  }
  // 5、获取栈元素的个数
  Stack.prototype.size = function () {
    return this.items.length
  }
  // 6、toString()方法
  Stack.prototype.toString = function () {
    let str = ''
    for (let i = 0; i < this.items.length; i++) {
      str += this.items[i] + ' '
    }
    return str
  }
}

// 使用
let s = new Stack()

s.push(20)
s.push(10)
s.push(100)
s.push(4)
console.log(s)  // Stack { items: [ 20, 10, 100, 4 ] }
s.pop()
console.log(s)  // Stack { items: [ 20, 10, 100 ] }
console.log(s.size())  // 3
console.log(s.isEmpty())  // false
console.log(s.toString()) // 20 10 100

六、栈的应用

实现十进制转二进制(使用上述封装的栈方法)

// 封装一个十进制转二进制的方法
function decTobin(decNumber) {
  // 定义一个栈对象保存过程中的余数
  let stack = new Stack()
  // 循环操作
  while (decNumber > 0) {
    // 获取余数存入栈中
    stack.push(decNumber % 2)
    // 获取整除结果作为下次求余的数字
    decNumber = Math.floor(decNumber / 2)
  }
  // 从栈中取出余数就是二进制结果
  let binsryString = ''
  while (!stack.isEmpty()) {
    binsryString += stack.pop()
  }
  return binsryString
}

console.log(decTobin(100))  // 1100100
console.log(decTobin(10))   // 1010
console.log(decTobin(1000)) // 1111101000
标签: 数据结构 栈
最后更新:2022-08-11

粥呀Bo

所谓惊喜,就是苦苦等候的兔子来了,后面却跟着狼

点赞
< 上一篇
下一篇 >

文章评论

取消回复
目录
  • 一、什么是栈结构
  • 二、栈的应用
  • 三、栈结构面试题
  • 四、栈的常见操作
  • 五、栈结构的实现
  • 六、栈的应用

COPYRIGHT © 2022 zhouyaker.cn. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS

陕ICP备2022009272号