我们经常会问到java数据结构可以怎么实现，看过了算法之后得到很大启发，这里整理如下。
队列是一种先进先出(FIFO)的集合模型,而栈则是后进先出(LIFO)的集合模型，我们经常使用它们用来保存元素的相对顺序。Java中在java.util.LinkedList类中实现了关于队列和栈的实现，但是这是一个宽接口的例子，这里我们自己实现它以研究它的思路。
有两种基础可以用来实现：数组和链表
我们实现栈的基本要素如下：
int N 代表栈的容量
boolean isEmpty()用来判断栈是否为空
int size()返回栈的容量
void push()进栈操作，每次栈顶新增元素
T pop()出栈操作，由于出栈后栈中元素会得到释放，因此我们需要一个返回值纪录出栈元素以便操作。这里返回值为一个范型，可以把范型理解为占位符，即开始时不规定类型是什么，到后来用到时再定义，这里范型可以为任何类。
数组实现：
由于数组在初始化时必须设置存储容量，而我们并不知道我们的栈与队列需要多大的存储空间，因此我们对思路是在对元素进行进入操作时与容量大小进行比较，关键思路是如果超过了则对容量进行“扩容”，即复制一份数组并将原来那份废弃。在这里对元素使用率进行了判断，使其不回低于1/4.
public class StackInArray<T> implements Iterable<T> {
private T[] a = (T[]) new Object[1];
private int N = 0;
public boolean isEmpty() {
return N == 0;
}
public int size() {
return N;
}
private void resize(int max) {
T[] temp = (T[]) new Object[max];
for (int i = 0; i < N; i++) {
temp[i] = a[i];
}
a = temp;
}
public void push(T t) {
if (N == a.length)
resize(a.length << 1);//移位操作，相当于＊2，感觉更能理解扩容一倍的意思。
a[N++] = t;
}
public T pop() {
T t = a[--N];
a[N] = null;
if (N > 0 && N == a.length / 4)
resize(a.length >> 1);
return t;
}
@Override
public Iterator<T> iterator() {
return new ArrayIterator();
}
private class ArrayIterator implements Iterator<T> {
private int i = N;
@Override
public boolean hasNext() {
return i > 0;
}
@Override
public T next() {
return a[--i];
}
}
}
这里栈的基本元素为一个范型数组。这里新增了一个void resize(int max)方法用来对数组进行大小调整。
当我们进栈和出栈时，实际上是对数组中最后一个标记
看完了数组实现的栈我们接下来看由链表实现的栈，首先复习一下链表。
链表定义如下：链表时一种递归的数据结构，它或者为空，或者是指向一个结点的引用，该结点含有一个范型的元素和一个指向另一条链表的引用。
在java中，我们可以用一个嵌套类定义结点实现链表
private class Node {
T t;
Node next;
}
用链表实现的栈基本操作与用数组实现栈的操作一致，只不过我们这里用Node数据类型替代数组，因此在初始化的时候不需要定义栈的大小。
public class StackInChain<T> implements Iterable<T> {
private Node first;// 栈顶
private int N;// 容量
private class Node {
T t;
Node next;
}
public boolean isEmpty() {
return first == null;
}
public int size() {
return N;
}
public void push(T t) {
Node oldFirst = first;
first = new Node();
first.t = t;
first.next = oldFirst;
N++;
}
public T pop(){
T t=first.t;
first=first.next;
N--;
return t;
}
}
链表实现的栈思路很明显，每当push时就在头节点前新增一个节点，使其作为新的头节点，并使容量自增即可。出栈时将头节点向后移一位即可。
| 数据结构 | 优点 | 缺点 |
| 数组 | 通过索引可以直接访问任意元素 | 在初始化时就需要知道元素的数量 |
| 链表 | 使用的空间大小与元素数量正比 | 需要通过索引访问任意元素 |