兴亡谁人定，胜败岂无凭——易中天《百家讲坛》
不得慕虚名而处实祸 ——曹操
1. 概述
队列是一种线性集合，其元素从一端加入，从另一端删除。因此队列是按照先进先出方式处理的，从队列中删除元素的次序与往队列里放置元素的的次序是一样的。
由于队列是一种线性集合，因此可以像处理栈一样，把队列实现成一种LinearNode对象的链表。
2. 队列ADT
队列核心功能的声明：
package ds.java.ch05.queueImpl;
/**
* @author LbZhang
* @version 创建时间：2015年11月16日 下午7:06:32
* @description 队列接口
*/
public interface QueueADT<T> {
public void enqueue(T elem);
public T dequeue();
public T first();
public boolean isEmpty();
public int size();
public String toString();
}
3. 链表实现队列
使用两个分别指向链表受元素、链表末元素的引用方便队列的链表实现。
package ds.java.ch05.queueImpl;
/**
* 结点类的声明
* @author MrLBZ
* @param <T>
*/
public class LinearNode<T> {
private LinearNode<T> next;
private T element;
public LinearNode() {
next = null;
element = null;
}
public LinearNode(T elem) {
next = null;
element = elem;
}
public LinearNode<T> getNext() {
return next;
}
public void setNext(LinearNode<T> node) {
next = node;
}
public T getElement() {
return element;
}
public void setElement(T elem) {
element = elem;
}
}
package ds.java.ch05.queueImpl;
public class EmptyCollectionException extends RuntimeException
{
/**
* Sets up this exception with an appropriate message.
*/
public EmptyCollectionException (String collection)
{
super ("The " + collection + " is empty.");
}
}
package ds.java.ch05.queueImpl;
/**
* @author LbZhang
* @version 创建时间：2015年11月16日 下午7:30:59
* @description 链表实现队列
*/
public class LinkedQueue<T> implements QueueADT<T> {
private int count;
private LinearNode<T> head, tail;
// 首尾声明
/**
* 初始化队列
*/
public LinkedQueue() {
count = 0;
head = tail = null;
}
@Override
public void enqueue(T elem) {
LinearNode<T> node = new LinearNode<T>(elem);
if (isEmpty()) {// /如果是空的话初始化头结点
head = node;
} else {
tail.setNext(node);
}
tail = node;// /新结点的next不需要显式的设置 因为在new一个新结点的时候已经设置完毕
count++;
}
@Override
public T dequeue() throws EmptyCollectionException{
if (isEmpty()) {
throw new EmptyCollectionException("queue");
}
T result = head.getElement();
head = head.getNext();
count--;
if (isEmpty()) {
tail = null;// /如果栈变成了空栈
}
return result;
}
@Override
public T first() throws EmptyCollectionException{
if (isEmpty())
throw new EmptyCollectionException("queue");
return head.getElement();
}
@Override
public boolean isEmpty() {
return (count == 0);
}
@Override
public int size() {
return count;
}
@Override
public String toString() {
String result = "";
LinearNode<T> current = head;
while (current != null) {
result = result + (current.getElement()).toString() + "
";
current = current.getNext();
}
return result;
}
}
4. 数组实现队列
把数组看作是环形的，可以除去在队列的数组实现中把元素移位的需要。
package ds.java.ch05.queueImpl;
/**
* @author LbZhang
* @version 创建时间：2015年11月16日 下午10:14:12
* @description 环形数组 可以除去在队列的数组实现中元素移位的需要
*/
public class CircularArrayQueue<T> implements QueueADT<T> {
private final static int DEFAULT_CAPACITY = 100;
private int front, rear, count;
private T[] queue;// 数组队列
public CircularArrayQueue() {
this(DEFAULT_CAPACITY);
}
public CircularArrayQueue(int initc) {
front = rear = count = 0;
queue = (T[]) (new Object[initc]);
}
@Override
public void enqueue(T elem) {
if (size() == queue.length) {
expandCapacity();
}
queue[rear] = elem;
rear = (rear + 1) % queue.length;// 设置尾坐标
count++;
}
private void expandCapacity() {
// /开辟数组
T[] larger = (T[]) (new Object[queue.length * 2]);
// 复制数组
for (int scan = 0; scan < count; scan++) {
larger[scan] = queue[front];// 从front开始复制
front = (front + 1) % queue.length;
}
// /重置首尾结点
front = 0;
rear = count;
queue = larger;
}
/**
* 出队列
*/
@Override
public T dequeue() {
if (isEmpty())
throw new EmptyCollectionException("queue");
T result = queue[front];// 获取front的结点内容
queue[front] = null;// 置空front结点
front = (front + 1) % queue.length;// front后移
count--;
return result;
}
@Override
public T first() {
if (isEmpty())
throw new EmptyCollectionException("queue");
T result = queue[front];// 获取front的结点内容
return result;
}
@Override
public boolean isEmpty() {
return (count == 0);
}
@Override
public int size() {
return count;
}
@Override
public String toString() {
String result = "";
int scan = 0;
while (scan < count) {
if (queue[scan] != null) {
result += queue[scan].toString() + "
";
}
scan++;
}
return result;
}
}