我们可以设计一个栈API:
public class Stack<Item> implemrnts Iterable<Item>
Stack() 创建一个空栈
void push(Item item) 添加一个元素
Item pop() 删除最近添加的元素
boolean isEmpty() 栈是否为空
int size() 栈中元素的数量
逻辑很好理解,接下来使用链表来实现(其中实现了迭代器类):
public class Stack<Item> implements Iterable<Item> { //实现迭代器接口
private Node<Item> first; //头指针
private int n; //栈中元素数量
//节点类
private static class Node<Item> {
private Item item;
private Node<Item> next;
}
//构造器
public Stack() {first = null;n = 0;}
//是否为空
public boolean isEmpty() {return first == null;}
//当前元素数量
public int size() {return n;}
//压栈
public void push(Item item) {
Node<Item> oldfirst = first;
first = new Node<Item>();
first.item = item;
first.next = oldfirst;
n++;
}
//出栈
public Item pop() {
if (isEmpty()) throw new NoSuchElementException("Stack underflow");
Item item = first.item;
first = first.next;
n--;
return item;
}
//新建迭代器
public Iterator<Item> iterator() {
return new ListIterator<Item>(first);
}
//实现迭代器
private class ListIterator<Item> implements Iterator<Item> {
private Node<Item> current;
public ListIterator(Node<Item> first) {
current = first;
}
public boolean hasNext() {
return current != null;
}
public void remove() {
throw new UnsupportedOperationException();
}
public Item next() {
if (!hasNext()) throw new NoSuchElementException();
Item item = current.item;
current = current.next;
return item;
}
}
}