Java队列
在队列的实现中, 可以把数据设想为一个圆环, 这种数组称为循环数组, 用循环数组实现的队列称为循环队列;
用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);
}
}