我们可以设计一个队列API(泛型实现):
public class Queue<Item> implements Iterable<Item> Queue() 创建空队列 void enqueue() 添加一个元素 Item dequeue() 删除最早添加的一个元素 boolean isEmpty() 队列是否为空 int size() 队列中的元素数量
使用链表实现队列(实现了迭代器):
public class Queue<Item> implements Iterable<Item> { //实现迭代器接口
//持有一个头指针一个尾指针,方便进队和出队。
private Node<Item> first,last;
private int n; //保存队列中的元素个数
//节点类
private static class Node<Item> {
private Item item;
private Node<Item> next;
}
//构造器
public Queue() {first = null;last = null;n = 0;}
//是否为空
public boolean isEmpty() { return first == null; }
//当前元素个数
public int size() {return n;}
//入队列
public void enqueue(Item item) {
Node<Item> oldlast = last;
last = new Node<Item>();
last.item = item;
last.next = null;
if (isEmpty()) first = last;
else oldlast.next = last;
n++;
}
//出队列
public Item dequeue() {
if (isEmpty()) throw new NoSuchElementException("Queue underflow");
Item item = first.item;
first = first.next;
n--;
if (isEmpty()) last = null;
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;
}
}
}