栈

  • 一种基于数组或者链表的数据结构
  • 可以抽象为一个单口容器（如下图），只有一边可以进出操作，具有先进后出的特点

栈.jpg

栈的实现

  • 数组实现

image.png

  • 链表实现

image.png

  • 最大的区别就是扩容，链表天然支持动态扩容。栈溢出

    栈基本操作代码示例

    ```java /**
  • @author jitwxs

  • @date 2022-03-06 */ public class ArrayStock implements MyStock {

    private T[] data = (T[])new Object[1]; private int n=0;

    public ArrayStock(int capacity) {

    1.   this.data = (T[])new Object[capacity];

    }

    @Override public MyStock push(T t) {

    1.   adjustSize();
    2.   data[n++] = t;
    3.   return null;

    }

    @Override public T pop() {

    1.   if (isEmpty()) {
    2.       return null;
    3.   }
    4.   T curr = data[--n];
    5.   data[n] = null;
    6.   return curr;

    }

    @Override public int size() {

    1.   return n;

    }

    @Override public boolean isEmpty() {

    1.   return n==0;

    }

    void adjustSize(){

    1.   if (n>=data.length){
    2.       T[] newData = (T[])new Object[n*2];
    3.       for (int i = 0;i < n;i++) {
    4.           newData[i] = data[i];
    5.       }
    6.       data = newData;
    7.   }

    } } ```