队列小实现

package cn.smallbug.datastructure.queue;

/**
 * 队列接口
 * 
 * @timestamp Feb 23, 2016 3:28:20 PM
 * @author smallbug
 * @param <T>
 */
public interface Queue<T> {

	/**
	 * 入队列
	 * 
	 * @timestamp Feb 23, 2016 3:28:31 PM
	 * @param obj
	 * @return
	 */
	public boolean enQueue(T obj);

	/**
	 * 出队列
	 * 
	 * @timestamp Feb 23, 2016 3:28:51 PM
	 * @return
	 */
	public T deQueue();

	/**
	 * 队列是否为空
	 * 
	 * @timestamp Feb 23, 2016 3:28:59 PM
	 * @return
	 */
	public boolean isEmpty();

	/**
	 * 队列中元素个数
	 * 
	 * @timestamp Feb 23, 2016 3:29:36 PM
	 * @return
	 */
	public int size();

	/**
	 * 获取对头元素（不删除）
	 * 
	 * @timestamp Feb 23, 2016 3:30:03 PM
	 * @return
	 */
	public T getFirst();
}

 

package cn.smallbug.datastructure.queue;

/**
 * 队列异常
 * 
 * @timestamp Feb 23, 2016 3:50:19 PM
 * @author smallbug
 */
public class QueueException extends RuntimeException {

	/**
	 * 
	 */
	private static final long serialVersionUID = 3156992864706426492L;

	public QueueException() {

		this(null, null);

	}

	public QueueException(String message) {

		this(message, null);

	}

	public QueueException(Throwable throwable) {

		this(null, throwable);

	}

	public QueueException(String message, Throwable throwable) {

		super();
		this.message = message;
		this.throwable = throwable;

	}

	protected String message = null;

	protected Throwable throwable = null;

	public String getMessage() {

		return (message);

	}

	public Throwable getThrowable() {

		return (throwable);

	}

	public String toString() {

		StringBuilder sb = new StringBuilder("QueryException:  ");
		if (message != null) {
			sb.append(message);
			if (throwable != null) {
				sb.append(":  ");
			}
		}
		if (throwable != null) {
			sb.append(throwable.toString());
		}
		return (sb.toString());

	}

}

 

package cn.smallbug.datastructure.queue;

/**
 * 数组结构实现的队列
 * 
 * @timestamp Feb 23, 2016 3:32:44 PM
 * @author smallbug
 */
public class ArrayQueue<T> implements Queue<T> {

	private int defaultSize = 10; // 默认队列的长度
	private int front; // 队头
	private int rear; // 队尾
	private int count; // 统计元素个数的计数器
	private int maxSize; // 队的最大长度
	private T[] queue; // 队列

	/**
	 * 默认大小
	 */
	public ArrayQueue() {
		init(defaultSize);
	}

	/**
	 * 指定大小
	 * 
	 * @param maxSize
	 */
	public ArrayQueue(int maxSize) {
		if (maxSize <= 0)
			throw new IllegalArgumentException("maxSize mast greater than 0!");
		init(maxSize);
	}

	/**
	 * 初始化
	 * 
	 * @timestamp Feb 23, 2016 3:42:20 PM
	 * @param maxSize
	 */
	@SuppressWarnings("unchecked")
	private void init(int maxSize) {
		this.maxSize = maxSize;
		front = rear = 0;
		count = 0;
		queue = (T[]) new Object[maxSize];
	}

	@Override
	public boolean enQueue(T obj) {
		if (obj == null) {
			throw new QueueException("object not null!");
		}
		if (count > 0 && rear == front) {
			return false;
		}
		queue[rear] = obj;
		count++;
		rear = (rear + 1) % maxSize;
		return true;
	}

	@Override
	public T deQueue() {
		if (count == 0 && rear == front) {
			return null;
		}
		T obj = queue[front];
		queue[front] = null;
		count--;
		front = (front + 1) % maxSize;
		return obj;
	}

	@Override
	public boolean isEmpty() {
		return count == 0 ? true : false;
	}

	@Override
	public int size() {
		return count;
	}

	@Override
	public T getFirst() {
		if (count > 0)
			return queue[front];
		return null;
	}

}

 

package cn.smallbug.datastructure.queue;

/**
 * 链表结构实现的循环队列
 * 
 * @timestamp Feb 23, 2016 3:32:02 PM
 * @author smallbug
 */
public class LinkedQueue<T> implements Queue<T> {

	private Node<T> front; // 队头
	private Node<T> rear; // 队尾
	private int count; // 计数器

	private int maxSize = -1;// 最大元素个数

	public LinkedQueue() {
		init();
	}

	public LinkedQueue(int maxSize) {
		if (maxSize <= 0) {
			throw new IllegalArgumentException("maxSize mast greater than 0!");
		}
		init();
		this.maxSize = maxSize;
	}

	private void init() {
		front = rear = null;
		count = 0;
	}

	@Override
	public boolean enQueue(T obj) {
		if (obj == null) {
			throw new QueueException("object not null!");
		}
		if (maxSize != -1 && maxSize == count)
			return false;
		Node<T> node = new Node<T>(obj, null);
		if (rear != null) {
			rear.next = node;
		}
		rear = node;
		if (front == null) {
			front = node;
		}
		count++;
		return true;
	}

	@Override
	public T deQueue() {
		if (isEmpty())
			return null;
		T t = front.getElement();
		front = front.next;
		count--;
		return t;
	}

	@Override
	public boolean isEmpty() {
		return count == 0;
	}

	@Override
	public int size() {
		return count;
	}

	@Override
	public T getFirst() {
		if (!isEmpty()) {
			return front.getElement();
		} else {
			return null;
		}
	}

	private class Node<D> {

		private D element; // 数据域
		private Node<D> next; // 指针域

		// 头结点的构造方法
		public Node(Node<D> nextval) {
			this.next = nextval;
		}

		// 非头结点的构造方法
		public Node(D obj, Node<D> nextval) {
			this(nextval);
			this.element = obj;
			this.next = nextval;
		}

		// 获得当前的数据域的值
		public D getElement() {
			return this.element;
		}
	}
}

 

循环队列和链式队列的比较：

     （1）从时间上看，它们的基本操作都是常数时间，即O(1)的。不过循环队列是事先申请好空间，使用期间不释放；而链式队列，每次申请和释放结点也会存在一定的时间开销，如果入栈和出栈比较频繁，则两者还是有细微的差别。

     （2）从空间上看，循环队列必须有一个固定的长度，所以就有了存储元素个数和空间浪费的问题。而链式队列不存在这个问题，尽管它需要一个指针域，会产生一些空间上的开销，但也可以接受。所以在空间上，链式队列更加灵活。