一.简介

  栈是一种LIFO结构，使用数组头部添加元素的时间复杂度是O(n),而向尾部添加元素或删除元素的时间复杂度为O(1),所以我们使用数组的尾部作为栈的top，元素出栈即删除数组的尾部元素，入栈即在数组尾部添加元素。

二.数组栈的代码实现

• 这里为了方便我封装了自己的数组结构MyArray，实现了数据的动态扩容和缩容

public class MyArray<T> {

  private T[] data;
  private int size;

  @SuppressWarnings("unchecked")
  public MyArray(int capacity) {
    this.data = (T[]) new Object[capacity];
    this.size = 0;
  }

  /**
   * 无参构造函数初始容量10
   */
  @SuppressWarnings("unchecked")
  public MyArray() {
    this(10);
  }

  /**
   * 获取元素个数
   */
  public int getSize() {
    return size;
  }

  /**
   * 获取数组容量
   */
  public int getCapacity() {
    return data.length;
  }

  /**
   * 数组是否是空的
   */
  public boolean isEmpty() {
    return size == 0;
  }

  /**
   * 在index 索引位置添加一个元素t
   * O(n/2)=O(n)时间复杂度
   */
  public void add(int index, T t) {


    if (index < 0 || index > size) {
      throw new IllegalArgumentException("Add fail,Require index >=0 and index <=size");
    }
    if(size==data.length){
      resizeArray(2*data.length);
    }
    for (int i = size - 1; i >= index; i--) {
      data[i + 1] = data[i];
    }
    data[index] = t;
    size++;

  }

  /**
   * 在数组开始位置添加一个元素t
   * O(n)时间复杂度
   */
  public void addFirst(T t) {
    add(0, t);
  }

  /**
   * 在当前所有元素后添加一个元素t
   * O(1)均摊复杂度
   */
  public void addLast(T t) {
    add(size, t);
  }

  /**
   * 获取index索引位置的元素
   * 0(1)
   */
  public T get(int index) {
    if (index < 0 || index > size - 1) {
      throw new IllegalArgumentException("Get failed,index is illegal");
    }
    return data[index];
  }

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

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

  /**
   * 查找数组中元素e所在的索引，如果不存在元素e，则返回-1
   * O(n)
   */
  public int find(T t) {
    for (int i = 0; i < size; i++) {
      if (data[i].equals(t) ) {
        return i;
      }
    }
    return -1;
  }

  /**
   * 是否包含某个元素
   * O(n)
   * @param t
   * @return
   */
  public boolean contains(T t) {
    return find(t) != -1;
  }

  /**
   * 修改index索引位置的元素
   * O(1)时间复杂度
   */
  public void set(int index, T t) {
    if (index < 0 || index > size - 1) {
      throw new IllegalArgumentException("Get failed,index is illegal");
    }
    data[index] = t;
  }


  /**
   * 删除index索引的元素，并返回该元素
   * O(n/2)=O(n)时间复杂度
   */
  public T remove(int index) {
    if (index < 0 || index > size - 1) {
      throw new IllegalArgumentException("Get failed,index is illegal");
    }
    T ret = data[index];
    for (int i = index; i < size; i++) {
      data[i] = data[i + 1];
    }
    data[size] = null;
    size--;
    //防止复杂度震荡，防止创建0size的数组
    if (size == data.length / 4&& data.length / 2 != 0) {
      resizeArray(data.length/2);
    }
    return ret;
  }

  public void removeElement(T t) {
    int i = find(t);
    if (i != -1) {
      remove(i);
    }
  }

  /**
   * 移除所有元素中的第一个元素
   * O(n)时间复杂度
   */
  public T removeFirst() {
    return remove(0);
  }

  /**
   * 移除所有元素中的最后个元素
   * O(1)时间复杂度
   */
  public T removeLast() {
    return remove(size - 1);
  }

  @SuppressWarnings("unchecked")
  public T[] resizeArray(int length) {
    T[] newArray = (T[]) new Object[length];
    for (int i = 0; i < size; i++) {
      newArray[i] = data[i];
    }
    data=newArray;
    return newArray;
  }

  @Override
  public String toString() {
    StringBuilder builder = new StringBuilder();
    builder.append(String.format("Array : size = %d ,capacity = %d \n", size, data.length));
    builder.append("[");
    for (int i = 0; i < size; i++) {
      builder.append(data[i]);
      if (i != size - 1) {
        builder.append(",");
      }
    }
    builder.append("]");
    return builder.toString();
  }
}

• 使用MyArray实现栈

public interface Stack<E> {
  int getSize();
  boolean isEmpty();
  E peek();
  E pop();
  void push(E e);
}

/**
 * 数组栈 时间复杂度O(1)
 * @param <E>
 */
public class ArrayStack<E> implements Stack<E> {
   private MyArray<E> array;

  public ArrayStack(int capacity) {
    array = new MyArray<>(capacity);
  }

  public ArrayStack(){
    array = new MyArray<>();
  }

  @Override
  public int getSize() {
    return array.getSize();
  }

  @Override
  public boolean isEmpty() {
    return array.isEmpty();
  }

  /**
   * 查看栈顶元素
   * @return
   */
  @Override
  public E peek() {
    return array.getLast();
  }

  /**
   * 弹出栈顶元素，出栈
   * @return
   */
  @Override
  public E pop() {
    return array.removeLast();
  }

  /**
   * 入栈
   * @param e
   */
  @Override
  public void push(E e) {
    array.addLast(e);
  }

  /**
   * 查看栈的容量
   * @return
   */
  public int capacity(){
    return array.getCapacity();
  }

  @Override
  public String toString() {
    StringBuilder builder = new StringBuilder();
    builder.append("Stack :" );
    builder.append("[");
    for (int i = 0; i < array.getSize(); i++) {
      builder.append(array.get(i));
      if (i != array.getSize() - 1) {
        builder.append(",");
      }
    }
    builder.append("]top");
    return builder.toString();
  }

三.时间复杂度分析

  数组栈的出栈和入栈皆为O(1)操作，所以总体来说数组栈是一个时间复杂度为O(1)的数据结构。