JavaScript实现栈结构（Stack）

Js实现栈结构

一、前言

1.1 什么是数据结构

数据结构就是在计算机中，存储和组织数据的方式。
例如：图书管理，怎样摆放图书才能既能放很多书，也方便取？

常见的数据结构：

• 栈（Stack）
• 队列（Queue）
• 链表（Linked List）
• 集合（Set）
• 哈希（Hash）
• 树（Tree）
• 图（Graph）

1.2 什么是算法

算法通俗理解：解决问题的办法/步骤逻辑。数据结构的实现，离不开算法。

二、栈（Stack）

2.1 简介

我们知道数组是一个线性结构，并且可以在数组的任意位置插入和删除元素。而栈和队列就是比较常见的受限的线性结构，栈遵循LIFO（先进后出，后进先出）的原则。

程序中的栈结构：

递归：为什么没有停止条件的递归会造成栈溢出？比如函数A为递归函数，不断地调用自己（因为函数还没有执行完，不会把函数弹出栈），不停地把相同的函数A压入栈，最后造成栈溢出（Stack Overfloat）。

栈的常见操作：

• push：添加一个新元素
• pop：移除栈顶的元素，同时返回被移除的元素
• peek：返回栈顶的元素，不对栈做任何修改
• isEmpty：如果栈里没有任何元素就返回true，否则返回false
• size：返回栈里的元素个数
• toString：将栈结构的内容以字符串的形式返回

2.2 js封装栈

代码实现：

function Stack() {
        this.items = [];
        // 压入栈
        Stack.prototype.push = function (element) {
          this.items.push(element);
        };
        // 栈中取出元素
        Stack.prototype.pop = function () {
          return this.items.pop();
        };
        // 查看栈顶元素
        Stack.prototype.peek = function () {
          return this.items[this.items.length - 1];
        };
        // 判断栈是否为空
        Stack.prototype.empty = function () {
          return this.items.length == 0;
        };
        // 栈中元素个数
        Stack.prototype.size = function () {
          return this.items.length;
        };
        // toString
        Stack.prototype.toString = function () {
          let resString = "";
          for (let i = 0; i < items.length; i++) {
            resString += this.items[i];
          }
          return resString;
        };
      }

场景应用：

// 10转2进制
      function dec2binb(decnumber) {
        let stack = new Stack();
        while (decnumber > 0) {
          stack.push(decnumber % 2);
          decnumber = Math.floor(decnumber / 2);
        }
        let binstring = "";
        while (!stack.empty()) {
          binstring += stack.pop();
        }
        return binstring;
      }

参考资料：B站视频