Java 数组模拟队列 + 优化

队列介绍

队列是一个有序列表，可以用数组或是链表来实现。 遵循先入先出的原则。

即：先存入队列的数据，要先取出。后存入的要后取出 示意图：(使用数组模拟队列示意图)

 

 

 数组模拟队列

队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队列的最大容量。

因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front及 rear分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear则是随着数据输入而改变，

如图所示:

当我们将数据存入队列时称为"addQueue"，

addQueue 的处理需要有两个步骤：

思路分析 将尾指针往后移：

　　rear+1 , 当front == rear 【空】 若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear所指的数组元素中，否则无法存入数据。

　　rear == maxSize - 1[队列满] 代码实现 问题分析并优化

 

代码实现

package com.lin.queue_0131;import java.util.Scanner;public class Array_Queue { public static void main(String[] args) {  ArrayQueue arrayQueue = new ArrayQueue(4);  Scanner scanner = new Scanner(System.in);  char c;  while(true) {   System.out.println("------------------------------");   System.out.println("|");   System.out.println("|");   System.out.println("------------------------------");   System.out.println("-1 s(show):显示队列, -2 e(exit)：退出程序, -3 a(add)：添加数据到队列, -4 g(get)：获取队列的数据, -5 h(head):查看队列头数据 ");   System.out.println("请输入以上提示字符：");   c = scanner.next().charAt(0);   switch (c) {   case 's':    arrayQueue.showQueue();    break;   case 'e':    System.exit(0);    break;   case 'a':    System.out.println("请输入添加数据：");    int n = scanner.nextInt();    arrayQueue.addQueue(n);    break;   case 'g':    try {     System.out.println("出队：" + arrayQueue.getQueue());    } catch (NullQueueException e) {     System.err.println(e.getMessage());    }    break;   case 'h':    try {     System.out.println("头数据：" + arrayQueue.headQueue());    } catch (NullQueueException e) {     System.err.println(e.getMessage());    }    break;   default:    break;   }  } }}class ArrayQueue{  private int fornt; private int rear; private int maxSize; private int[] arr;  // 创建队列构造器 public ArrayQueue(int maxSize){  this.arr = new int[maxSize];  this.maxSize = maxSize;  this.rear = -1;  // 指向队尾的数据  this.fornt = -1; // 指向队列头的前一位置 }  // 判断队列是否已满 public boolean isFull() {  return rear == (maxSize - 1); }  // 判断队列是否为空 public boolean isEmpty() {  return rear == fornt; }  // 入队 public void addQueue(int n) {  if(!isFull()) {   arr[++rear] = n;   System.out.println("添加成功！");  } else {   System.out.println("队列已满！");  } }  // 出队 public int getQueue() throws NullQueueException {  if(isEmpty()) {   throw new NullQueueException("队列为空！"); // 自定义异常  }  int arrNum = arr[++fornt];  arr[fornt] = 0;  return arrNum;   }  // 遍历队列 public void showQueue() {  if(isEmpty()) {   System.out.println("队列为空，无法输出数据！");   return;  }  for (int i = 0; i < arr.length; i++) {   System.out.print("arr[" + i + "] = " + arr[i] + "\t");  }  System.out.println(); }  // 显示队列的头数据 public int headQueue() throws NullQueueException {  if(isEmpty()) {   throw new NullQueueException("队列为空！"); // 自定义异常  }  return arr[fornt +1]; }}
注意：没有优化的代码数组只能用一次，即使队列为空，也无法添加数据。

优化后的代码
环形队列调整思路（其中的一种办法）：
front变量的含义：front指向队列的第一个元素，也就是说arr[front]就是队列的第一个元素，之前的front是指向队列头元素的前一个位置。初始值为0。 
rear变量的含义：rear指向队列的最后一个元素的后一个位置。希望空出一个空间作为约定。初始值为0。
当队列满时，条件是(rear + 1)%maxSize == front。
当队列为空时，条件是rear == front。
有效个数：(rear + maxSize - front)%maxSize。

package com.lin.queue_0131;import java.util.Scanner;public class ArrayQueuePuls {  public static void main(String[] args) { ArrayQueue2 arrayQueue2 = new ArrayQueue2(4); Scanner scanner = new Scanner(System.in); char c; while(true) {  System.out.println("------------------------------");  System.out.println("|");  System.out.println("|");  System.out.println("------------------------------");  System.out.println("-1 s(show):显示队列, -2 e(exit)：退出程序, -3 a(add)：添加数据到队列, -4 g(get)：获取队列的数据, -5 h(head):查看队列头数据,-1 printFornt,-2 printRear ");  System.out.println("请输入以上提示字符：");  c = scanner.next().charAt(0);  switch (c) {  case 's':   arrayQueue2.showQueue();   break;  case 'e':   System.exit(0);   break;  case 'a':   System.out.println("请输入添加数据：");   int n = scanner.nextInt();   arrayQueue2.addQueue(n);   break;  case 'g':   try {    System.out.println("出队：" + arrayQueue2.getQueue());   } catch (NullQueueException e) {    System.err.println(e.getMessage());   }   break;  case 'h':   try {    System.out.println("头数据：" + arrayQueue2.headQueue());   } catch (NullQueueException e) {    System.err.println(e.getMessage());   }   break;  case '1':   arrayQueue2.printFront();   break;  case '2':   arrayQueue2.printRear();   break;  default:   break;  } }}}class ArrayQueue2{  private int fornt; private int rear; private int maxSize; private int[] arr;  // 创建队列构造器 public ArrayQueue2(int maxSize){  this.arr = new int[maxSize];  this.maxSize = maxSize;  this.rear = 0;  // 指向队尾的数据  this.fornt = 0; // 指向队列头的前一位置 }  // 判断队列是否已满 public boolean isFull() {  return (rear + 1)%maxSize == fornt;  }  // 判断队列是否为空 public boolean isEmpty() {  return rear == fornt; }  // 入队 public void addQueue(int n) {  if(!isFull()) {   arr[rear] = n;   rear = (rear + 1)%maxSize;   System.out.println("添加成功！");  } else {   System.out.println("队列已满！");  }   }  // 出队 public int getQueue() throws NullQueueException {  if(isEmpty()) {   throw new NullQueueException("队列为空！"); // 自定义异常  }  int arrNum = arr[fornt];  fornt = (fornt + 1)%maxSize;  return arrNum;   }  // 遍历队列 public void showQueue() {  if(isEmpty()) {   System.out.println("队列为空，无法输出数据！");   return;  }  for (int i = fornt; i < fornt + numSize(); i++) {    System.out.print("arr[" + i%maxSize + "] = " + arr[i%maxSize] + "\t");  }  System.out.println(); }  public int numSize() {  return (rear + maxSize - fornt)%maxSize; // (rear + maxSize - fornt)%maxSize环形队列元素的实际个数 } // 显示队列的头数据 public int headQueue() throws NullQueueException {  if(isEmpty()) {   throw new NullQueueException("队列为空！"); // 自定义异常  }  return arr[fornt]; } public void printFront() {  System.out.println(this.fornt); } public void printRear() {  System.out.println(this.rear); }}

虽然数组size为4，但容量只有3

最后，fornt单词写错了，应该是front。

 

仅供参考，有错误还请指出！

有什么想法，评论区留言，互相指教指教。

原文转载：http://www.shaoqun.com/a/521230.html

跨境电商：https://www.ikjzd.com/

ideal：https://www.ikjzd.com/w/2286

友家速递：https://www.ikjzd.com/w/1341

队列介绍队列是一个有序列表，可以用数组或是链表来实现。遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出示意图：(使用数组模拟队列示意图)数组模拟队列队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图,其中maxSize是该队列的最大容量。因为队列的输出、输入是分别从前后端来处理，因此需要两个变量front及rear分别记录队列前后端的下标，front会
急速：急速
瀚霖：瀚霖
eBay全线沟通模板！基本等于全部身家：eBay全线沟通模板！基本等于全部身家
优秀的亚马逊选品有哪些流程？具体应该怎样操作？：优秀的亚马逊选品有哪些流程？具体应该怎样操作？
如何有效降低推广成本？这些方法一定要知道！：如何有效降低推广成本？这些方法一定要知道！