阅读 29

数据结构与算法-栈(Stack)

栈(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
}
复制代码

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

关注下面的标签,发现更多相似文章
评论