一、定义
栈是限定在表的同一端进行插入或删除的线性表，进行插入或删除操作的一端称为栈顶，另一端为栈底，插入数据元素的操作叫做入栈，删除数据元素的操作叫做出栈，它具有先进后出（First In Last Out，FILO）的特性。
二、栈的基本操作分析
前面章节说到，线性表可以通过顺序存储和链式存储来实现，作为操作受限的线性表也一样，所以后面也会通过两种存储结构来分析栈的基本操作实现。
在顺序存储结构中，我们一般会使用数组来实现，定义一个栈，约定使用 top 来存放栈顶元素的位置，当 top=-1 时表示栈为空，当 top=array.length-1 时，表示栈满。顺序栈的数据元素空间大小是预先分配好的，当空间全部满了后再入栈会溢出，栈为空时出栈也会产生溢出。
在链式存储结构中，可以直接使用单向链表来实现，此时，我们只要考虑把链表的头部作为栈底还是栈顶，很容易想到，栈的插入和删除等操作都只会在栈顶一端进行，所以把链表头部作为栈顶效率更高。
1. 入栈
在顺序存储中进行入栈操作，只需要通过 top 来定位栈顶位置，然后做入栈操作，执行完后 top 移到新的栈顶位置。链式存储中，需要将新的结点添加到链表头部，首先把 head 结点赋给 a4.next，然后新结点 a4 成为新的头部结点。
2. 出栈
顺序存储中进行出栈操作，通过 top 定位并获取栈顶元素，然后做出栈操作，执行完后 top 移动到新的栈顶位置。链式存储中，做出栈操作时，获取到头部结点元素 a4 后，然后直接把 head.next 赋值给 head 来实现栈顶元素的删除。
下面新建一个栈常规操作的接口，然后我们分别使用顺序结构（数组）和链式结构来实现它，读者可以分别对两种存储结构实现的接口的时间复杂度进行分析。
public interface Stack<T> { /** * 入栈 */ boolean push(T t); /** * 出栈 */ T pop(); /** * 判断栈是否为空 */ boolean isEmpty(); /** * 打印栈所有数据 */ void print(); }
三、栈的基本操作实现
和线性表实现一样，顺序结构使用数组来存储数据，链式结构使用结点来存储数据。
1. 顺序存储实现
public class ArrayStack<T> implements Stack<T> { private int top = -1; private int size = 0; private Object[] elementData; public ArrayStack(int size) { this.elementData = new Object[size]; } @Override public boolean push(T t) { if (top > elementData.length - 1) { throw new ArrayIndexOutOfBoundsException(); } elementData[++top] = t; size++; return true; } @SuppressWarnings("unchecked") @Override public T pop() { if (top == -1) { throw new NullPointerException(); } Object e = elementData[top]; elementData[top--] = null; size--; return (T) e; } @Override public boolean isEmpty() { return size == 0; } @Override public void print() { System.out.println(Arrays.toString(elementData)); } }
2. 链式存储实现
public class LinkedStack<T> implements Stack<T> { private Node head; private int size = 0; private class Node { private T t; private Node next; public Node() { } public Node(T t, Node next) { this.t = t; this.next = next; } } @Override public boolean push(T t) { Node n = new Node(t, null); if (head != null) { n.next = head; } head = n; size++; return true; } @Override public T pop() { if (head == null) { throw new NullPointerException(); } T t = head.t; head = head.next; size--; return t; } @Override public boolean isEmpty() { return size == 0; } @Override public void print() { Node n = head; while (n != null) { System.out.print(n.t + ","); n = n.next; } System.out.println(); } }
