数据结构与算法-栈（Stack）

曾经终败给现在 2022-10-01 05:56 169阅读 0赞

> 栈（stack）又名堆栈，它是一种运算受限的线性表

> 定义：栈是限定仅在表头进行插入和删除操作的线性表。要搞清楚这个概念，首先要明白”栈“原来的意思，如此才能把握本质。"栈“者,存储货物或供旅客住宿的地方,可引申为仓库、中转站，所以引入到计算机领域里，就是指数据暂时存储的地方，所以才有进栈、出栈的说法。

> 比如我们在洗盘子时，一碟盘子可以想象成一个栈，只能从最上面取盘子，盘子洗净后，放在另一个地方也只能摞在盘子的最上面。这种后入先出（LIFO，last-in-first-out）的数据结构被称为栈。

# 栈的实现 #

> 实现一个栈，就得决定存储数据的底层数据结构，这里采用数组。

// 实现Stack类的构造函数
    function Stack () {
        this.dataStore = [] // 保存栈内元素
        this.top = 0 // 记录栈顶位置
    }
    Stack.prototype = {
        constructor: Stack,
        push: function (element) {
            this.dataStore[this.top] = element
            this.top++
        },
        pop: function () {
            return this.dataStore[--this.top]
        },
        peek: function () {
            return this.dataStore[this.top - 1]
        },
        length: function () {
            return this.top
        },
        clear: function () {
            this.top = 0
        }
    }
    复制代码

# 栈的应用 #

## 1.回文 ##

> 一个单词，短语或数字，从前往后写和从后往前写都是一样的，就是回文。

> 将拿到的字符串的每个字符按照从左到右的顺序压入栈，当字符串中的字符都入栈后，栈内就保存了一个反转后的字符串，判断两个字符串是否相等即可。

function isPalindrome (word) {
        var s = new Stack()
        for (var i = 0; i < word.length; i++) {
            s.push(word[i])
        }
        var rword = ''
        while (s.length() > 0) {
            rword += s.pop()
        }
        if (word === rword) {
            return true
        } else {
            return false
        }
    }
    复制代码

## 2.递归演示 ##

> 用栈模拟实现递归

> 首先将数字从5到1压入栈，然后使用一个循环，将数字挨个弹出连乘。

// 5! = 5 * 4 * 3 * 2 * 1
    function fact(n) {
        var s = new Stack()
        while (n > 1) {
            s.push(n--)
        }
        var product = 1
        while (s.length() > 0) {
            product *= s.pop()
        }
        return product
    }
    复制代码

### 栈是一种思想，对数据的处理逻辑，比如在生活中的做事情的先后顺序。计算机是人开发出来的，可以把计算机想象成一个人在做事情，只是它按照人为事先定义好的程序执行，所以机器做事时如果对某一资源有先后关系，比如栈这种后入先出，就要按照栈（这种思想，人为抽象出来叫栈，所以不要纠结它为什么叫栈）执行 ###

转载于:https://juejin.im/post/5ce7cdb3f265da1bbc6fb03b