Java数据结构——循环队列

普通顺序队列存在的问题
在普通顺序队列中,入队的操作就是先将尾指针rear右移一个单位，然后将元素值赋值给rear单位。出队时，则是头指针front后移一个单位。像这样进行了一定数量的入队和出队操作后，可能会出现这样的情况：
尾指针rear已指到数组的最后有一个元素，即rear==MaxLen-1，此时若再数组的前面部分可能还有很多闲置空间，即这种溢出并非是真的没有可用的存储空间，故称这种溢出现象为“假溢出”。显然，必须要解决这一块假溢出的问题，否则顺序队列就没有太多使用价值。

循环队列
循环队列的存储结构，头、尾指针都和普通顺序队列相同。不同的只是将队列视为“环状结构”，即data[0]为紧接着data[MaxLen-1]的单元，为相邻的元素，首位成为一个环。结构如下：

队列为空的条件：rear==front；
队列为满的条件：（rear+1）%maxSize==front

实现：

public class MyDlQueue {

private Object data[];

private int rear;

private int front;

private int maxSize = 10;

// 初始化队列

public MyDlQueue(int maxSize) {

if (maxSize >= 0) {

this.maxSize = maxSize;

rear = front = 0;

data = new Object[maxSize];

} else {

throw new RuntimeException("初始化队列大小不能小于0");

}

}

// 判空

public boolean empty() {

return rear == front ? true : false;

}

// 判满

public boolean full() {

//maxsize加1是因为①处的rear指向队尾的后一个

return ((rear + 1) % (maxSize + 1)) == front ? true : false;

}

// 入队

public boolean add(Object obj) {

if (full()) {

throw new RuntimeException("队满");

} else {

rear = rear % maxSize; //防止数组越界

data[rear] = obj;

rear = (rear + 1) % (maxSize + 1); //①

return true;

}

}

// 出队

public Object poll() {

if (empty()) {

throw new RuntimeException("队空");

} else {

Object value = data[front];

data[front] = null;

front = (front + 1) % maxSize;

return value;

}

}

// 获取队首元素

public Object peek() {

if (empty()) {

throw new RuntimeException("队空");

} else {

return data[front];

}

}

// 返回队列长度

public int length() {

return rear - front;

}

public static void main(String[] args) {

MyDlQueue queue = new MyDlQueue(5);

queue.add(1);

queue.add(2);

queue.add(3);

queue.add(4);

queue.add(5);

System.out.println(queue.length());

System.out.println(queue.empty());

System.out.println(queue.peek());

System.out.println(queue.poll());

queue.add("aaa");

for (Object obj : queue.data) {

System.out.print(obj + " ");

}

}

}

巴特西

Java数据结构——循环队列

最新文章

热门文章