程序员社区

【数据结构与算法】详解什么是栈,并用代码手动实现一个栈结构

本系列文章【数据结构与算法】所有完整代码已上传 github,想要完整代码的小伙伴可以直接去那获取,可以的话欢迎点个Star哦~下面放上跳转链接

栈结构是一种非常常见的数据结构,并且在很多场景下也被用到。其实栈结构跟数组结构很像,只是在数组的基础上,对栈结构做了一些限制,本文我们将对其进行详细的介绍。
在这里插入图片描述

一、什么是栈

上面是说了,相对于数组结构做了一些限制。在使用数组结构的时候,我们可以任意的取出数组内的任何元素,也可以随意在指定位置插入元素,而却对元素的获取插入做了一些限制。

我们可以形象地把栈理解成一个没有盖子的茶杯,例如下图
在这里插入图片描述
杯口的位置叫做栈顶
杯底的位置叫做栈底

现在我们往被子里放入一个物体,这个操作叫做入栈,这也就相当于我们向栈内插入一个元素
在这里插入图片描述
我们再进行一次入栈操作,结果如下
在这里插入图片描述
此时,我们想要从杯子里拿出一个物体,可以很明显的看到,物体1物体2盖住了,所以我们只能先拿到 物体2,所以,我们就把 物体2 取出了,这样的操作成为出栈,结果如下
在这里插入图片描述
此时再进行一次出栈操作,就把 物体1 拿出来了,此时栈就为空了,结果如下:
在这里插入图片描述

看了上面的讲解,相信你们对栈结构有了很深刻的印象,所以这里我来总结一下:

  • 栈是一种受限的线性数据结构,它对元素的操作遵循的是先进后出,也就是向入栈的元素会比后入栈的元素晚一点取出来。

二、栈结构的方法

我们都知道像数组结构,都有一些操作元素的方法,例如在末尾插入元素 、在头部插入元素 、删除指定位置的元素等等,同样的,栈结构也是有它自己的操作元素的方法的,接下来我们就来介绍一下,栈结构常用的操作元素的方法有哪些吧。

方法 含义
push() 入栈操作
pop() 出栈操作
getTopElement() 返回栈顶的元素,但不会移除栈顶的元素
isEmpty() 查看栈是否为空
size() 返回栈内元素的个数
toString() 以字符串的形式展示栈内的所有元素

三、用代码实现一个栈结构

接下来,我们就用JavaScript封装实现一个基于数组的栈结构的类,因为是基于数组实现的栈,所以我们可以把数组的头部看作是栈底,把数组的尾部看作是栈顶

(1)创建一个构造函数

首先就是声明一个构造函数Stack,然后并在内部创建一个空数字,用于储存数据元素

function Stack() {
   
    //属性
    this.list = []
}

(2)实现push()方法

push()方法就是进行入栈操作,所以我们需要向栈顶(数组的尾部)插入元素

接下来我们来单独实现一下该方法

function Stack() {
   
    //属性
    this.list = []

    //push()方法的实现
    Stack.prototype.push = function (e) {
   
        this.list.push(e)
    }
}

我们来使用一下该方法

let stack = new Stack()
stack.push(3)
stack.push(9)
stack.push(5)

经过上面操作后,栈内的情况是这样的:
在这里插入图片描述

(3)实现pop()方法

pop()方法就是进行出栈操作,所以我们需要取出栈顶的第一个元素(数组的尾部),并返回取出的元素

接下来我们就来实现一下该方法

function Stack() {
   
    //属性
    this.list = []

    //pop()方法的实现
    Stack.prototype.pop = function (e) {
   
        return this.list.pop()
    }
}

我们来使用一下该方法

let stack = new Stack()
//先按 3 9 5 的顺序入栈,再进行出栈操作
stack.push(3)
stack.push(9)
stack.push(5)

stack.pop()        //返回 5

此时栈内的情况是这样的,元素5被取出,此时栈顶第一个为元素9
在这里插入图片描述

(4)实现getTopElement()方法

getTopElement()方法就相当于是查看一下栈顶的元素是什么(查看数组尾部的元素),而不会对栈内元素进行任何的入栈或出栈操作

我们来实现一下该方法

function Stack() {
   
    //属性
    this.list = []

    //getTopElement()方法的实现
    Stack.prototype.getTopElement = function () {
   
        return this.list[this.list.length - 1]
    }
}

我们来使用一下该方法

let stack = new Stack()
//先按 3 9 5 的顺序入栈,再查看一下栈顶元素是什么
stack.push(3)
stack.push(9)
stack.push(5)

stack.getTopElement()     //返回 5

(5)实现isEmpty()方法

isEmpty()方法就是看看栈内是否有元素(查看数组是否为空),有的话就返回 false,没有就返回 true

我们来实现一下该方法

function Stack() {
   
    //属性
    this.list = []

    //isEmpty()方法的实现
    Stack.prototype.isEmpty = function () {
   
        let size = this.list.length
        if(size === 0) {
   
            return true
        }
        else {
   
            return false
        }
    }
}

我们来使用一下该方法

let stack = new Stack()

stack.isEmpty()    // true,因为此时还没有插入元素

stack.push(3)

stack.isEmpty()   // false,将 3 入栈了,所以栈不会空,返回false

(6)实现size()方法

size()方法就是查看栈内有多少元素(查看数组的长度)并返回

我们来实现一下该方法

function Stack() {
   
    //属性
    this.list = []

    //size()方法的实现
    Stack.prototype.size = function () {
   
        return this.list.length
    }
}

我们来使用一下该方法

let stack = new Stack()

stack.size()       // 0,因为还没进行过入栈操作

stack.push(4)
stack.push(7)

stack.size()       // 2,因为栈内有两个元素,所以返回 2

(7)实现toString()方法

toString()方法就是将栈内的元素用字符串的方式展示出来(将数组转化成字符串)并返回

我们来实现一下该方法

function Stack() {
   
    //属性
    this.list = []

    //toString()方法的实现
    Stack.prototype.toString = function () {
   
        let string = ''
        for(let i in this.list) {
   
            string += `${
     this.list[i]} `
        }
        return string
    }
}

我们来使用一下该方法

let stack = new Stack()

stack.push(3)
stack.push(9)
stack.push(5)

stack.toString()        // 返回 3 9 5

四、栈结构的实战应用

现在需要通过栈结构实现一个函数,将输入的十进制转化成二进制

我们都知道,十进制转二进制是将一个数每次都除以2,一直到无法再除以2以后,倒着将每次除以2后获得的余数连接起来,就是正确的二进制数,如下图
在这里插入图片描述
所以,我们可以看到,最先获得的余数是最后才被取走的,这是一个很典型的栈结构的例子。每次除得的余数,就对其进行入栈操作,最后再进行多次出栈操作就可以实现十进制转二进制的功能了。

因此我们来封装一下这样一个函数

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()
    }
}

我们来使用一下这个函数,看看是否正确

d2b(100)           //返回 1100100

好了,这个例子的功能函数封装完成了

五、总结

栈结构的讲解就到这里了,希望大家对栈结构有了更深一层的理解。下一篇文章我将讲解一下队列

大家可以关注我,之后我还会一直更新别的数据结构与算法的文章来供大家学习,并且我会把这些文章放到【数据结构与算法】这个专栏里,供大家学习使用。

然后大家可以关注一下我的微信公众号:前端印象,等这个专栏的文章完结以后,我会把每种数据结构和算法的笔记放到公众号上,大家可以去那获取。

或者也可以去我的github上获取完整代码,欢迎大家点个Star

我是Lpyexplore,创作不易,喜欢的加个关注,点个收藏,给个赞~ 带你们在Python爬虫的过程中学习Web前端

赞(0) 打赏
未经允许不得转载:IDEA激活码 » 【数据结构与算法】详解什么是栈,并用代码手动实现一个栈结构

一个分享Java & Python知识的社区