java 数组实现队列

发表于：2010-03-10 | 零回复

　　对于 Java 来说，数据结构不象 C 语言那样需要自行实现，因为 Java 本身已经提供了丰富的数据结构。例如我们经常用来的 List、Map 等。不过自行实现一些数据结构不仅对我们的逻辑思维能力有帮助，并且让我们更加了解数据结构的底层实现。今天我们来说说 Java 中怎么利用数组来实现队列。

　　首先了解一下什么是队列：队列是一种特殊的线性表，它只允许在表的前端进行删除操作，而在表的后端进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。这也就是我们平常经常用说到的先进先出原则（FIFO）。Java 中的 List 就可以作为队列来使用，在队列尾部添加元素则使用 list.add 方法，从队列头部删除元素则使用 list.remove 方法。要用数组来实现，就必需定义进和出的下标，实现方法如下：

public class Queue {
 
	/** 默认长度 */
	private static final int DEFUALT_LENGTH = 5;
 
	/** 队列数据 */
	private Object[] objs;
	/** 队列头 */
	private int head = 0;
	/** 队列尾 */
	private int tail = 0;
	/** 队列可用长度 */
	private int length = 0;
 
	/**
	 * 初期化一个默认大小的数组
	 */
	public Queue() {
		this.objs = new Object[DEFUALT_LENGTH];
	}
 
	/**
	 * 初期化一个指定大小的数组
	 *
	 * @param int
	 */
	public Queue(int l) {
		if (l > 0) {
			this.objs = new Object[l];
		} else {
			this.objs = new Object[DEFUALT_LENGTH];
		}
	}
 
	/**
	 * 入列
	 *
	 * @param obj
	 */
	public void enQueue(Object obj) {
		// 满位的场合
		if (isFull()) {
			// 增加队列容量
			enlarge();
			head = 0;
		}
 
		this.tail = (this.head + this.length) % this.objs.length;
		this.objs[this.tail] = obj;
		length++;
	}
 
	/**
	 * 出列
	 *
	 * @return Object
	 */
	public Object deQueue() {
		if (isEmpty()) {
			return null;
		}
 
		Object tempObj = this.objs[this.head];
		this.objs[this.head] = null;
		this.head = (this.head + 1) % (this.objs.length);
		this.length--;
 
		return tempObj;
	}
 
	/**
	 * 队列是否满
	 *
	 * @return boolean
	 */
	public boolean isFull() {
		return this.length == this.objs.length;
	}
 
	/**
	 * 队列是否为空
	 *
	 * @return boolean
	 */
	public boolean isEmpty() {
		return this.length == 0;
	}
 
	/**
	 * 扩展数组容量
	 */
	public void enlarge() {
		Object[] tempObjs = new Object[this.objs.length * 2];
		System.arraycopy(this.objs, 0, tempObjs, 0, this.objs.length);
		this.objs = tempObjs;
	}
}

评论留言