频道栏目
首页 > 资讯 > Java > 正文

Java数据结构之何为队列

14-05-27        来源:[db:作者]  
收藏   我要投稿

没有java数据结构的基础,如何优化Android应用的性能?在实际生活中,队列有着广泛的应用,例如排队购物,文章打印,都遵循着队列先进先出的原则。队列queue在我们Handel looper thread那章中我们讲解过,今天我们重点解析下Queue的性质。

队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入,而在另一端进行删除。允许删除的一端称为队头(front),允许插入的一端称为队尾(rear)。

顺序 queue的相关概念

?进行插入操作的端称为队尾,进行删除操作的端称为队头。

?队列中没有元素时,称为空队列。

?队列空的条件: front = rear

?队列满的条件: rear = MAXSIZE

从上述相关概念中,顺序队列有一个很大的问题,容易出现假溢,如下图所示。


因此,我们设计了循环队列,将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。注意循环队列 的队列满的条件为(rear+1)%MaxSize=front,为了避免与队空条件冲突,预留了一个空间。


下面我们来看一下如何实现上述的循环队列。

package c;

public class SeqQueue implements QQueue {
	private Object[] element;
	private int front, rear;

	public SeqQueue(int size) {
		// TODO Auto-generated constructor stub
		this.element = new Object[Math.abs(size)];
		this.front = this.rear = 0;
	}
     //构造一个空的方法,默认大小为64
	public SeqQueue() {
		// TODO Auto-generated constructor stub
		this(64);
	}
    //判断队列是否为空
	@Override
	public boolean isEmpty() {
		// TODO Auto-generated method stub
		return this.front == this.rear;
	}
     //入队操作
	@Override
	public void enqueue(T x) {
		// TODO Auto-generated method stub
		if (x == null)
			return;
		//如何队列已满,重新申请一个两倍的空间
		if (this.front == (this.rear + 1) % element.length) {
			Object[] temp = this.element;
			this.element = new Object[temp.length * 2];
			int i = this.front;
			int j = 0;
			while (i != this.rear) {
				this.element[i] = temp[i];
				i = (i + 1) % temp.length;
				j++;
			}
			this.front = 0;
			this.rear = j;
		}
		this.element[this.rear] = x;
		this.rear = (this.rear + 1) % element.length;
	}
     //出队操作
	@Override
	public T dequeue() {
		// TODO Auto-generated method stub
		if (isEmpty())
			return null;
		@SuppressWarnings("unchecked")
		T temp = (T) this.element[this.front];
		this.front = (this.front + 1) % this.element.length;
		return temp;

	}
    //打印队列
	public String toString() {
		String s = "(";
		if (!isEmpty()) {
			s = s + this.element[this.front].toString();
			int i = (this.front + 1) % this.element.length;
			while (i != this.rear) {
				s = s + this.element[i].toString();
				i = (i + 1) % this.element.length;
			}
		}
		return s + ")";
	}
   //测试上述方法
	public static void main(String args[]) {
		SeqQueue queue = new SeqQueue(64);
		for (int i = 0; i < 10; i++) {
			queue.enqueue("a" + i);
		}
		System.out.print(queue.toString());
	}

}


相关TAG标签
上一篇:Uva 563 网络流
下一篇:Java 并发专题 : Timer的缺陷 用ScheduledExecutorService替代
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站