栈定义
栈是一种基于后进先出（LIFO）策略的集合类型。本章讨论如何使用Java语言实现一个基本的栈。一个栈容器要求提供入栈操作，出栈操作，获取栈大小和判断栈是否为空操作。抽象数据类型可定义为：
public interface Stack<Item> {
/*
* 判断栈是否为空。
*/
public boolean isEmpty();
/*
* 获取栈大小。
*/
public int size();
/*
* 入栈。
*/
public void push(Item item);
/*
* 出栈。
*/
public Item pop();
}
数组实现
栈元素存储在数组中是一种基本的实现方式。内部定义一个数组[]a用于存在入栈的元素，整数N保存当前元素数量。
public class ArrayStack<Item> implements Stack<Item> {
/**
* 存储栈元素
*/
private Item[] a = (Item[]) new Object[1];
/**
* 栈元素数量
*/
private int N;
@Override
public boolean isEmpty() {
return N == 0;
}
@Override
public int size() {
return N;
}
@Override
public void push(Item item) {
a[N++] = item;
}
@Override
public Item pop() {
Item item = a[--N];
a[N] = null;
return item;
}
}
选择用数组标示栈内容必须先预估栈最大容量大小。在Java中，数组一旦创建，其大小就不能改变。在实际应用中，我们一般无法在创建栈时确定其大小。如果太小，会导致数组越界，如果太大，则会浪费内存空间。因此，我们需要在入栈和出栈中动态的调整数据大小。
入栈时通过检查栈大小N和数组大小a.length是否相等来检查是否能够容纳新的元素。如果没有多余的空间，将数组的的长度加倍。
出栈时检查栈大小是否小于数组的四分之一，如果满足则把数组大小减半。
public class ResizingArrayStack<Item> implements Stack<Item> {
private Item[] a = (Item[]) new Object[1];
private int N = 0;
public boolean isEmpty() {
return N == 0;
}
public int size() {
return N;
}
public void push(Item item) {
if (N == a.length) {
resize(2 * a.length);
}
a[N++] = item;
}
private void resize(int max) {
Item[] temp = (Item[]) new Object[max];
System.arraycopy(a, 0, temp, 0, N);
a = temp;
}
public Item pop() {
Item item = a[--N];
a[N] = null; // 避免对象游离
if (N > 0 && N == a.length / 4) {
resize(a.length / 2);
}
return item;
}
public static void main(String[] args) {
ResizingArrayStack<String> stack = new ResizingArrayStack<>();
stack.push("ye");
stack.push("c");
stack.push("l");
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
}
}
数组实现的缺点在于某些push()和pop()操作会调整数组的大小：这项操作的耗时和栈大小成正比。为了克服这个缺点，可以采用链表实现栈。
链表实现
链表是一种递归的数据结构，它或者为空，或者指向一个节点的引用，该节点含有一个泛型的元素和一个指向另一个链表的结构。
节点的抽象数据类型可以表示为：
private class Node{
/**
* 存储数据
*/
Item item;
/**
* 下一个节点引用
*/
Node next;
}
链表实现时用一个节点表示栈顶元素，整数N记录栈大小。入栈时新节点的下一个节点引用指向原来的栈顶节点，出栈时栈顶元素指向原来栈顶元素的下一个节点。
public class LinkedStack<Item> implements Stack<Item> {
/**
* 栈顶
*/
private Node first;
/**
* 元素数量
*/
private int N;
private class Node {
Item item;
Node next;
}
@Override
public boolean isEmpty() {
return first == null; // or N == 0;
}
@Override
public int size() {
return N;
}
@Override
public void push(Item item) {
// 栈顶添加元素
Node oldFirst = first;
first = new Node();
first.item = item;
first.next = oldFirst;
N++;
}
@Override
public Item pop() {
// 栈顶删除元素
Item item = first.item;
first = first.next;
N--;
return item;
}
}
在结构化存储数据集时，链表是数组的一种重要替代方式。它们各有优点和缺点，我们应该根据实际情况选择合适的实现。
