Java基础之数组模拟循环队列

Java基础之数组模拟循环队列

一、队列简介

队列是一个有序列表，遵循“先入先出”的原则，即先存入队列的数据要先取出，后存入的数据后取出。

队列有两种存储表示，顺序表示和链式表示。顺序表示可以用数组来实现。

二、数组模拟队列

用数组模拟队列时，设两个值front=0，rear=0。front表示队列首部第一个数据所在位置，rear表示尾部最后一个数据的下一个位置。

将数据插入数组队列时（入队），从尾部进行插入,即array[rear] = value,同时rear后移，rear++。取出数据时（出队），从头部取出数据,value = array[front]，同时front后移front++。

当front=0，rear=maxSize（数组的最大长度），队列满，不能再存入数据。

这时如果执行出队操作，又有空间可以存储，但继续插入数据，会出现溢出现象，即因数组越界而导致程序非法操作错误。而实际上空间并未占满，所以称这种现象为“假溢出”。这是由“队尾入队，队头出队”的限制操作所造成的。

如何解决“假溢出”的问题呢？

答案就是循环队列。

三、数组模拟循环队列

将顺序队列变为一个环状空间，front、rear和队列元素之间的关系不变，只是在循环队列中，front、rear依次后移加1的操作可用“模”运算来实现。

通过取模，front、rear就可以在顺序表空间内以头尾衔接的方式“循环”移动。

元素出队后，front = （front+1）%maxSize ；

元素入队后，rear = （rear+1）%maxSize 。

（maxSize为数组队列的最大长度）

例如，队列最大长度为4，当rear=3时，存入数据，array[3]=value,rear后移一位，如果没有取模运算，则rear=4，这时继续插入数据，array[4]越界。

如果进行取模运算，rear = （rear+1）%maxSize ，这时rear=0，rear又重新回到了0的位置。这样的运算，使得rear的值在0、1、kuwmfmrQ2、3之间循环。

front的值同理。

写了这么多字，感觉还不如看代码来得更容易理解一点。

四、代码实现

数组模拟循环队列

package com.ArrayQueue;

import java.util.Scanner;

public class CircleArrayQueueDemo {

public static void main(String args[]){

int maxSize = 4;

CircleArrayQueue queue = new CircleArrayQueue(maxSize);

Scanner scanner = new Scanner(System.in);

char key;

boolean loop = true;

while (loop) {

//根据输入的不同字母，进行对应的操作

System.out.println("a(add):添加一个数据");

System.out.println("g(get):取出一个数据");

System.out.println("h(head):展示头部数据");

System.out.println("s(show):展示所有数据");

System.out.println("q(quit):退出程序");

//因为判满条件的缘故，队列的最大容量实为maxSize-1

System.out.printf("(队列的最大容量为：%d)\n",maxSize-1);

key = scanner.next().charAt(0);//接收一个字符

try {

switch (key) {

case 'a':

System.out.println("请输入一个数：");

int value = scanner.nextInt();

queue.addQueue(value);

System.out.println("数据添加成功。");

http:// break;

case 'g':

System.out.printf("取出的数据为：%d\n", queue.getQueue());

break;

case 'h':

queue.headQueue();

break;

case 's':

queue.showQueue();

break;

case 'q':

scanner.close();

loop = false;

System.out.println("程序已退出。");

break;

default:

break;

}

} catch (RuntimeException e) {

System.out.println(e.getMessage());

}

}

}

}

/**

* 队列的顺序表示

* 数组模拟循环队列

*/

class CircleArrayQueue{

private int maxSize;

private int front;//指向头元素所在位置

private int rear;//指向尾元素所在位置的下一个位置

private int arr[];//存放数据的数组

//构造器，传入数组最大容量值

public CircleArrayQueue(int size){

maxSize = size;

front = 0;

rear = 0;

//虽然数组最大容量为maxSize，但实际用于存储的只有maxSize-1

arr = new int[maxSize];

}

//判空条件：front == rear

public boolean isEmpty(){

return front == rear;

}

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

public boolean isFull(){

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

}

//添加数据，入队

public void addQueue(int n){

//判kuwmfmrQ满

checkFull();

arr[rear] = n;

rear = (rear+1)%maxSize;

}

//取出数据，出队

public int getQueue(){

//判空

checkEmpty();

int value = arr[front];

front = (front+1)%maxSize;

return value;

}

//队列中的有效值个数

public int size(){

return (rear-front+maxSize)%maxSize;

}

//展示队列的所有数据

public void showQueue(){

//判空

checkEmpty();

for(int i=front;i

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

}

System.out.printf("当前front=%d,rear=%d\n",front,rear);

}

//展示位于队列头部的元素值，不改变front的指向

public void headQueue(){

//判空

checkEmpty();

System.out.printf("头部数据是：%d\n",arr[front]);

}

//检测出队列为空时，打印当前front，rear的值，抛出异常

public void checkEmpty(){

if (isEmpty()) {

System.out.printf("当前front=%d,rear=%d\n",front,rear);

throw new RuntimeException("队列为空,不能取数据");

}

}

//检测出队列满时，打印当前front，rear的值，抛出异常

public void checkFull(){

if(isFull()){

System.out.printf("当前front=%d,rear=%d\n",front,rear);

throw new RuntimeException("队列已满，不能添加数据");

}

}

}

五、运行结果

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

}

System.out.printf("当前front=%d,rear=%d\n",front,rear);

}

//展示位于队列头部的元素值，不改变front的指向

public void headQueue(){

//判空

checkEmpty();

System.out.printf("头部数据是：%d\n",arr[front]);

}

//检测出队列为空时，打印当前front，rear的值，抛出异常

public void checkEmpty(){

if (isEmpty()) {

System.out.printf("当前front=%d,rear=%d\n",front,rear);

throw new RuntimeException("队列为空,不能取数据");

}

}

//检测出队列满时，打印当前front，rear的值，抛出异常

public void checkFull(){

if(isFull()){

System.out.printf("当前front=%d,rear=%d\n",front,rear);

throw new RuntimeException("队列已满，不能添加数据");

}

}

}

五、运行结果

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