上一篇中我们实现了动态数组，封装了一个可以动态扩容、缩容的数组。由此我们根据封装的数组实现java中 栈 这种数据结构。

栈是一种线性数据结构，它按照 先进后出 的原则存储数据,先进入的数据被压入栈底,最后的数据在栈顶,需要读数据的时候从栈顶开始弹出数据。

栈的应用：软件中的撤销操作，程序中的方法栈

//定义Stack接口

public interface Stack<E> {

int getSize();

boolean isEmpty();

void push(E e);

E pop();

E peek();

}

//实现Stack接口

public class ArrayStack<E> implements Stack<E> {

//默认数组

private Array<E> array;

//指定初始化容量的构造函数

public ArrayStack(int capacity){

array = new Array<>(capacity);

}

public ArrayStack(){

array = new Array<>();

}

//获取栈中元素个数

@Override

public int getSize() {

return array.getSize();

}

//判断栈是否为空

@Override

public boolean isEmpty() {

return array.isEmpty();

}

//入栈

@Override

public void push(E e) {

//往数组末尾添加元素，极端情况下会触发扩容

array.addLast(e);

}

//出栈

@Override

public E pop() {

//返回并删除数组末尾元素

return array.removeLast();

}

//查看栈顶元素

@Override

public E peek() {

//获取数组末尾元素

return array.getLast();

}

@Override

public String toString() {

StringBuilder sb = new StringBuilder();

sb.append("stack:");

sb.append("[");

for(int i = 0;i < array.getSize(); i++){

sb.append(array.get(i));

if(i!=array.getSize()-1){

sb.append(",");

}

}

sb.append("]");

return sb.toString();

}

}

由上可以发现，由数组实现的栈这种数据结构，入栈和出栈操作均摊复杂的为O（1），极端情况下是O（n)的。极端情况是指数组触发了扩容或者缩容操作。

通过源码我们可以发现java中Stack这个类也是基于动态数组实现的，以上是其简单版实现

下期我们根据封装好的数组实现“ 队列 ” 这种数据结构

---------本文源于日常学习笔记记录，如有错误欢迎批评指正