目 录

队列详解队列定义创建队列**队列的基本操作**添加元素取出元素判断队列是否为空判断队列是否为满 问题分析优化 环形队列特点应用环形队列的实现环形队列基本操作创建环形队列判断是否为空队列判断是否为满队列添加元素取出数据查看当前元素且不取出 完整代码每日一言：

队列详解

队列定义

在这里插入代码片队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

创建队列

创建初始数组 int arr[maxSize] 定义头指针 front = -1，尾指针 rear = -1.

队列的基本操作

添加元素

判断队列是否为满队列，若为满队列则输出提示信息，否则执行2；rear ++ ;arr[rear] = temp;队列添加元素成功；

取出元素

判断队列是否为空，若为空输出错误提示信息，否则执行2front ++;队列元素成功取出；

判断队列是否为空

若front == rear 则队列为空，否则队列不为空

判断队列是否为满

若 rear == maxSize 则队列为满，否则队列不是满队列 查看当前元素且不取出判断队列是否为空，若为空输出错误提示信息，否则执行2Return arr[front+1];

问题分析优化

此方法实现的队列只能使用一次，且空间利用率不高。可以考虑使用环形队列

环形队列

特点

它是一个首尾相连的FIFO的数据结构，采用数组的线性空间,数据组织简单。能很快知道队列是否满为空。能以很快速度的来存取数据。 因为有简单高效的原因，甚至在硬件都实现了环形队列.

应用

环形队列广泛用于网络数据收发，和不同程序间数据交换（比如内核与应用程序大量交换数据,从硬件接收大量数据）均使用了环形队列.

环形队列的实现

实现环形队列最重要的一个问题就是队空和队满的判断问题，在上面的队列实现方法中判定队满条件为 front == rear。判定队空条件为 rear == maxsize

考虑如何实现数组的循回，假设现在rear== maxSize 那么如何可以使rear指向arr[0]。我们发现（rear++）% maxSize 可以实现数组的循环。

考虑如可判断队满和队空。若不浪费数组空间 则可能出现一下俩种情况：

所以我们可以消耗一个数组空间

则队满状态的判断条件为（rear++）% maxSize == front。队空状态的判断条件为 front == rear。

环形队列基本操作

创建环形队列

创建初始数组 int arr[] 头指针 front = 0，尾指针 rear = 0（注意必须设置为0，否则判断队空，队满会失败），设置数组容量maxSize。

class CircleArray { private int front ; private int rear ; private int [] arr; private int maxSize; public CircleArray(int maxSize) { this.arr = new int [maxSize] ; this.maxSize = maxSize; } }

判断是否为空队列

判定front==rear是否为真，若为真则队空，否则该队列不为空。 public boolean isEmpty(){ return this.front == this.rear; }

判断是否为满队列

判断（rear+1）% maxSize == front 是否为真，若为真则队满，否则该队列不是满队列。 public boolean isFull(){ return (this.rear+1) % this.maxSize == this.front; }

添加元素

判断是否队满，若队满则输出错误提示信息。否则执行2.Rear = (rear+1)%maxSizeArr[rear] = temp;添加元素成功； public void addQueue(int temp){ if(this.isFull()){ System.out.println("队列满，不能添加数据"); return; } this.rear = (this.rear+1) % this.maxSize; this.arr[this.rear] = temp; }

取出数据

判断是否队空，若队空则输出错误提示信息。否则执行2.Front = (front+1)%maxSize;取出数据成功； public int getQueue(){ if(this.isEmpty()){ throw new RuntimeException("队列空，不能取数据"); } this.front = (this.front+1) % this.maxSize; int value = this.arr[this.front]; return value; }

查看当前元素且不取出

判断是否队空，若队空则输出错误提示信息。否则执行2.Return arr[front+1] public int headQueue(){ if(this.isEmpty()){ throw new RuntimeException("队列空，无数据"); } return this.arr[(this.front+1) % this.maxSize]; }

完整代码

import java.util.Scanner; class CircleArrayQueueDemo { public static void main(String[] args) { CircleArray queue = new CircleArray(4); char key = ' '; Scanner scanner = new Scanner(System.in); boolean lop = true; while (lop) { System.out.println("e: 退出程序"); System.out.println("a: 添加数据"); System.out.println("g: 取出数据"); System.out.println("h: 查看队列头数据"); key = scanner.next().charAt(0); switch (key) { case 'a': System.out.println("输入一个数字"); int value = scanner.nextInt(); queue.addQueue(value); break; case 'g': try{ int res = queue.getQueue(); System.out.printf("取出的数据是%d\n",res); } catch(Exception e){ System.out.println(e.getMessage()); } break; case 'h': try{ int res = queue.headQueue(); System.out.printf("取出的数据是%d\n",res); } catch(Exception e){ System.out.println(e.getMessage()); } break; case 'e': scanner.close(); lop=false; break; } } System.out.println("程序退出"); } } class CircleArray { private int front ; private int rear ; private int [] arr; private int maxSize; public CircleArray(int maxSize) { this.arr = new int [maxSize] ; this.maxSize = maxSize; } public boolean isEmpty(){ return this.front == this.rear; } public boolean isFull(){ return (this.rear+1) % this.maxSize == this.front; } public void addQueue(int temp){ if(this.isFull()){ System.out.println("队列满，不能添加数据"); return; } this.rear = (this.rear+1) % this.maxSize; this.arr[this.rear] = temp; } public int getQueue(){ if(this.isEmpty()){ throw new RuntimeException("队列空，不能取数据"); } this.front = (this.front+1) % this.maxSize; int value = this.arr[this.front]; return value; } public int headQueue(){ if(this.isEmpty()){ throw new RuntimeException("队列空，无数据"); } return this.arr[(this.front+1) % this.maxSize]; } }

每日一言：

玫瑰花：＂我并非如此的弱不禁风...夜晚的凉风对我倒有好处。我是一朵花啊。＂ ——— 小王子