栈(Stack)是一种后进先出的数据结构（LIFO:last in first out），只允许访问栈中的第一个数据项：即最后插入的数据项。移除这个数据项之后，才能看到第二个数据项，以此类推。
往栈中存入数据称之为压栈(push)，移除数据称之为弹栈(pop)，此外通常还提供查看栈顶元素的peek方法，此方法可以可以栈顶元素的值，但是并不会将其移除
java.util.Stack就是JDK提供的一种对栈的实现，这个实现是基于数组的，由于栈非常简单，我们没有必须要分析源码，直接按照以下方法提供一个相同的自己的实现，此外，我们也可以基于链表来实现一个栈
基于数组的栈的实现
关于基于数组的栈的实现，只有一点值得注意的地方，其是LIFO，但是我们在使用数组的时候，并不需要每次都将元素插入数组的第一个位置，然后将之前的所有元素后移一个位置，只要用一个变量记住最后一个添加的元素的位置即可，当弹栈时，直接返回这个位置上的数字即可
代码语言：javascript复制public class SimpleArrayStack<T> { private Object[] array = null; private int size = 0; private static final int DEFAULR_INITIAL_SIZE = 10; private int capacity = 0; public SimpleArrayStack() { this(DEFAULR_INITIAL_SIZE ); } public SimpleArrayStack(int initial_size) { super(); this.capacity = initial_size; array = new Object[initial_size]; } @SuppressWarnings("unchecked" ) public T pop() { if (size < 1) { throw new IllegalStateException("no more elements"); } T result = (T) array [--size]; array[size ] = null; return result ; } @SuppressWarnings("unchecked" ) public T peek() { if (size < 1) { throw new IllegalStateException("no more elements"); } return (T) array [size - 1]; } public void push(T e) { int index = size ; if (index > capacity) { // 扩容 int new_capacity = capacity capacity >> 1; if (new_capacity <= 0) { new_capacity = Integer.MAX_VALUE; } array = Arrays.copyOf( array, new_capacity ); } array[index ] = e; } public int getSize() { return size ; }}测试代码
代码语言：javascript复制public class SimpleArrayStackTest { public static void main(String[] args) { SimpleArrayStack<Integer> simpleStack=new SimpleArrayStack<Integer>(); System. out.print("push:t" ); for (int i = 0; i < 10; i ) { simpleStack.push(i ); System. out.print(i "t" ); } System. out.print("npop:t" ); while (simpleStack.getSize()>0){ System. out.print(simpleStack .pop() "t"); } }}运行程序输出
push: 0 1 2 3 4 5 6 7 8 9 pop: 9 8 7 6 5 4 3 2 1 0 |
|---|
可以看到数据都是按照和插入顺序相反的方式弹出来了
基于链表的栈的实现
基于链表的Stack尤为简单，我们可以使用上一节编写SingleLinkList来实现，实际上就是一种委派，并把我们不想提供的方法给屏蔽，这可能没有什么技术含量，但是读者意识到了，一个数据结构可以在另外一个数据结构的基础上编写
public class SimpleLinkedListStack <T>{ private SingleLinkList<T> singleLinkList =new SingleLinkList<T>(); public void push(T t){ singleLinkList.addFirst(t); } public T pop(){ return singleLinkList.removeFisrt(); } public T peek(){ return singleLinkList.getFirst(); } public int getSize(){ return singleLinkList.size(); } }
