【数据结构】栈（Stack）与栈的模拟实现

Myth丶恋晨 2024-04-17 10:43 78阅读 0赞

#### 文章目录 ####

*  ?栈(Stack)
 *   *  ?栈的概念
     *  ?栈的使用
     *  ? 栈的模拟实现
     *   *  ?栈的创建
         *  ?栈是否为空
         *  ?压栈
         *  ?出栈
         *  ?获取栈顶元素
         *  ?MyStack完整代码实现
 *  ?概念区分（栈、虚拟机栈、栈帧）
 *  ⭕总结

## ?栈(Stack) ##

### ?栈的概念 ###

?栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。

***栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则***

*  压栈：栈的插入操作叫做进栈/压栈/入栈，***入数据在栈顶***。
 *  出栈：栈的删除操作叫做出栈。***出数据在栈顶***。
 *  ![在这里插入图片描述][c91e35886f2d498d84180125a7580d57.png]

比如下面数据的出栈与进栈  
![在这里插入图片描述][1211e1382f494e87a46c681b3ace7625.png]  
就像枪的弹匣一样，先压进去的子弹，最后出来  
![在这里插入图片描述][d7a9ce262e9f49f3aec298a52521edc2.png]

### ?栈的使用 ###

在java中，提供了这些方法用于操作栈  
![在这里插入图片描述][8c2afb54f76349b8a48222028281fea8.png]  
使用如下：

import java.util.Stack;
    
    public class Main {
        
        public static void main(String[] args) {
        
            Stack<Integer> s = new Stack();
            s.push(1);
            s.push(2);
            s.push(3);
            s.push(4);
            System.out.println(s.size()); // 获取栈中有效元素个数---> 4
            System.out.println(s.peek()); // 获取栈顶元素---> 4
            s.pop(); // 4出栈，栈中剩余1 2 3，栈顶元素为3
            System.out.println(s.pop()); // 3出栈，栈中剩余1 2 栈顶元素为3
            if(s.empty()){
        
                System.out.println("栈为空");
            }else{
        
                System.out.println(s.size());
            }
        }
    }

### ? 栈的模拟实现 ###

从下图中可以看到，Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的  
![在这里插入图片描述][2854d9fdf8a44b7d8c44f998b0994adf.png]  
接下来我们模拟实现一个栈

#### ?栈的创建 ####

我们创建一个MyStack的类，用于模拟实现我们的栈

*  我们的这里的模拟栈用数组的形式给大家呈现
 *  创建一个int型的elem数组
 *  再创建一个usedSize的常数，用于记录栈中元素个数
 *  ![在这里插入图片描述][b1aa554a7ed242b29805b8be097457e3.png]
 *  再给一个构造方法，构造栈初始的长度

代码实现如下：

public class MyStack {
        
        public int[] elem;
        public int usedSize;
    
        public MyStack() {
        
            this.elem = new int[10];
        }
    }

#### ?栈是否为空 ####

若usedSize为0则为空，所以直接比较返回就好

代码实现如下

public boolean isEmpty() {
        
            return usedSize == 0;
        }

#### ?压栈 ####

做法如下：

*  首先对现有栈进行判断是否为满，若满则需要进行扩容
 *  若没有满，则只需要将该元素放在数组elem下标为usedSize的位置
 *  然后usedSize加一即可

代码实现如下：

//压栈
        public void push(int val) {
        
            if(isFull()) {
        
                //扩容
                elem = Arrays.copyOf(elem,2*elem.length);
            }
            elem[usedSize++] = val;
        }
        public boolean isFull() {
        
            return usedSize == elem.length;
        }

#### ?出栈 ####

做法如下：

*  首先得判断栈是否为空，若为空我们需要抛出异常
 *  这里我们自定义一个异常为EmptyException如下

public class EmptyException extends RuntimeException{
        
        public EmptyException() {
        
        }
    
        public EmptyException(String message) {
        
            super(message);
        }
    }

*  若不为空，则usedSize变为usedSize-1
 *  然后返回usedSize下标的元素即可

代码实现如下：

//出栈
        public int pop() {
        
            if(isEmpty()) {
        
                throw new EmptyException("栈是空的！");
            }
            return elem[--usedSize];
        }
        public boolean isEmpty() {
        
            return usedSize == 0;
        }

#### ?获取栈顶元素 ####

做法如下：

*  我们同样需要对栈进行是否为空的判断
 *  若为空，抛出我们自定义栈为空的异常EmptyException
 *  若不为空，则返回数组elem下标为usedSize-1的元素

代码实现如下：

public int peek() {
        
            if(isEmpty()) {
        
                throw new EmptyException("栈是空的！");
            }
            return elem[usedSize-1];
        }

#### ?MyStack完整代码实现 ####

import java.util.Arrays;
    
    public class MyStack {
        
        public int[] elem;
        public int usedSize;
    
        public MyStack() {
        
            this.elem = new int[10];
        }
        //压栈
        public void push(int val) {
        
            if(isFull()) {
        
                //扩容
                elem = Arrays.copyOf(elem,2*elem.length);
            }
            elem[usedSize++] = val;
        }
        public boolean isFull() {
        
            return usedSize == elem.length;
        }
        //出栈
        public int pop() {
        
            if(isEmpty()) {
        
                throw new EmptyException("栈是空的！");
            }
            return elem[--usedSize];
        }
        public boolean isEmpty() {
        
            return usedSize == 0;
        }
        public int peek() {
        
            if(isEmpty()) {
        
                throw new EmptyException("栈是空的！");
            }
            return elem[usedSize-1];
        }
    }

自定义异常

## ?概念区分（栈、虚拟机栈、栈帧） ##

栈（stack） ：***是只允许在一端进行插入或删除的线性表，满足后入先出的特点。***

虚拟机栈 ：***逻辑结构，是具有特殊作用的一块内存空间 。 主管Java程序的运行，它保存方法的局部变量 (8种基本数据类型、对象的引用地址)、部分结果，并参与方法的调用和返回。***

栈帧 ：***函数从调用过程到结束的体现，一个函数从调用到销毁其中占用的空间，内部的局部变量统一放在栈帧中。 每个函数在运行时，jvm都会创建一个栈帧，然后将栈帧压入到虚拟机栈中，当函数调用结束时，该函数对应的栈帧会从虚拟机栈中出栈。***

## ⭕总结 ##

关于《 【数据结构】 栈（Stack）与栈的模拟实现》就讲解到这儿，感谢大家的支持，欢迎各位留言交流以及批评指正，如果文章对您有帮助或者觉得作者写的还不错可以点一下关注，点赞，收藏支持一下！

[c91e35886f2d498d84180125a7580d57.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/b78e1931d4d84512afaf4880c2717411.png
[1211e1382f494e87a46c681b3ace7625.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/3455ea131e5c4f369da21105dd2d4679.png
[d7a9ce262e9f49f3aec298a52521edc2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/4f9db3ace8cb44c296dcbdc656cb0773.png
[8c2afb54f76349b8a48222028281fea8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/e389bdbefcdf4dc0849a1cdc5447fa0b.png
[2854d9fdf8a44b7d8c44f998b0994adf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/eba3d734abd24212becf231b1ad2d226.png
[b1aa554a7ed242b29805b8be097457e3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/9fb80d1f2bee4b95972d772bdee58a1e.png