队列(Queue)。队列简称队。是一种操作受限的线性表,只允许在表的一端进行插入,而在表的另一端进行删除。向队列中插入元素称为入队或进队;删除元素称为出队或离队。其操作特性为先进先出(First In First Out,FIFO),并且只允许在队尾进,队头出。
先定义两个指针,front用于指向头部元素,rear用于指向尾部元素。当取出元素时front指针后移,当存入元素时rear指针后移。front、rear默认值-1。
两个理解点:
代码实现:
package com.zlp.datastructure.controller; import java.util.Arrays; import java.util.Scanner; public class Queue { public static void main(String[] args) { // 创建队列 System.out.println("请输入队列长度:"); Scanner scanner = new Scanner(System.in); int size = scanner.nextInt(); ArrayQueue arrayQueue = new ArrayQueue(size); boolean flag = true; while (flag) { // 操作指南 System.out.println("显示队列:1"); System.out.println("添加数据:2"); System.out.println("取出数据:3"); System.out.println("结束:4"); int choose = scanner.nextInt(); switch (choose) { case 1: arrayQueue.showQueue(); break; case 2: System.out.println("请输入要添加的数据:"); int data = scanner.nextInt(); arrayQueue.addQueue(data); System.out.println("数据添加成功~"); break; case 3: int queue = arrayQueue.getQueue(); System.out.println("数据取出:" + queue); break; case 4: System.out.println("程序结束~"); return; default: System.out.println("输入错误~"); break; } } } } class ArrayQueue{ private int maxSize; private int front;// 头指针 private int rear;// 尾指针 private int[] arr; // 队列构造方法 public ArrayQueue(int size) { maxSize = size; arr = new int[maxSize]; front = -1; rear = -1; } // 判断队列是否满 public boolean isFull() { return rear == maxSize - 1; } // 判断队列是否为空 public boolean isEmpty() { return front == rear; } // 添加数据到队列 public void addQueue(int data) { // 判断是否队列满 if (isFull()) { System.out.println("队列已满~"); return; } rear++;// 尾指针后移 arr[rear] = data; } // 取出数据 public int getQueue() { // 判断为空 if (isEmpty()) { System.out.println("队列为空~"); return 0; } front++; // 头指针后移 return arr[front]; } // 显示所有队列数据 public void showQueue() { if (isEmpty()) { System.out.println("队列为空~"); return; } System.out.println(Arrays.toString(arr)); } // 显示队列头数据 public int headQueue() { if (isEmpty()) { System.out.println("队列为空~"); return 0; } return arr[front + 1]; } }
问题分析:
数组实现有个明显的缺点:这个队列我们只能用一次,不能重复使用,循环队列便可以解决这个问题。
利用数组取模,从而时数组形成环形。
一句话看起来抽象,我们举个例子:
比如该数组长度maxSize为3,也就是坐标有三种情况 0、1、2,这时候我们有一个指针index,当index=1时,通过取模index%3得到结果是1,同理index=2时得到结果2;index=3时得到结果0,这时如果index继续增加变为index=4,取模index%3得到结果为1,这样就有从1开始了一个新的循环。
同样定义两个指针,front表示头指针,rear表示尾指针,指针默认值0
难点:
代码实现:
package com.zlp.datastructure.controller; import java.util.Arrays; import java.util.Scanner; /** * 环形队列 */ public class CirQueue { public static void main(String[] args) { // 创建队列 System.out.println("请输入队列长度:"); Scanner scanner = new Scanner(System.in); int size = scanner.nextInt(); CirArrayQueue arrayQueue = new CirArrayQueue(size); boolean flag = true; while (flag) { // 操作指南 System.out.println("显示队列:1"); System.out.println("添加数据:2"); System.out.println("取出数据:3"); System.out.println("结束:4"); int choose = scanner.nextInt(); switch (choose) { case 1: arrayQueue.showQueue(); break; case 2: System.out.println("请输入要添加的数据:"); int data = scanner.nextInt(); arrayQueue.addQueue(data); System.out.println("数据添加成功~"); break; case 3: int queue = arrayQueue.getQueue(); System.out.println("数据取出:" + queue); break; case 4: System.out.println("程序结束~"); return; default: System.out.println("输入错误~"); break; } } } } class CirArrayQueue{ private int maxSize; private int front;// 头指针 private int rear;// 尾指针 private int[] arr; public CirArrayQueue(int size) { maxSize = size; arr = new int[maxSize]; front = 0; //front 为当前第一个元素 rear = 0; // 约定rear指向最后一个元素的后一个位置,也就是空出一个空间 } // 判断队列是否满 public boolean isFull() { return front == (rear + 1) % maxSize; } // 判断队列是否为空 public boolean isEmpty() { return front == rear; } // 添加数据到队列 public void addQueue(int data) { // 判断是否队列满 if (isFull()) { System.out.println("队列已满~"); return; } arr[rear] = data; // 当前位置插入元素 rear = (rear + 1) % maxSize;// 尾指针后移,尾指针指向最后一个元素的后一个位置 } // 取出数据 public int getQueue() { // 判断为空 if (isEmpty()) { System.out.println("队列为空~"); return 0; } int data = arr[front]; // 取出当前元素 front = (front + 1) % maxSize; // 头指针后移 return data; } // 显示所有队列数据 public void showQueue() { if (isEmpty()) { System.out.println("队列为空~"); return; } System.out.println(Arrays.toString(arr)); } // 显示队列头数据 public int headQueue() { if (isEmpty()) { System.out.println("队列为空~"); return 0; } return arr[front + 1]; } }
手敲一遍代码,更容易理解~~