数据结构 模拟实现Stack栈（数组模拟）

目录

一、栈的概念

概念：栈是一种先进后出的数据结构，类似羽毛球桶，先放进去的羽毛球，后面才能拿出来        如图：

还有弹匣，先放进去的子弹后面发射出去，如图：

我们定义一个自己的栈类，里面有数组，存放数据，还有一个变脸usedSize，记录栈里的元素个数，带有构造方法，不带参数的给数组默认初始化10个元素，带参数就初始化你想要的元素个数，代码如下：

public class MyStack implements IStack{

    private int[] elem;
    private int usedSize;
    private int DEFAULT_CAPACITY = 10;

    public MyStack() {
        this.elem = new int[DEFAULT_CAPACITY];
    }
    public MyStack(int n) {
        this.elem = new int[n];
    }
}

二、栈的接口

代码如下：

public interface IStack {
    public void push(int x);
    public int  pop();
    public int peek();
    public int size();
    public boolean empty();
}

三、栈的方法实现

（1）push方法

此方法是放元素进栈里面，也就是入栈，因为我们有记录栈元素个数的usedSize变量，所以我们可以用这个变量充当入栈时，要放进elem数组的哪个下标，因为usedSize记录的栈的个数，在数组中对应的下标就是个数-1；

入栈前，要检查栈是否满了，满了就要扩容，没满就给elem数组的usedSize-1下标位置放入元素，放完后usedSize++。代码如下：

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

执行效果如下：

elem数组里面有3个数，正好是我们入栈的元素。

（2）pop方法

此方法是出栈方法，取出栈顶元素，取完后就删除栈顶元素；在取出栈顶元素前，要检查栈是否为空，如果是空就要抛异常，因为没有元素可以出栈了；如果栈不为空，就出栈顶元素，也就是取出elem数组下标为usedSize-1的位置，然后usedSize–，代码如下：

    public int pop() {
        if(usedSize == 0) {
            throw new EmptyException("栈空了");
        }
        int tmp = elem[usedSize - 1];
        usedSize--;
        return tmp;
    }
//异常类
public class EmptyException extends RuntimeException{
    public EmptyException(String msg) {
        super(msg);
    }
}

执行效果如下：

里面有元素的时候就正常出栈，空了就会抛异常。

（3）peek方法

peek翻译成中文就是瞄一眼的意思，此方法也是就拿到栈顶元素，但不会删掉栈顶的元素，里面的操作和pop一样，但不会usedSize–，代码如下：

    public int peek() {
        if(usedSize == 0) {
            throw new EmptyException("栈空了");
        }
        int tmp = elem[usedSize - 1];
        return tmp;
    }

执行效果如下：

一直打印的都是栈顶元素，说明没有出栈顶元素，只是拿栈顶元素。

（4）size方法

此方法是获取栈里的元素，所以这里直接返回usedSize就好了，代码如下：

    public int size() {
        return usedSize;
    }

执行效果如下：

（5）empty方法

此方法是判断栈是不是空的，所以直接判断usedSize==0就好了，返回这个表达式的结果，代码如下：

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

执行效果如下：

四、最终代码

//接口类
public interface IStack {
    public void push(int x);
    public int  pop();
    public int peek();
    public int size();
    public boolean empty();
}

//自定义MyStack类
public class MyStack implements IStack{

    private int[] elem;
    private int usedSize;
    private int DEFAULT_CAPACITY = 10;

    public MyStack() {
        this.elem = new int[DEFAULT_CAPACITY];
    }
    public MyStack(int n) {
        this.elem = new int[n];
    }

    @Override
    public void push(int x) {
        if(full()) {
            //扩容
            elem = Arrays.copyOf(elem, elem.length * 2);
        }
        elem[usedSize++] = x;
    }
    private boolean full() {
        return usedSize == elem.length;
    }

    @Override
    public int pop() {
        if(usedSize == 0) {
            throw new EmptyException("栈空了");
        }
        int tmp = elem[usedSize - 1];
        usedSize--;
        return tmp;
    }

    @Override
    public int peek() {
        if(usedSize == 0) {
            throw new EmptyException("栈空了");
        }
        int tmp = elem[usedSize - 1];
        return tmp;
    }

    @Override
    public int size() {
        return usedSize;
    }

    @Override
    public boolean empty() {
        return usedSize == 0;
    }
}

//自定义异常类
public class EmptyException extends RuntimeException{
    public EmptyException(String msg) {
        super(msg);
    }
}

都看到这了，点个赞再走吧，谢谢谢谢谢！