数据结构 - 栈结构详解

哈喽,大家好，我是xy👨🏻‍💻. 这篇文章：数据结构之栈结构详解 将是我 《javaScript数据结构》系列的第二篇文章；2022 年的 Flag：学习数据结构、算法、设计模式，如果你也想和我一起学习，欢迎加我为好友，拉你进数据结构算法设计模式学习群一起学习交流 ❤️

什么是栈结构

栈是一种特殊的线性表,它的存储空间是连续的。

栈的操作只能在表尾进行,因此栈的特点有一个是 “先入后出”（LIFO）

栈的头部,叫做栈底,有一个指针始终指向栈底。

栈的最后一个元素,叫做栈顶,也有一个指针指着。

加入元素时,会在栈尾加入,叫做 ： 进栈,入栈,或压栈。元素入栈后，尾指针会指向它的地址。

删除元素时,删除尾部最后一个,叫做出栈或退栈。

栈的操作

栈常见有哪些操作呢?

• push(element): 添加一个新元素到栈顶位置.
• pop()：移除栈顶的元素，同时返回被移除的元素。
• getTopElement()：返回栈顶的元素，不对栈做任何修改（这个方法不会移除栈顶的元素，仅仅返回它）。
• isEmpty()：如果栈里没有任何元素就返回 true，否则返回 false。
• size()：返回栈里的元素个数，这个方法和数组的 length 属性很类似。
• toString()：展示当前栈内所有元素

用 js 代码实现栈

function Stack() {
  this.list = [];

  //入栈
  Stack.prototype.push = function (e) {
    this.list.push(e);
  };
  //出栈
  Stack.prototype.pop = function (e) {
    return this.list.pop();
  };
  //获取栈顶元素
  Stack.prototype.getTopElement = function () {
    return this.list[this.list.length - 1];
  };
  //判断栈是否为空
  Stack.prototype.isEmpty = function () {
    let size = this.list.length;
    if (size === 0) {
      return true;
    } else {
      return false;
    }
  };
  //判断栈内元素个数
  Stack.prototype.size = function () {
    return this.list.length;
  };
  //展示当前栈内所有元素
  Stack.prototype.toString = function () {
    let string = "";
    for (let i in this.list) {
      string += `${this.list[i]} `;
    }
    return string;
  };
}

export default Stack;

栈结构应用

以下使用一个比较经典的实列：十进制转二进制 来进一步讲解栈结构应用

现实生活中，我们主要使用十进制。 但在计算科学中，二进制非常重要，因为计算机里的所有内容都是用二进制数字表示的（0 和 1）。

要把十进制转化成二进制，我们可以将该十进制数字和2整除（二进制是满二进一），直到结果是0为止。

举个例子，把十进制的数字168转化成二进制的数字，过程大概是这样：

代码实现十进制转二进制

//输入需要转化的十进制数
function d2b(number) {
    let stack = new Stack()
    while (number > 0) {
        stack.push(number % 2)
        number = Math.floor(number / 2)
    }

    let string = ''
    while (!stack.isEmpty()) {
        string += stack.pop()
    }

    return string
}

console.log(d2b(168)) // 10101000

写在最后

公众号：前端开发爱好者 专注分享 web 前端相关技术文章、视频教程资源、热点资讯等，如果喜欢我的分享，给 🐟🐟 点一个赞 👍 或者 ➕关注 都是对我最大的支持。

欢迎长按图片加好友，我会第一时间和你分享前端行业趋势，面试资源，学习途径等等。

关注公众号后，在首页：

• 回复面试题，获取最新大厂面试资料。
• 回复简历，获取 3200 套 简历模板。
• 回复React实战，获取 React 最新实战教程。
• 回复Vue实战，获取 Vue 最新实战教程。
• 回复ts，获取 TypeScript 精讲课程。
• 回复vite，获取 精讲课程。
• 回复uniapp，获取 uniapp 精讲课程。
• 回复js书籍，获取 js 进阶 必看书籍。
• 回复Node，获取 Nodejs+koa2 实战教程。
• 回复数据结构算法，获取 数据结构算法 教程。
• 回复架构师，获取 架构师学习资源教程。
• 更多教程资源应用尽有，欢迎关注获取