一文读懂之数据结构之栈_栈满了在压数据

1. 先来了解一下基本概念：
   栈stack
   栈底：第一个存入数据的位置
   压栈：push，往栈中放入数据
   出栈、弹栈：pop。从栈中取出数据
   栈顶指针：类似一个变量、该变量保存的是下一个存入栈中的数据的位置。
   栈顶指针永远指向代存入数据的栈顶的空白位置。
   栈一开始是空的，栈顶指针指向栈底。
   所有的对战的数据操作，都是通过栈顶指针来完成的。
   压栈的过程：
   1、将数据存入指针指向的位置。2、将指针上移，继续指向栈顶。
   出栈的过程：
   1、指针下移2、将指针处的数据取走。
2. 下面我们通过数组保存数据来模拟栈的这些压栈、出栈的特点。
   新建MyStack类，来定义栈
   2.1初始化栈

class MyStack {
    //栈的初始化容量。扩容的规则：每次扩容为现有容量的1.5倍
    public static final int DEFAULT_CAPACITY = 6;
    private Object[] elementData;
    //栈顶指针，一开始指向栈底
    private int index;

    //初始化栈对象
    public MyStack() {
        elementData = new Object[DEFAULT_CAPACITY];
    }
1
2
3
4
5
6
7
8
9
10
11

2.2模拟压栈过程
如果栈满了就扩容，否则将对象数据赋值给栈顶指针索引处的值，然后指针加1.

    /**
     * 模拟压栈过程
     * @param o 被压栈的对象
     */
    public void push(Object o) {
        //两种情况，栈满了
        if (isFull()) {
            //扩容 创建一个新的长度的数组，然后将原数组中的内容复制过来，让elementData指向新数组即可
            elementData = Arrays.copyOf(elementData, index * 3 >> 1);
        }//没有满，将o存入index指向的位置，并且index自增
        elementData[index++] = o;
    }
1
2
3
4
5
6
7
8
9
10
11
12

    /**
     * 判断栈是否满了
     * @return
     */
    private boolean isFull() {
        return index == elementData.length;
    }
1
2
3
4
5
6
7

2.3模拟出栈过程
同样是两种情况，当栈为空时不允许取数据，否则抛出异常，当栈不为空时，将栈顶指针减一，此时取出该位置出的数据，并将该位置的数据设为空，防止内存泄漏。

    /**
     * 模拟出栈过程
     * @return
     */
    public Object pop() throws Exception {
        //两种情况，空栈,就不能取数据，需要抛异常
        if (isEmpty()) {
            Exception e = new Exception("对不起！栈中无数据！");
            throw e;
        }//不为空
        Object o = elementData[--index];//栈顶指针先减一，在将指针所指位置数据取出。
        //避免内存泄漏,即当引用对象不为空时，使gc无法回收，内存造成资源浪费
        elementData[index] = null;
        return o;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

    /**
     * 判断栈是否为空
     * @return
     */
    private boolean isEmpty() {
        return index == 0;
    }
1
2
3
4
5
6
7

2.4重写toString方法，打印栈

    //打印数组将数组中为null的位置去掉
    public String toString(){
        return Arrays.toString(Arrays.copyOf(elementData,index));
    }
1
2
3
4

2.5返回栈中元素的方法

    /**
     * 返回栈中元素个数
     * @return
     */
    public int size() {
        return index;
    }
1
2
3
4
5
6
7

2.6得到栈的容量

    /**
     * 得到栈的容量
     * @return
     */
    public int capacity() {
        return elementData.length;
    }
1
2
3
4
5
6
7

2.7测试类
通过debug来观察压栈和出栈的过程
如果debug不了解，可以查看debug

/**
 * 模拟栈的这种数据结构 breakpoint 断点调试debug
 */
public class AarraySimilateStack {
    public static void main(String[] args) {
        MyStack myStack = new MyStack();
        myStack.push("1");
        myStack.push(Integer.valueOf(2));
        myStack.push("a");
        myStack.push("b");
        myStack.push("c");
        myStack.push("d");
        myStack.push("e");
        //重写toString方法了
        System.out.println(myStack);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

整个压栈的过程分为如下7步：
2.7.1栈中已经存入5个数据，即将存入第六个，也就是栈满前的最后一个

2.7.2判断栈是否满，此时栈顶指针为5，这里马上要插入数据字符串d。

2.7.3没有满插入

2.7.4此时栈中已经有6个数据，将会扩容。
2.7.5索引为6，即栈顶指针为6，即栈顶指针=数组长度，也就是栈满了，即将扩容。
2.7.6扩容1.5倍

2.7.7扩容完之后，栈就不满了，然将栈顶指针处的数据赋值给索引6，随后，栈顶指针加1.

出栈过程：如下7步

1、此时栈中仅保留一位数据用来演示出栈过程和异常。（即栈不为空弹出数1和栈为空弹出数据）
2、判断是否为空

3、不为空4、不为空，此时栈顶指针减一，然后将栈顶指针出的数据取出，取出（即赋值），赋值完之后，对象引用还是指向该数据，因为gc不会回收该数据对象，会造成内存浪费，即内存泄露。故让该数据对象为null。

5、继续出栈，此时战中已经没有数据了6、为空，该抛异常了

7、抛出异常