文章目录
队列简介
数组模拟队列（无法复用）
数组模拟环形队列（可复用）
队列简介
队列是一个有序列表，可以用数组或是链表来实现。
遵循先入先出的原则。即先存入队列的数据，先取出，后存入的后取出。
示意图：(使用数组模拟队列示意图)
有两个分别指向头部和尾部的“指针”。
数组模拟队列（无法复用）
1、实现思路
队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图，其中maxSize是该队列的最大容量。
因为队列的输出、输入是分别从前后端来处理，因此需要两个变量front及rear分别记录队列前后端的下标，front会随着数据输出而改变，而rear则是随着数据输入而改变，如图所示：
当我们将数据存入队列时称为addQueue，addQueue的处理需要有两个步骤：
①将尾指针往后移。
②若尾指针rear小于队列的最大下标maxSize-1，则将数据存入rear 所指的数组元素中，否则无法存入数据。
rear+1当front== rear[空]
rear==maxSize-1[队列满]
2、代码实现
①数组实现队列类
class ArrQueue { private int maxSize; //队列（数组）最大容量 private int front; //指向队列头部 private int rear; //指向队列尾部 private int[] queue; //创造队列的构造器 public ArrQueue(int maxSize){ this.maxSize = maxSize; queue = new int[maxSize]; front = -1; //其实是队列第一个元素的前一个索引 rear = -1; //最后一个元素的索引 } //判断是否满 public boolean isFull(){ return rear == maxSize - 1; } //判断是否空 public boolean isEmpty(){ return front == rear; } //添加元素 public void addQueue(int n){ if (isFull()){ System.out.println("队列已经满了，无法添加！"); return; }else { rear++; queue[rear] = n; } } //取出元素 public int getQueue(){ if (isEmpty()){ throw new RuntimeException("队列为空，无元素可取！"); }else { front++; return queue[front]; } } //显示队列 public void showQueue(){ if (isEmpty()){ System.out.println("队列为空，没有元素可显示！"); return; } for (int i : queue){ System.out.println(i); } } //显示头数据 public void headQueue(){ if (isEmpty()){ throw new RuntimeException("队列为空，没有头数据！"); } int i = front; System.out.println(queue[++i]); } }
②测试类
import java.util.Scanner; /** * @Author: Yeman * @Date: 2021-10-11-22:02 * @Description: */ public class ArrayQueueTest { public static void main(String[] args) { //创建一个队列 ArrQueue arrQueue = new ArrQueue(3); //创建一个用户输入 Scanner scanner = new Scanner(System.in); //创建一个功能菜单 char key = ' '; boolean isShow = true; while (isShow){ System.out.println("s:显示队列"); System.out.println("a:添加数据"); System.out.println("g:取出数据"); System.out.println("h:显示头数据"); System.out.println("e:退出程序"); key = scanner.next().charAt(0); switch (key){ case 's' : arrQueue.showQueue(); break; case 'a' : System.out.println("请输入一个数："); int value = scanner.nextInt(); arrQueue.addQueue(value); break; case 'g' : try { System.out.println(arrQueue.getQueue()); } catch (Exception e) { e.printStackTrace(); } break; case 'h' : try { arrQueue.headQueue(); } catch (Exception e) { e.printStackTrace(); } break; case 'e' : isShow = false; break; } } System.out.println("程序退出..."); } }
数组模拟环形队列（可复用）
对前面的数组模拟队列的优化，充分利用数组。将数组看做是一个环形的，即取出之后，有位置可以空出来添加。(通过取模的方式来实现即可)
分析说明:
①尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定。在作判断队列满的时候需要注意(rear+ 1) % maxSize== front [满]
②rear == front [空]
1、思路如下:
①front 变量的含义调整：front 指向队列的第一个元素, 也就是说arr[front]就是队列的第一个元素，front的初始值为0。
②rear 变量的含义调整：rear 指向队列的最后一个元素的后一个位置，因为希望空出一个空间做为约定，rear的初始值=0。
③当队列满时，条件是(rear + 1) % maxSize == front [满]
④对队列为空的条件是rear== front[空]
⑤当我们这样分析，队列中有效的数据的个数(rear + maxSize - front) % maxSize
⑥我们就可以在原来的队列上修改得到一个环形队列
2、代码实现
①数组实现环形队列类
class ArrQueue { private int maxSize; //队列（数组）最大容量 private int front; //指向队列头部，队列第一个元素的索引 private int rear; //指向队列尾部，队列最后一个元素的后一个索引 private int[] queue; //创造队列的构造器 public ArrQueue(int maxSize){ this.maxSize = maxSize; queue = new int[maxSize]; } //判断是否满 public boolean isFull(){ return (rear + 1) % maxSize == front; } //判断是否空 public boolean isEmpty(){ return front == rear; } //添加元素 public void addQueue(int n){ if (isFull()){ System.out.println("队列已经满了，无法添加！"); return; }else { queue[rear] = n; rear = (rear + 1) % maxSize; } } //取出元素 public int getQueue(){ if (isEmpty()){ throw new RuntimeException("队列为空，无元素可取！"); }else { int data = queue[front]; front = (front + 1) % maxSize; return data; } } //显示队列 public void showQueue(){ if (isEmpty()){ System.out.println("队列为空，没有元素可显示！"); return; } for (int i = front; i < front + size(); i++) { System.out.printf("arr[%d] = %d\n",i % maxSize,queue[i % maxSize]); } } //求当前队列有效数据个数 public int size(){ return (rear + maxSize - front) % maxSize; } //显示头数据 public void headQueue(){ if (isEmpty()){ throw new RuntimeException("队列为空，没有头数据！"); } System.out.println(queue[front]); } }
②测试类
import java.util.Scanner; /** * @Author: Yeman * @Date: 2021-10-11-22:02 * @Description: */ public class ArrayQueueTest { public static void main(String[] args) { //创建一个队列 ArrQueue arrQueue = new ArrQueue(3); //说明该环形队列的最大有效数据为2 //创建一个用户输入 Scanner scanner = new Scanner(System.in); //创建一个功能菜单 char key = ' '; boolean isShow = true; while (isShow){ System.out.println("s:显示队列"); System.out.println("a:添加数据"); System.out.println("g:取出数据"); System.out.println("h:显示头数据"); System.out.println("e:退出程序"); key = scanner.next().charAt(0); switch (key){ case 's' : arrQueue.showQueue(); break; case 'a' : System.out.println("请输入一个数："); int value = scanner.nextInt(); arrQueue.addQueue(value); break; case 'g' : try { System.out.println(arrQueue.getQueue()); } catch (Exception e) { e.printStackTrace(); } break; case 'h' : try { arrQueue.headQueue(); } catch (Exception e) { e.printStackTrace(); } break; case 'e' : isShow = false; break; } } System.out.println("程序退出..."); } }
