数据结构-队列-数组队列
自定义队列
数组队列
简述：
队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队列的最大容量。
因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front及 rear分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear则是随着数据输入而改变，如图所示:
- 自定义简单数组对列（有问题，不能重复使用）
package com.njau.queue;
import java.util.Scanner;
/** * @author 张文军 * @Description:arrayQueue数组队列 * @Company:南京农业大学工学院 * @version:1.0 * @date 2019/8/249:06 */
public class ArrayQueue {
int maxiSize;
int front;
int rear;
int[] arr;
public ArrayQueue(int maxiSize) {
this.maxiSize = maxiSize;
arr = new int[maxiSize];
front = -1;
rear = -1;
}
public Boolean isFull() {
return rear == maxiSize - 1;
}
public boolean isEmpty() {
return rear == front;
}
public void addQueue(int n) {
if (isFull()) {
System.out.println("queue hase full !");
return;
} else {
arr[++rear] = n;
}
}
public int getQueue() {
if (isEmpty()) {
throw new RuntimeException("queue is empty !");
} else {
return arr[++front];
}
}
public void showQueue() {
if (!isEmpty()) {
for (int i = 0; i < arr.length; i++) {
System.out.printf("arr[%d] = %d\n", i, arr[i]);
}
} else {
System.out.println("queue is empty !");
}
}
public int getQueueHead() {
if (isEmpty()) {
throw new RuntimeException("queue is empty!");
} else {
return arr[front + 1];
}
}
/** * 测试 */
public static void main(String[] args) {
ArrayQueue queue = new ArrayQueue(3);
Scanner scanner = new Scanner(System.in);
Boolean loop = true;
while (loop) {
System.out.println("s 展示");
System.out.println("a 添加");
System.out.println("g 取数据");
System.out.println("h 显示头数据");
System.out.println("e 退出");
char key = scanner.next().charAt(0);
switch (key) {
case 's':
queue.showQueue();
break;
case 'a':
System.out.println("请输入数据：");
int i = scanner.nextInt();
queue.addQueue(i);
break;
case 'g':
try {
int queue1 = queue.getQueue();
System.out.println("取出的数据是:" + queue1);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'h':
try {
int queueHead = queue.getQueueHead();
System.out.println("头数据:" + queueHead);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'e':
loop = false;
break;
default:
break;
}
}
System.out.println("exit !");
}
}
数组环形队列
上面简介和用数组简单实现了一下队列，但这种队列依然存在问题，问题就是用数组简单实现的队列会存在假溢出现象（即：在数据退出队列时，虽然数据未满，但是队列的 rear 已经是数组的大小，即显示已满。故不能继续插入数据 ），这样会极大的降低了数组的利用，所以，在这里我将会用数组实现一个环形队列，以解决这种问题。
-
首先在这里，声明了一个容量大小为8的数组，并标出了索引0-7，然后使用front和 rear 分别来表示队列的，队首和队尾；在下图中，front 和 rear 的位置一开始都指向是了索引0的位置，这意味着当front == rear 的时候 队列为空 ，务必牢记这一点，以便区分后面介绍队列快满时的临界条件
-
front：表示队列队首，始终指向队列中的第一个元素（当队列空时，front指向索引为0的位置）
-
rear ：表示队列队尾，始终指向队列中的最后一个元素的下一个位置
-
元素入队，维护rear 的位置，进行rear ++操作
-
元素出队，维护front的位置，进行front++操作
按照上面的front和rear的意思，对队列的维护即对是简单的++操作，即：入队就是将rear++，front不变，出队就是front++，rear不变。
即如下图所示：
然而，如果再向后面添加，即当出现
即当rear指向数组的最后，而且队列也已经有元素出队时，应为rear不能再向后移动，所以虽然数组有空的空间，但却不能插入数据，此时就出现了数组假溢出现象。然而，如果rear的位置用（rear+1)% maxSize ，则就会避免出现这种情况，即我们将现在的数组看成是一个环，当rear=front=0时，数组为空，插入一条数据，rear = （rear+1 ）%maxSize = 1%8= 1； 当队列上图情况时，即rear已经是移动到数组的最后一个位置，而且有数据已经出队时，这时插入数据时，rear = （rear+1 ）% maxSize = （7+1）%8 = 0，即循环到了下一个位置。同理，front的位置决定也是：front= (front+1)%maxSize，在这种情况下，必须要牺牲一个数组空间来（用于方便判断），而且判断队列是否已满的条件是rear==(front+1)%maxSize，为空rear==front ==0；
代码实现如下：
package com.njau.queue;
/** * @author 张文军 * @Description:数组循环队列 * @Company:南京农业大学工学院 * @version:1.0 * @date 2019/9/23:42 */
public class ArrayCycleQueue {
/** * 数组大小 */
int maxiSize;
/** * 指向队列的头元素 */
int front;
/** * 指向队列的最后一个元素的下一个元素 */
int rear;
/** * 数组 */
int[] arr;
public ArrayCycleQueue(int maxiSize) {
this.maxiSize = maxiSize;
arr = new int[maxiSize];
front = 0;
rear = 0;
}
public Boolean isFull() {
return front == (rear + 1) % maxiSize;
}
public boolean isEmpty() {
return rear == front;
}
public void addQueue(int n) {
if (isFull()) {
System.out.println("queue is full !");
return;
} else {
arr[rear] = n;
rear = (rear + 1) % maxiSize;
}
}
public int getQueue() {
if (isEmpty()) {
throw new RuntimeException("queue is empty !");
} else {
int popData = arr[front];
front = (front + 1) % maxiSize;
return popData;
}
}
public void showQueue() {
if (!isEmpty()) {
for (int i = 0; i < arr.length; i++) {
System.out.printf("arr[%d] = %d\n", i, arr[i]);
}
} else {
System.out.println("queue is empty !");
}
}
public int getQueueHead() {
if (isEmpty()) {
throw new RuntimeException("queue is empty!");
} else {
return arr[front];
}
}
}
测试：
public static void main(String[] args) {
ArrayCycleQueue queue = new ArrayCycleQueue(3);
Scanner scanner = new Scanner(System.in);
Boolean loop = true;
while (loop) {
System.out.println("s 展示");
System.out.println("a 添加");
System.out.println("g 取数据");
System.out.println("h 显示头数据");
System.out.println("e 退出");
char key = scanner.next().charAt(0);
switch (key) {
case 's':
queue.showQueue();
break;
case 'a':
System.out.println("请输入数据：");
int i = scanner.nextInt();
queue.addQueue(i);
break;
case 'g':
try {
int queue1 = queue.getQueue();
System.out.println("取出的数据是:" + queue1);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'h':
try {
int queueHead = queue.getQueueHead();
System.out.println("头数据:" + queueHead);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case 'e':
loop = false;
break;
default:
break;
}
}
System.out.println("exit !");
}
国家电网工作强度 101人发布