java数据结构基础:顺序队列和循环队列

java数据结构基础:顺序队列和循环队列

目录队列：顺序队列：代码实现：循环队列：代码实现：总结

队列：

队列是一种受限制的线性表

只允许在表的一端进行插入，另一端进行删除

插入的一端称作队尾，删除的一端称作队头

具有先进先出的特性

顺序队列：

队列底层数据采用数组存储

设置队头指针front指向队头元素前一个位置，初始值为-1

设置队尾指针rear指向队尾元素，初始值为-1

判满：rear == maxSize - 1

判空：rear == front

代码实现：

//顺序队列

public class ArrayQueue {

private int maxSize; //数组的最大容量

private int front; //队头指针

private int rear; //队尾指针

private int[] array; //存放数据

public ArrayQueue(int arrMaxSize) {

maxSize = arrMaxSize;

array = new int[maxSize];

front = -1; //指向队头的前一个位置

rear = -1; //指向队尾

}

//判断队列是否满

public boolean isFull() {

return rear == maxSize - 1;

}

//判断队列是否空

public boolean isEmpty() {

return rear == front;

}

//入队

public void addQueue(int n) {

//判断队列是否满

if (isFull()) {

System.out.println("队列满");

return;

}

rear++; //rear后移

http:// array[rear] = n;

}

//出队

public int getQueue() {

//判断队列是否空

if (isEmpty()) {

throw new RuntimeException("队列为空");

}

front++; //front后移

return array[front];

}

//取队头数据

public int headQueue() {

if (isEmpty()) {

throw new RuntimeException("队列为空");

}

return array[front + 1];

}

//输出队列所有数据

public void showQueue() {

//遍历输出

if (isEmpty()) {

System.out.println("队列为空");

return;

}

for (int i = 0; i < array.length; i++) {

System.out.printf("array[%d] = %d\n", i, array[i]);

}

}

}

顺序队列存在假溢出现象，故使用循环队列替代顺序队列

循环队列：

队列底层数据仍然采用数组存储

为了便于判空和判满，在数组中预留一个空间，认为只留下一个空间的时候队列为满

设置队头指针front指向队头元素，初始值为0

设置队尾指针rear指向队尾元素的后一个位置，初始值为0

判满：(rear + 1) % maxSize == front

判空：rear == front

取得当前队列有效数据个数：(rear + maxSize - front) % maxSize

代码实现：

//循环队列

public class CircleQueue {

private int maxSize; //数组的最大容量

private int front; //队头指针

private int rear; //队尾指针

private int[] array; //存放数据

public CircleQueue(int arrMaxSize) {

maxSize = arrMaxSize;

array = new int[maxSize];

front = 0; //指向队头的前一个位置

rear = 0; //指向队尾

}

//判断队列是否满

public boolean isFull() {

return (rear + 1) % maxSize == front;

}

//判断队列是否空

public boolean isEmpty() {

return rear == front;

}

//入队

public void addQueue(int n) {

//判断队列是否满

if (isFull()) {

System.out.println("队列满");

return;

}

array[rear] = n;

rear = (rear + 1) % maxSize;

}

//出队

public int getQueue() {

//判断队列是否空

if (isEmpty()) {

throw new RuntimeException("队列为空");

}

//保存front对应的值

int value = array[front];

front = (front + 1) % maxSize;

return value;

}

//取队头数据

public int headQueue() {

if (isEmpty()) {

throw new RuntimeException("队列为空");

}

return array[front];

}

//获取当前队列有效数据个数

public int size() {

return (rear + maxSize - front) % maxSize;

}

//输出队列所有数据

public void showQueue() {

//遍历输出

if (isEmpty()) {

System.out.println("队列为空");

return;

}

//从front开始遍历

for (int i = front; i < front + size(); i++) {

System.out.printf("array[%d] = %d\n", i % maxSize, array[i % maxSize]);

}

}

}

总结

本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注我们的更多内容！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。