×
文章路径: Java > 数据结构

队列java实现

发表于3年前(Dec 24, 2014 10:24:48 AM)  阅读 481  评论 0

分类: Java 数据结构

标签: FIFO queue 先进先出 队列

队列和栈相反,是先进先出(FIFO,first in first out)的数据集合。就跟排队打饭一样,最先进入队伍的总是最先离开。

队列元素的操作一般由入列(enQueue)和出列(deQueue)组成。 按照通常理解,如果队首的人离开,队伍中所有的人将往前挪一个位置,在下面的代码里,我没有这么做,因为如果每次出列都进行一次平移,就造成了多次元素交换,影响效率,当然如果你不在乎可以进行平移。取而代之的是,用两个索引head跟tail来标记当前队首跟队尾元素的索引,避免了移位。在这里,没有实现队列的自动增长,使用索引来标记队首队尾元素,增加了自动增长的难度,其实也很简单,只是暂时觉得没有必要实现。

package cangzhitao.com.algorithms.datastructure;

import cangzhitao.com.algorithms.datastructure.exception.QueueOverFlowException;

/**
 * 队列,不支持自动增长
 * @author lihui
 *
 */
public class Queue<T> {

	private T[] arrays;
	
	/**
	 * 队列容量
	 */
	private int capacity = 10;
	
	
	/**
	 * 初始化数组
	 * @param capacity
	 * @return 泛型数组
	 */
	@SuppressWarnings("unchecked")
	private T[] initArray(int capacity) {
		return (T[]) new Object[capacity];
	}
	
	public Queue() {
		arrays = initArray(capacity);
	}
	
	public Queue(int capacity) {
		this.capacity = capacity;
		arrays = initArray(capacity);
	}
	
	/**
	 * 当前队列第一个元素的位置
	 */
	private int head = 0;
	
	/**
	 * 当前队列最后一个元素的位置
	 */
	private int tail = -1;
	
	/**
	 * 队列中的元素个数
	 */
	private int size = 0;
	
	
	public boolean isFull() {
		if(size==capacity) {
			return true;
		} else {
			return false;
		}
	}
	
	public boolean isEmpty() {
		if(size==0) {
			return true;
		} else {
			return false;
		}
	}
	
	/**
	 * 入列
	 * @param o
	 * @return
	 */
	public Queue<T> enQueue(T o) {
		boolean isFull = isFull();
		if(isFull) {
			throw new QueueOverFlowException("队列已满");
		}
		if(tail<capacity-1) {
			tail++;
		} else {
			tail = 0;
		}
		size ++;
		arrays[tail] = o;
		return this;
	}
	
	/**
	 * 出列
	 * @return
	 */
	public T deQueue() {
		boolean isEmpty = isEmpty();
		if(isEmpty) {
			throw new QueueOverFlowException("队列已空");
		}
		T o = arrays[head];
		arrays[head] = null;
		if(head<capacity-1) {
			head++;
		} else {
			head = 0;
		}
		size --;
		return o;
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Queue<Integer> q = new Queue<Integer>(5);
		q.enQueue(1);
		q.enQueue(2);
		q.enQueue(3);
		q.enQueue(4);
		q.enQueue(5);
		q.deQueue();
		q.enQueue(6);
		q.deQueue();
		q.enQueue(7);
		while(!q.isEmpty()) {
			System.out.println(q.deQueue());
		}
	}
	
}

发表评论