顺序存储实现循环队列

在队列的实现中, 可以把数据设想为一个圆环, 这种数组称为循环数组, 用循环数组实现的队列称为循环队列；

用front指针指向 队首元素所在的单元, 使用rear指针指向队尾元素所在单元的后一个单元；

在元素入队时, 将新入队的元素保存到rear指向的单元 ,然后rear指向后移; 在出队时, 将队首指针 front指向的元素返回, 然后front后移。

如何表示队列为空还是队列满 ??

一般情况下,采用以下两种方式表示队列已满：

1、少用一个存储单元, 当队尾指针rear的下个单元是队首指针front时, 停止入队, ( rear + 1 ) % capacity == front时表示队列满, 当front == rear时表示队列为空。

2、增设一个标志表示队列为空还是满 , 通常用size变量表示元素的个数, 当size==0时队列为空, 当size==capacity时表示队列已满。

package com.wkcto.chapter02.queue;
/**
 * 队列的顺序存储实现
 * @author 蛙课网
 *
 */
public class MyArrayQueue {
	private  Object[] elements ; 		//定义数组存储队列中的元素
	private static final int DEFAULT_CAPACITY = 8;
	private int front ; 		//队首
	private int rear; 			//队尾
	private int size;			//元素的个数
	
	//构造方法
	public MyArrayQueue() {
		elements = new Object[DEFAULT_CAPACITY];
	}
	public MyArrayQueue(int initialCapacity) {
		elements = new Object[initialCapacity];
	}
	
	//返回元素的个数
	public int  getSize() {
		return size;
	}
	//判断队列是否为空
	public boolean isEmpty() {
		return size == 0 ;
	}
	
	//入队
	public void enQueue(Object e) {
		//如果队列已满 ,可以对数组扩容
		if ( size >= elements.length ) {
			expandQueue();
		}
		
		elements[rear] = e; 		//把元素存储到rear指针指向的单元
		rear = (rear+1) % elements.length;		//rear指针后移
		size++;						//元素的个数加1
	}
	//队列的数组进行扩容
	private void expandQueue() {
		//定义一个更大的数组
		Object[] newElements = new Object[elements.length * 2]; 		//默认按2倍大小扩容
				
		//把原来数组的内容复制到新的数组中, 从队首开始的元素依次复制到新数组索引值0开始的位置
		for( int i = 0 ;  i < size ; i++) {
			newElements[i] = elements[front];
			front = (front + 1) % elements.length;
		}
		
		//让原来的数组名指向新的数组
		elements = newElements;
		//调整新的队首也队尾指针
		front = 0 ; 
		rear = size;
	}
	
	//出队
	public Object  deQueue() {
		//如果队列为空
		if ( size <= 0 ) {
			//抛出一个队列为空的异常
			throw  new QueueEmptyException("队列为空");
		}
		//队列不为空, 把front指向的元素返回, 
		Object old = elements[front];
		front = (front + 1 ) % elements.length;		//front指针后移
		size--;							//元素个数减1
		return old;
	}
	//返回队首元素
	public Object peek() {
		//队列为空,抛出异常
		if (size <= 0 ) {
			throw  new QueueEmptyException("队列为空");
		}
		
		return elements[front];
	}
}

package com.wkcto.chapter02.queue;
/**
 * 自定义队列为空的异常
 * 	该异常是一个运行时异常, 不需要开发人员进行预处理
 * 	RuntimeException的子类就是运行时异常
 * @author 蛙课网
 *
 */
public class QueueEmptyException extends RuntimeException {

	public QueueEmptyException() {
		super();
	}
	//String参数,传递的是异常的信息
	public QueueEmptyException(String message) {
		super(message);
	}

}