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

小鱼儿 2023-02-28 11:15 2阅读 0赞

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

*  [https://github.com/Lpyexplore/structureAndAlgorithm-JS][https_github.com_Lpyexplore_structureAndAlgorithm-JS]

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

>  *  公众号：**前端印象**
>  *  不定时有送书活动，记得关注~
>  *  关注后回复对应文字领取：【面试题】、【前端必看电子书】、【数据结构与算法完整代码】、【前端技术交流群】

### 数据结构——栈 ###

*  一、什么是栈
 *  二、栈结构的方法
 *  三、用代码实现一个栈结构
 *   *  （1）创建一个构造函数
     *  （2）实现push()方法
     *  （3）实现pop()方法
     *  （4）实现getTopElement()方法
     *  （5）实现isEmpty()方法
     *  （6）实现size()方法
     *  （7）实现toString()方法
 *  四、栈结构的实战应用
 *  五、总结

# 一、什么是栈 #

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

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

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

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

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

# 二、栈结构的方法 #

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

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

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

接下来，我们就用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)

经过上面操作后，栈内的情况是这样的：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ_size_16_color_FFFFFF_t_70 6]

## （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  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ_size_16_color_FFFFFF_t_70 7]

## （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后获得的余数连接起来，就是正确的二进制数，如下图  
![在这里插入图片描述][2020072110210531.png]  
所以，我们可以看到，最先获得的余数是最后才被取走的，这是一个很典型的栈结构的例子。每次除得的余数，就对其进行入栈操作，最后再进行多次出栈操作就可以实现十进制转二进制的功能了。

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

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**

*  [https://github.com/Lpyexplore/structureAndAlgorithm-JS][https_github.com_Lpyexplore_structureAndAlgorithm-JS]

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

[https_github.com_Lpyexplore_structureAndAlgorithm-JS]: https://github.com/Lpyexplore/structureAndAlgorithm-JS
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ_size_16_color_FFFFFF_t_70]: /images/20230209/7cf0e04d114d402d8823c66ed4f4eb32.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ_size_16_color_FFFFFF_t_70 1]: /images/20230209/72380866932c4a97bf77d95615a2684f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ_size_16_color_FFFFFF_t_70 2]: /images/20230209/8c8d1dde260647e18ed6a676ee4ff6cb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200721093326468.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200721093504953.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200721093551467.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200721095810879.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200721100237127.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xfUFBQ,size_16,color_FFFFFF,t_70
[2020072110210531.png]: https://img-blog.csdnimg.cn/2020072110210531.png