环境
- jdk8
顺序存储实现一个循环队列，队列空或者队列满了之后，抛出异常。
实现循环队列
队列内部结构
队列中需要front指向队头元素，rear指向队尾元素的下一个位置，当
初始化的时候，队头front和队尾rear都指向0的位置。
/**
* 阻塞队列
*
*/
class BlockQueue<T>{
private Object[] data;
private int maxSize;
private int front;
private int rear;
/**
* 初始化方法
* @param maxSize
*/
public BlockQueue(int maxSize) {
this.maxSize = maxSize;
this.data = new Object[maxSize];
this.front = 0;
this.rear = 0;
}
// add()方法位置
// remove方法位置
}
队列入队方法
循环队列判断队列满的条件(rear+1)%maxSize == font，如果队列满，抛出异常。
/**
* 入队
* @param element
*/
public void add(T element) throws Exception {
// 判断队列满，队列元素满就抛出异常
boolean isFull = (rear + 1) % maxSize == front;
if (isFull) {
throw new Exception("Queue is full");
}
data[rear] = element;
rear = (rear+1)%maxSize;
printQueue();
}
队列出队方法
判断队列为空的条件是 front == rear
/**
* 移除元素
*/
public T remove() throws Exception {
// 判断队列非空，队列空则抛出异常
if (front == rear) {
throw new Exception("Queue is empty");
}
Object element = data[front];
data[front] = null;
front = (front + 1) % maxSize;
printQueue();
return (T) element;
}
测试用例
public static void main(String[] args) throws Exception {
BlockQueue<Integer> queue = new BlockQueue<Integer>(4);
queue.add(0);
queue.add(1);
queue.remove();
queue.add(2);
queue.add(3);
queue.add(4);
queue.remove();
}
/**
* 打印队列中的元素
*/
public void printQueue() {
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + " ");
}
System.out.println();
}
完整实现代码
/**
* 创建一个阻塞队列
* @author wei youchen
*/
public class QueueDemo {
public static void main(String[] args) throws Exception {
BlockQueue<Integer> queue = new BlockQueue<Integer>(4);
queue.add(0);
queue.add(1);
queue.remove();
queue.add(2);
queue.add(3);
queue.add(4);
}
/**
* 阻塞队列
*
*/
static class BlockQueue<T>{
private Object[] data;
private int maxSize;
private int front;
private int rear;
/**
* 初始化方法
* @param maxSize
*/
public BlockQueue(int maxSize) {
this.maxSize = maxSize;
this.data = new Object[maxSize];
this.front = 0;
this.rear = 0;
}
/**
* 入队
* @param element
*/
public void add(T element) throws Exception {
// 判断队列满，队列元素满就抛出异常
boolean isFull = (rear + 1) % maxSize == front;
if (isFull) {
throw new Exception("Queue is full");
}
data[rear] = element;
rear = (rear+1)%maxSize;
printQueue();
}
/**
* 移除元素
*/
public T remove() throws Exception {
// 判断队列非空，队列空则抛出异常
if (front == rear) {
throw new Exception("Queue is empty");
}
Object element = data[front];
data[front] = null;
front = (front + 1) % maxSize;
printQueue();
return (T) element;
}
/**
* 打印数组中的元素
*/
public void printQueue() {
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + " ");
}
System.out.println();
}
}
}
此外，循环队列还有一种实现方式，队列的内部结构增加一个属性——队列的长度length, 在出队和入队的时候，length做相应的加减，改判断栈空和栈满的条件是length大小，下面是此种实现方式的完整代码：
第二种实现方式
/**
* 实现循环队列方式2
*
* @author wei youchen
*/
public class QueueDemo2 {
public static void main(String[] args) throws Exception {
QueueDemo.BlockQueue<Integer> queue = new QueueDemo.BlockQueue<Integer>(4);
queue.add(0);
queue.add(1);
queue.remove();
queue.add(2);
queue.add(3);
queue.add(4);
}
/**
* 阻塞队列
*
*/
static class BlockQueue<T>{
private Object[] data;
private int maxSize;
private int front;
private int rear;
private int length;
/**
* 初始化方法
* @param maxSize
*/
public BlockQueue(int maxSize) {
this.maxSize = maxSize;
this.data = new Object[maxSize];
this.front = 0;
this.rear = 0;
this.length = 0;
}
/**
* 入队
* @param element
*/
public void add(T element) throws Exception {
// 判断队列满，队列元素满就抛出异常
if (length!=maxSize) {
throw new Exception("Queue is full");
}
data[rear] = element;
rear = (rear+1)%maxSize;
length++;
printQueue();
}
/**
* 移除元素
*/
public T remove() throws Exception {
// 判断队列非空，队列空则抛出异常
if (length != 0) {
throw new Exception("Queue is empty");
}
Object element = data[front];
data[front] = null;
front = (front + 1) % maxSize;
length--;
printQueue();
return (T) element;
}
/**
* 打印数组中的元素
*/
public void printQueue() {
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + " ");
}
System.out.println();
}
}
}
参考资料
- 大话数据结构
