1、队列简介
队列是一个有序列表,遵循“先入先出”的原则,即先存入队列的数据要先取出,后存入的数据后取出。
队列有两种存储表示,顺序表示和链式表示。顺序表示可以用数组来实现。
2、数组模拟队列
用数组模拟队列时,设两个值front=0,rear=0。front表示队列首部第一个数据所在位置,rear表示尾部最后一个数据的下一个位置。
将数据插入数组队列时(入队),从尾部进行插入,即array[rear] = value,同时rear后移,rear++。取出数据时(出队),从头部取出数据,value = array[front],同时front后移front++。
当front=0,rear=maxSize(数组的最大长度),队列满,不能再存入数据。
这时如果执行出队操作,又有空间可以存储,但继续插入数据,会出现溢出现象,即因数组越界而导致程序非法操作错误。而实际上空间并未占满,所以称这种现象为“假溢出”。这是由“队尾入队,队头出队”的限制操作所造成的。
如何解决“假溢出”的问题呢?
答案就是循环队列。
3、数组模拟循环队列
将顺序队列变为一个环状空间,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、2、3之间循环。
front的值同理。
写了这么多字,感觉还不如看代码来得更容易理解一点。
4、代码实现:数组模拟循环队列
package com.ArrayQueue;import java.util.Scanner;publicclassCircleArrayQueueDemo{publicstaticvoidmain(String args[]){int maxSize=4;
CircleArrayQueue queue=newCircleArrayQueue(maxSize);
Scanner scanner=newScanner(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("数据添加成功。");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());}}}}/**
* 队列的顺序表示
* 数组模拟循环队列
*/classCircleArrayQueue{privateint maxSize;privateint front;//指向头元素所在位置privateint rear;//指向尾元素所在位置的下一个位置privateint arr[];//存放数据的数组//构造器,传入数组最大容量值publicCircleArrayQueue(int size){
maxSize= size;
front=0;
rear=0;//虽然数组最大容量为maxSize,但实际用于存储的只有maxSize-1
arr=newint[maxSize];}//判空条件:front == rearpublicbooleanisEmpty(){return front== rear;}//判满条件:(rear+1)%maxSize == frontpublicbooleanisFull(){return(rear+1)%maxSize== front;}//添加数据,入队publicvoidaddQueue(int n){//判满checkFull();
arr[rear]= n;
rear=(rear+1)%maxSize;}//取出数据,出队publicintgetQueue(){//判空checkEmpty();int value= arr[front];
front=(front+1)%maxSize;return value;}//队列中的有效值个数publicintsize(){return(rear-front+maxSize)%maxSize;}//展示队列的所有数据publicvoidshowQueue(){//判空checkEmpty();for(int i=front;i<front+size();i++){
System.out.printf("arr[%d]=%d\n",i%maxSize,arr[i%maxSize]);}
System.out.printf("当前front=%d,rear=%d\n",front,rear);}//展示位于队列头部的元素值,不改变front的指向publicvoidheadQueue(){//判空checkEmpty();
System.out.printf("头部数据是:%d\n",arr[front]);}//检测出队列为空时,打印当前front,rear的值,抛出异常publicvoidcheckEmpty(){if(isEmpty()){
System.out.printf("当前front=%d,rear=%d\n",front,rear);thrownewRuntimeException("队列为空,不能取数据");}}//检测出队列满时,打印当前front,rear的值,抛出异常publicvoidcheckFull(){if(isFull()){
System.out.printf("当前front=%d,rear=%d\n",front,rear);thrownewRuntimeException("队列已满,不能添加数据");}}}
运行结果: