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

这篇具有很好参考价值的文章主要介绍了【数据结构】栈（Stack）与栈的模拟实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

🍀栈(Stack)

🎋栈的概念

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

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

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据在栈顶。

比如下面数据的出栈与进栈
【数据结构】栈（Stack）与栈的模拟实现,数据结构,数据结构,栈,模拟实现,java
就像枪的弹匣一样，先压进去的子弹，最后出来

🎍栈的使用

在java中，提供了这些方法用于操作栈
【数据结构】栈（Stack）与栈的模拟实现,数据结构,数据结构,栈,模拟实现,java
使用如下：

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是线程安全的
【数据结构】栈（Stack）与栈的模拟实现,数据结构,数据结构,栈,模拟实现,java
接下来我们模拟实现一个栈

🚩栈的创建

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

我们的这里的模拟栈用数组的形式给大家呈现
创建一个int型的elem数组
再创建一个usedSize的常数，用于记录栈中元素个数
再给一个构造方法，构造栈初始的长度

代码实现如下：

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];
    }
}

自定义异常

public class EmptyException extends RuntimeException{
    public EmptyException() {
    }

    public EmptyException(String message) {
        super(message);
    }
}