数据结构——栈结构_栈式结构

作者：小蓝xlanll | 2024-05-14 18:20:50

踩

栈式结构

栈结构

一、栈的概念
二、栈的基本操作
三、栈的应用

一、栈的概念

栈：栈结构只能在一端操作，该操作端叫做栈顶，另一端叫做栈底。栈结构按照“后进先出”（Last In First Out, LIFO）的方式处理结点数据。

典型的栈结构如下图所示：
在这里插入图片描述
举个例子，栈好比如我们生活的放盘子，先放的盘子在下方，后放的盘子在上方，只有先取出上面的盘子才可以取出下面的盘子，这就是栈的特性，先进后出。

二、栈的基本操作

在栈结构中只有栈顶的元素可以访问，这样栈结构的数据运行非常简单，一般栈结构的基本操作有两个：

入栈，将数据保存到栈顶，进行入栈操作前，先修改栈顶引用，使其向上移动一个元素单位，然后将数据保存到栈顶所指位置。
出栈，将栈顶数据数据弹出，通过修改栈顶引用，使其指向下一个元素。

push(element)：添加一个新元素到栈顶位置。
pop()：移除栈顶的元素，同时返回被移除的对象。
peek()：返回栈顶的元素，不对栈做任何操作（这个方法不会移除栈顶的元素，仅仅返回它）。
isEmpty()：如果栈里没有任何元素就返回true,否则返回false。
size()：返回栈里的元素个数。
tostring()：将栈结构的内容以字符串形式返回。

下面展示一下各个方法的简单运用：

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>
<body>
    <script>
        //封装栈类
        function Stack() {
            //栈中的属性
            this.items =[]
            //栈的相关操作
            //1.将元素压入栈
            Stack.prototype.push = function(element){
                this.items.push(element)
                }
            //2.从栈中取出元素
            Stack.prototype.pop = function(){
                this.items.pop()
            }
            //3.查看一下栈顶元素
            Stack.prototype.peek = function(){
                return this.items[this.items.length-1]
            }
            //4.判断栈是否为空
            Stack.prototype.isEmpty = function(){
                return this.items.length ==0
            }
            //5.获取栈中的元素
            Stack.prototype.size = function(){
                return this.items.length
            }
            //6.toString方法
            Stack.prototype.toString = function(){
                var resultString = ''
                for(var i = 0;i<this.items.length;i++){
                    resultString += this.items[i] + ''
                }
                return resultString;
            }
        }
        
        //栈的使用
        var s = new Stack()
        s.push(10)
        s.push(20)
        s.push(100)
        s.push(30)
        alert(s);

        s.pop()
        s.pop()
        alert(s);

        alert(s.peek());

        alert(s.isEmpty());

        alert(s.size());

        alert(s.toString())
    
    </script>
</body>
</html>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

输出结果如图：
在这里插入图片描述

三、栈的应用

1、十进制转为二进制
在现实生活中，我们经常使用十进制，然而在计算机科学中，二进制非常作用，因为计算机里的所有内容都是用二进制数字表示的（0和1），所以学习十进制转为二进制是很有必要的。但是如何实现十进制转为二进制那？
要把十进制转为二进制，我们可以将该十进制和2整除（二进制是满二进一），直到结果为0为止
举个例子，将100这样一个十进制的数字转化为二进制的数字，过程大概是这样：

计算100/2	余数0
计算50/2	余数0
计算25/2	余数1
计算12/2	余数0
计算6/2	余数0
计算3/2	余数1
计算1/2	余数1

最后，将所有的0和1数字从下往上整合起来（利用栈的思路）。就是十进制转化为二进制的结果：1100100

代码如下

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>
<body>
    <script>
 		 //函数：将十进制转为二进制
        function  dec2bin(dec){
            // 1.声明空数组
            const  bin=[]
            //2.循环操作
            while(dec > 0){
                //获取余数并放入数组中
                bin.push(dec % 2)
                //获取整除后的结果，作为下一次运行的数字
                dec = Math.floor(dec / 2)
            }
            //3.从我们栈中取出0和1
            let result = ''
            while(bin.length!=0){
                 result += bin.pop()
        }
        return result;
        }
        //3.测试
        alert(dec2bin(100));
        alert(dec2bin(10));
        alert(dec2bin(1000));  
    </script>
</body>
</html>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

得到的运行结果如下：
在这里插入图片描述

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小蓝xlanll/article/detail/569520