自定义数组类

功能

  1. 获取元素个数
  2. 获取数组容量
  3. 动态扩容

  4. 增删改查操作

    注意点

    移除节点

    移除时，索引位置之后的元素全部往前移一位，从前往后移

    1. for (int i = index + 1; i < size; i++) {
    2.  data[i - 1] = data[i];
    3. }

    添加节点

    添加时，索引位置开始的元素全部往后移一位，从后往前移

    1. for (int i = size - 1; i >= index; i--) {
    2.  data[i + 1] = data[i];
    3. }

    代码

    ```java public class MyArray {

    private T[] data; private Integer size;

    public MyArray(Integer capacity) {

    1.  data = (T[]) new Object[capacity];
    2.  size = 0;

    }

    public MyArray() {

    1.  this(10);

    }

    /**

    • 元素个数 *
    • @return java.lang.Integer
    • @author YangYudi

    • @date 2020/12/25 15:25 */ public Integer getSize() { return size; }

      /**

    • 数组容量 *
    • @return java.lang.Integer
    • @author YangYudi

    • @date 2020/12/25 15:25 */ public Integer getCapacity() { return data.length; }

      /**

    • 判空 *
    • @return boolean
    • @author YangYudi

    • @date 2020/12/28 15:50 */ public boolean isEmpty() { return size == 0; }

      /**

    • 数组扩容 *
    • @param newSize 新大小
    • @return void
    • @author YangYudi

    • @date 2020/12/25 15:46 */ private void resize(Integer newSize) { T[] newData = (T[]) new Object[newSize]; for (int i = 0; i < size; i++) {

      1.  newData[i] = data[i];

      } data = newData; }

      public void addLast(T e) { add(size, e); }

      public void addFirst(T e) { add(0, e); }

      /**

    • 添加 *
    • @param index 下标
    • @param e 对象
    • @author YangYudi

    • @date 2020/12/28 15:50 */ public void add(Integer index, T e) { if (size == data.length) {

      1.  Integer length = data.length;
      2.  //通过位运算得到新长度 借鉴arraylist
      3.  Integer resize = length + (length >> 1);
      4.  resize(resize);

      } if (index < 0 || index > size) {

      1.  throw new IllegalArgumentException("下标不合法");

      } for (int i = size - 1; i >= index; i—) {

      1.  data[i + 1] = data[i];

      } data[index] = e; size++; }

      /**

    • 判断有没有 *
    • @param e 对象
    • @author YangYudi
    • @date 2020/12/28 15:50

    • @return boolean */ public boolean contains(T e) { for (int i = 0; i < size; i++) {

      1.  if (data[i].equals(e)) {
      2.      return true;
      3.  }

      } return false; }

      /**

    • 判断对象存不存在 *
    • @param e 对象
    • @author YangYudi
    • @date 2020/12/28 15:51

    • @return java.lang.Integer */ public Integer find(T e) { for (int i = 0; i < size; i++) {

      1.  if (data[i].equals(e)) {
      2.      return i;
      3.  }

      } return -1; }

      public T get(Integer index) { if (index < 0 || index >= size) {

      1.  throw new IllegalArgumentException("下标不合法");

      } return data[index]; }

      public T getLast() { return get(size - 1); }

      public T getFirst() { return get(0); }

      public void set(Integer index, T e) { if (index < 0 || index >= size) {

      1.  throw new IllegalArgumentException("下标不合法");

      } data[index] = e; }

      public T removeFirst() { return remove(0); }

      public T removeLast() { return remove(size - 1); }

      public void removeElement(T e) { int index = find(e); if (index != -1) {

      1.  remove(index);

      } }

      public T remove(Integer index) { if (index < 0 || index >= size) {

      1.  throw new IllegalArgumentException("下标不合法");

      } T temp = data[index]; for (int i = index + 1; i < size; i++) {

      1.  data[i - 1] = data[i];

      } size—; data[size] = null; return temp; }

      @Override public String toString() { return “MyArray{“ +

      1.      "data=" + Arrays.toString(data) +
      2.      ", size=" + size +
      3.      '}';

      }

}

  1. <a name="vp7G4"></a>
  2. # 基于数组实现栈
  3. <a name="DqAWP"></a>
  4. ## 功能
  5. 先进后出，判空，获取元素个数，查看栈顶
  6. <a name="wj6TR"></a>
  7. ## 代码
  8. 刚好调用之前自定义的数组类，使得自定义栈变得非常简单<br />Stack<E>是自定义接口
  9. ```java
  10. public class ArrayStack<E> implements Stack<E> {
  12.     private MyArray<E> array;
  14.     public ArrayStack(int capacity){
  15.         array = new MyArray<>(capacity);
  16.     }
  18.     public ArrayStack() {
  19.         array = new MyArray<>();
  20.     }
  22.     @Override
  23.     public int getSize() {
  24.         return array.getSize();
  25.     }
  27.     @Override
  28.     public boolean isEmpty() {
  29.         return array.isEmpty();
  30.     }
  32.     @Override
  33.     public void push(E e) {
  34.         array.addLast(e);
  35.     }
  37.     @Override
  38.     public E pop() {
  39.         return array.removeLast();
  40.     }
  42.     @Override
  43.     public E peek() {
  44.         return array.getLast();
  45.     }
  47.     @Override
  48.     public String toString() {
  49.         return "ArrayStack{" +
  50.                 "array=" + array +
  51.                 '}';
  52.     }
  53. }

基于数组实现队列

功能

先进先出，判空，获取元素个数，获取队头队尾

代码

同样使用自定义数组类实现起来变得很简单
Queue是自定义的接口

  1. public class ArrayQueue<E> implements Queue<E> {
  3.     private MyArray<E> array;
  5.     public ArrayQueue(int capacity) {
  6.         array = new MyArray<>(capacity);
  7.     }
  9.     public ArrayQueue() {
  10.         array = new MyArray<>();
  11.     }
  13.     @Override
  14.     public int getSize() {
  15.         return array.getSize();
  16.     }
  18.     @Override
  19.     public boolean isEmpty() {
  20.         return array.isEmpty();
  21.     }
  23.     @Override
  24.     public void enqueue(E e) {
  25.         array.addLast(e);
  26.     }
  28.     @Override
  29.     public E dequeue() {
  30.         return array.removeFirst();
  31.     }
  33.     @Override
  34.     public E getFirst() {
  35.         return array.getFirst();
  36.     }
  38.     @Override
  39.     public E getEnd() {
  40.         return array.getLast();
  41.     }
  43.     @Override
  44.     public String toString() {
  45.         return "ArrayQueue{" +
  46.                 "array=" + array +
  47.                 '}';
  48.     }

此队列不是循环队列
测试一下每次出队完，后面的元素也覆盖
image.png

问题

出队时，移出队头元素，然后每个元素向前挪一位，时间复杂度是O(N)，所以要使用循环队列进行改善

循环队列

注意点

需要定义两个变量front和tail用于指向队头元素和队尾元素下标，tail指向队尾元素的下一个下标

循环队列定义：
队空 front == tail
队满 (tail + 1) % data.length == front
出队 front = (front + 1) % data.length
入队 tail = (tail + 1) % data.length
需要浪费一个空间用于判断
image.png

代码

  1. public class LoopQueue<E> implements Queue<E> {
  3.     private E[] data;
  4.     private int front;
  5.     private int tail;
  6.     private int size;
  8.     public LoopQueue(int capacity) {
  9.         //因为要有意浪费一个数组所以容量要比传来的+1
  10.         data = (E[]) new Object[capacity + 1];
  11.         front = 0;
  12.         tail = 0;
  13.         size = 0;
  14.     }
  16.     public LoopQueue() {
  17.         this(10);
  18.     }
  20.     private int getCapacity() {
  21.         return data.length - 1;
  22.     }
  24.     @Override
  25.     public int getSize() {
  26.         return size;
  27.     }
  29.     @Override
  30.     public boolean isEmpty() {
  31.         return front == tail;
  32.     }
  34.     @Override
  35.     public void enqueue(E e) {
  36.         if ((tail + 1) % data.length == front) {
  37.             resize(getCapacity() * 2);
  38.         }
  39.         data[tail] = e;
  40.         tail = (tail + 1) % data.length;
  41.         size++;
  42.     }
  44.     private void resize(int newSize) {
  45.         E[] newData = (E[]) new Object[newSize + 1];
  46.         for (int i = 0; i < size; i++) {
  47.             //原数组要通过偏移量获取下标
  48.             newData[i] = data[(i + front) % data.length];
  49.         }
  50.         data = newData;
  51.         front = 0;
  52.         tail = size;
  53.     }
  55.     @Override
  56.     public E dequeue() {
  57.         if (isEmpty()) {
  58.             throw new IllegalArgumentException("队列为空");
  59.         }
  60.         E temp = data[front];
  61.         data[front] = null;
  62.         front = (front + 1) % data.length;
  63.         size--;
  64.         //如果数组元素个数为数组容量的4分之1就进行缩容
  65.         if (size == getCapacity() / 4 && getCapacity() / 2 != 0) {
  66.             resize(getCapacity() / 2);
  67.         }
  68.         return temp;
  69.     }
  71.     @Override
  72.     public E getFirst() {
  73.         if (isEmpty()) {
  74.             throw new IllegalArgumentException("队列为空");
  75.         }
  76.         return data[front];
  77.     }
  79.     @Override
  80.     public E getEnd() {
  81.         return data[tail - 1];
  82.     }
  84.     @Override
  85.     public String toString() {
  86.         return "LoopQueue{" +
  87.                 "data=" + Arrays.toString(data) +
  88.                 ", front=" + front +
  89.                 ", tail=" + tail +
  90.                 ", size=" + size +
  91.                 '}';
  92.     }
  94. }