文章目录

一次性数组模拟队列数组模拟环形队列

一次性数组模拟队列

队列先进先出，队列的输出、输入分别从前端、后端处理，需要2个变量front及rear分别记录队列前后端的下标，front随着输出改变，rear随着输入改变添加队列元素步骤： 尾指针后移 且小于最大下标 import java.util.Scanner; public class ArrayQueueDemo { public static void main(String[] args) { //测试队列 ArrayQueue queue = new ArrayQueue(3); boolean loop=true; while (loop){ System.out.println("添加元素请按a ："); System.out.println("取出元素请按g ："); System.out.println("显示第一个元素请按h ："); System.out.println("显示元素请按s ："); Scanner scanner = new Scanner(System.in); String key = scanner.next(); switch (key){ case "a": System.out.println("请输入一个数字："); int n = scanner.nextInt(); queue.addQueue(n); break; case "g": try { int i = queue.getQueue(); System.out.println("去除的数字是："+i); } catch (Exception e) { e.printStackTrace(); } break; case "h": try { System.out.println("队列的头部是： "+queue.headQueue()); } catch (Exception e) { e.printStackTrace(); } break; case "s": queue.showQueue(); break; case "e": scanner.close(); loop=false; break; default: break; } } System.out.println("程序退出."); } } class ArrayQueue{ private int MaxSize; private int front; private int rear; private int[] arr; //初始化队列构造函数 public ArrayQueue(int maxSize) { MaxSize = maxSize; arr=new int[maxSize]; front=-1;//输出上移 指向头部前一个位置 rear=-1;//输入上移 指向尾部最后一个位置 } //判断队列是否满 public boolean isfull(){ //队列满表示尾部索引在最后一个位置 return rear==MaxSize-1; } //判断队列是否为空 public boolean isempty(){ //队列空表示头部索引与尾部索引重合 例如初始化的时候 return rear==front; } //添加数据到队列 public void addQueue(int element){ if (isfull()){ System.out.println("队列已满不可添加"); return; } rear++; arr[rear]=element; } //获取队列元素 public int getQueue(){ if (isempty()){ throw new RuntimeException("队列为空，没有数据可取"); } front++; return arr[front]; } //显示队列的所有元素 public void showQueue(){ if (isempty()){ System.out.println("队列为空，没有数据可取"); return; } for (int i = 0; i < arr.length; i++) { System.out.printf("arr[%d]==%d\n",i,arr[i]); } } //显示队列头元素 public int headQueue(){ if (isempty()){ throw new RuntimeException("队列为空，没有数据可取"); } return arr[front+1]; } }

此代码的弊端：

取出数据后再次展示元素还在，只是索引front的指向发生变化当添加元素已满时，再全部取出，此时再添加，会显示队列已满，rear=front=maxSize-1

解决方式：将数组使用算法，改为环形队列。取模

数组模拟环形队列

取模的理解：为了将一次性队列改为循环队列，引入取模的方法，%maxSize，当小于maxSize时，没有影响；一旦等于maxSize，就会又从0开始，形成了循环。 取余的作用就是相等时将结果置为0。 无论出队入队，当前面元素取出rear在最后一个位置时取模才能让继续从0开始添加；否则会造成指针溢出。

队列满的理解：空时rear=front，那么满时可以保留一个元素空间，也就是数组中还有一个空闲单元。就表示队列已满。 所以a4就表示数组的最后一个元素，而rear指向最后一个元素的下一个位置。 下图是满的两种情况： 队列满的条件是：（rear+1）%MaxSize==front 针对于第一种情况如果条件为rear+1==front的话就不满足，需要通过取模将rear+1的值循环起来，一旦rear+1=maxSize就将rear+1至为0与front比较，此时的条件依然满足第二种rear<front的情况，因为rear+1<maxSize,取模依旧为本值，不影响。

循环队列有效长度的理解： 如上左图，当rear>front，队列元素个数为rear-front；当rear<front时，如上右图，计算元素个数分为两段：第一段为rear-0；第二段为maxSize-front，相加为rear-front+maxSize；如果rear=0，front=0时，队列为空，此时有效长度为0，因此需要将结果置为0，取模，所以最终公式为（rear-front+maxSize）%maxSize。

import java.util.Scanner; public class CircleArrayQueueDemo { public static void main(String[] args) { //测试队列 CircleArrayQueue queue = new CircleArrayQueue(4);//设置是4，有效数据为3，因为有预留空间 boolean loop=true; while (loop){ System.out.println("添加元素请按a ："); System.out.println("取出元素请按g ："); System.out.println("显示第一个元素请按h ："); System.out.println("显示元素请按s ："); Scanner scanner = new Scanner(System.in); String key = scanner.next(); switch (key){ case "a": System.out.println("请输入一个数字："); int n = scanner.nextInt(); queue.addQueue(n); break; case "g": try { int i = queue.getQueue(); System.out.println("取出的数字是："+i); } catch (Exception e) { e.printStackTrace(); } break; case "h": try { System.out.println("队列的头部是： "+queue.headQueue()); } catch (Exception e) { e.printStackTrace(); } break; case "s": queue.showQueue(); break; case "e": scanner.close(); loop=false; break; default: break; } } System.out.println("程序退出."); } } class CircleArrayQueue{ private int MaxSize; private int front; private int rear; private int[] arr; //初始化队列构造函数 public CircleArrayQueue(int maxSize) { MaxSize = maxSize; arr=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 element){ if (isfull()){ System.out.println("队列已满不可添加"); return; } //因为rear指向最后一个元素的后一个位置，rear索引处元素为空，直接在此处添加元素，再后移rear到下一个空位置 arr[rear]=element; //rear如果在最后一个位置，要将元素添加最后一个位置后，移动到0位置时需要取模；其余情况直接后移 rear=(rear+1)%MaxSize; } //获取队列元素 public int getQueue(){ if (isempty()){ throw new RuntimeException("队列为空，没有数据可取"); } //front是指向队列的第一个元素，首先先保存front的值，然后后移front，最后返回先保存的值 int value=front; front=(front+1)%MaxSize; return arr[value]; } //显示队列的所有元素 public void showQueue(){ if (isempty()){ System.out.println("队列为空，没有数据可取"); return; } //如果队列前面为空，后面一部分有元素，就没有必要展示 //思路：从front开始遍历有效元素个数个元素 int length=(rear-front+MaxSize)%MaxSize; for (int i = front; i < front+length; i++) { System.out.printf("arr[%d]==%d\n",i%MaxSize,arr[i%MaxSize]);//i有可能越界因此要取模 } } //显示队列头元素 public int headQueue(){ if (isempty()){ throw new RuntimeException("队列为空，没有数据可取"); } return arr[front];//front就是指头元素，不需要+1 } }