接口类：
public interface Stack<E> { int getSize(); boolean isEmpty(); void push(E e); E pop(); E peek(); }
接口实现：
import com.lyy.datasty.Array; /** * @program: Data-Structures * @ClassName ArrayStack * @description: * @author: lyy * @create: 2019-11-20 21:52 * @Version 1.0 * 用户不能看栈中间的元素，只能看到栈顶的元素 **/ public class ArrayStack<E> implements Stack<E>{ Array<E> array; public ArrayStack(int capacity){ array = new Array<>(capacity); } public ArrayStack(){ array = new Array<>(); } @Override public int getSize() { return 0; } @Override public boolean isEmpty() { return array.isEmpty(); } public int getCapacity(){ return array.getCapacity(); } @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 res = new StringBuilder(); res.append("Stack："); res.append('['); for (int i = 0; i < array.getSize(); i++) { res.append(array.get(i)); if(i != array.getSize() - 1) res.append("，"); } res.append("] top");//哪里是栈顶 return res.toString(); } }
测试结果：
Stack: [0] top Stack: [0, 1] top Stack: [0, 1, 2] top Stack: [0, 1, 2, 3] top Stack: [0, 1, 2, 3, 4] top Stack: [0, 1, 2, 3] top
从结果中我们可以看到，我们每循环一次就添加一条数据，这里为了好让我们知道哪一个是 栈顶，我们在最后一个添加的数据那里，加了一个 top ，最新增加的数据，就是我们的栈顶，当我们添加完成后，可以看到栈数据为：[0, 1, 2, 3, 4] top，当我们出栈一个数据后，我们就可以看到 栈顶数据 4 就没有了，以上就是对于栈实现的代码，感兴趣的小伙伴可以自己实现一遍，源码在最后我会放在 github上，有兴趣的小伙伴记得下载。
1.4 栈的时间复杂度
ArrayStack：
二、队列
2.1 队列认识
队列与栈一样是一种线性结构，因此以常见的线性表如数组、链表作为底层的数据结构。
相比数组，队列对应的操作是数组的子集
队列只能从一端（队尾）添加元素，只能从一端（队首）取出元素，也就是队尾添加元素，在队头删除元素
队列是一种先进先出的数据结构（先到先得）
队列列中的数据元素遵循“先进先出”（First In First Out）的原则，简称 FIFO 结构。
队列是一个 先进先出的线性表，相应的也有 顺序存储 和 链式存储两种方式。
在队列中，新添加的一端为 队尾 ，另一端为 队首 ，当一个元素从队尾进入队列时，一直向队首移动，直到它成为移除的元素为止。这种 先进先出（FIFO） 模式，在我们生活中也随处可见，比如：我们去银行柜台取钱，我们在取钱之前就要先去取号，先做 入队操作，也就是我们队列中的在 队尾添加元素，新来的人等待排队，等待前面的人处理完，当前面取号的人在柜台处理完之后，就会叫下一个号码，这个过程就是 出队操作，只有当在我们前面的人，都处理完之后才会轮到我们。
如下图：
2.2 数组队列的实现（顺序存储）
首先我们需要以下几个栈元素：
int getSize(); // 获取队列的元素多少
boolean isEmpty(); //查看队列是否为空
void enqueue(E e); //添加队列元素
E dequeue(); //删除队列队首元素
E getFront(); //获取队首队列元素
2.2.1 接口实现
public interface Queue<E> { int getSize(); boolean isEmpty(); void enqueue(E e); E dequeue(); E getFront(); }
2.2.2 接口类实现
public class ArrayQueue<E> implements Queue<E> { private Array<E> array; public ArrayQueue(int capacity){ array = new Array<>(capacity); } public ArrayQueue(){ array = new Array<>(); } @Override public int getSize(){ return array.getSize(); } @Override public boolean isEmpty(){ return array.isEmpty(); } public int getCapacity(){ return array.getCapacity(); } @Override public void enqueue(E e){ array.addLast(e); } @Override public E dequeue(){ return array.removeFirst(); } @Override public E getFront(){ return array.getFirst(); } @Override public String toString(){ StringBuilder res = new StringBuilder(); res.append("Queue: "); res.append("front ["); for(int i = 0 ; i < array.getSize() ; i ++){ res.append(array.get(i)); if(i != array.getSize() - 1) res.append(", "); } res.append("] tail"); return res.toString(); } public static void main(String[] args) { ArrayQueue<Integer> queue = new ArrayQueue<>(); for(int i = 0 ; i < 10 ; i ++){ queue.enqueue(i); System.out.println(queue); if(i % 3 == 2){ queue.dequeue(); System.out.println(queue+"：================="+(i % 3)); } } } }
2.2.3 执行结果
Queue: front [0] tail Queue: front [0, 1] tail Queue: front [0, 1, 2] tail Queue: front [1, 2] tail：=================2 Queue: front [1, 2, 3] tail Queue: front [1, 2, 3, 4] tail Queue: front [1, 2, 3, 4, 5] tail Queue: front [2, 3, 4, 5] tail：=================2 Queue: front [2, 3, 4, 5, 6] tail Queue: front [2, 3, 4, 5, 6, 7] tail Queue: front [2, 3, 4, 5, 6, 7, 8] tail Queue: front [3, 4, 5, 6, 7, 8] tail：=================2 Queue: front [3, 4, 5, 6, 7, 8, 9] tail
首先我们总共是循环十次，添加到队列中，每天添加一次打印队列中的元素，如果遇到 i % 3 == 2，我们就去除队首的元素，就是我们在结果中看到的 =================2的位置，每次都会把最先添加（队首）的元素给删除掉，从上面的结果中可以看出，当我们每次去 queue.dequeue()元素的时候，其实就是操作数组中的 size --，这样对于我们队列来说效率其实是很慢的，如果删除队首元素，后面的元素就要往前移动，对应的时间复杂度就是O(n)。
