- 1、队列介绍
- 2、数组模拟队列思路
- 3、数组模拟环形队列思路
-
队列是一个有序列表，可以用数组或是链表来实现
-
遵循先入先出的原则 （first in first out，简称“FIFO”）。即：先存入队列的数据，要先取出。后存入的要后取出
-
队列是线性表的一种，在操作数据元素时，和栈一样，有自己的规则：使用队列存取数据元素时，数据元素只能从表的一端进入队列，另一端出队列，如下图。
-
示意图：（使用数组模拟队列示意图）
队列的实现同样有两种方式：顺序存储(数组)和链式存储(链表)。本文使用数组实现队列
2、数组模拟队列思路- 队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列的声明如下图，其中 maxSize 是该队列的最大容量
- 因为队列的输出、输入是分别从前后端来处理，因此需要两个指针 front 和 rear 分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear 则是随着数据的输入而改变，如图所示：
-
当我们将数据存入队列是称为 “addQueue” ，addQueue 的处理需要两个步骤：思路分析
- 将为指针后移： rear + 1
- 若尾指针 rear 小于队列的最大下标 maxSize - 1 ，则将数据存入 rear 所指的数组元素中，否则无法存入数据。
队列满 rear == maxSize - 1
代码实现
package com.yao.queue;
import java.util.Scanner;
public class ArrayQueueDemo {
public static void main(String[] args) {
//创建一个队列对象
ArrayQueue arrayQueue = new ArrayQueue(3);
//接收用户的输入
char key = ' ';
Scanner scanner = new Scanner(System.in);
boolean loop = true;
while (loop){
System.out.print("s(show): 显示队列t");
System.out.print("e(exit): 退出程序t");
System.out.print("a(add): 添加数据t");
System.out.print("g(get): 取出数据t");
System.out.print("h(head): 查看队列头数据n");
key = scanner.next().charAt(0);
switch (key){
case 's':
try {
arrayQueue.showQueue();
} catch (Exception e) {
e.printStackTrace();
}
break;
case 'e':
scanner.close();
loop = false;
break;
case 'a':
try {
System.out.println("输入一个数字：");
int value = scanner.nextInt();
arrayQueue.addElement(value);
} catch (Exception e) {
e.printStackTrace();
}
break;
case 'g':
try {
int res = arrayQueue.getElement();
System.out.printf("取出的数据是%dn", res);
} catch (Exception e) {
e.printStackTrace();
}
break;
case 'h':
try {
int res = arrayQueue.peekFront();
System.out.printf("队列头的数据是%dn", res);
} catch (Exception e) {
e.printStackTrace();
}
break;
default:
}
}
System.out.println("程序退出....");
}
}
class ArrayQueue {
private int maxSize;
private int front;
private int rear;
private int [] arr;
public ArrayQueue(int maxSize){
this.maxSize = maxSize;
arr = new int[maxSize];
//初始化 front 是指向队列头的前一个位置 rear 是指向队尾的位置
front = -1;
rear = -1;
}
public Boolean isFull(){
return rear == maxSize - 1;
}
public Boolean isEmpty(){
return front == rear;
}
public void addElement(int num){
if (isFull()){
throw new RuntimeException("队列已经满了....");
}
rear ++;
arr[rear] = num;
}
public int getElement(){
//判断队列空
if (isEmpty()){
//通过抛出异常处理
throw new RuntimeException("队列为空....");
}
front ++;
return arr[front];
}
public void showQueue(){
if (isEmpty()){
return;
}
for (int i : arr) {
System.out.println(i);
}
}
public int peekFront(){
if (isEmpty()){
throw new RuntimeException("队列为空....");
}
return arr[front+1];
}
}
裡 问题分析并优化
- 目前数组使用一次就不能用了，没有达到复用的效果
- 将这个数组使用算法，改成一个环形队列 取模：%
对前面的数组模拟队列的优化，充分利用数组。因此将数组看做是一个环形的。（通过取模的方式来实现即可）
裡 分析说明：
- 尾指针的下一个为头指针时表示队列满，即将队列容量空出一个作为约定，这个在做判断队列满的时候需要注意 （rear + 1）% maxSize == front【满】
- rear == front【空】
- 分析示意图：
思路如下：
- front 头指针的含义做一个调整：front 就指向队列的第一个元素，也就是说 arr[front] 就是队列的第一个元素 ，front 初始值就 = 0
- rear 尾指针的含义做一个调整：rear 指向队列的最后一个元素的后一个位置。因为希望空出一个空间作为约定。 rear 的初始值 = 0
- 当队列为满时，条件是 (rear + 1) % maxSize == front 【满】
- 当队列为空时，条件是 rear == front 【空】
- 当我们这样分析，队列中有效的数据个数 (rear + maxSize - front) % maxSize
- 我们就可以在原来的队列上修改得到，一个环形队列
代码实现
package com.yao.queue;
public class CircleArrayQueue {
private int maxSize; //表示队列的最大容量
private int front; //队列头
private int rear; //队列尾
private int [] arr;
public CircleArrayQueue(int maxSize){
this.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 addElement(int num){
if (isFull()){
throw new RuntimeException("队列已满....");
}
arr[rear] = num;
//将 real 后移，进行取模
rear = (rear+1) % maxSize;
}
public int getElement(){
//判断队列
if (isEmpty()){
throw new RuntimeException("队列为空.....");
}
//这里需要分析出 front 是指向队列的第一个元素
//1.先把 front 对应的值保存到一个临时变量中
//2.将 front 后移，考虑取模
//3.将临时变量返回
int value = arr[front];
front = (front + 1) % maxSize;
return value;
}
public void showElement(){
if (isEmpty()){
throw new RuntimeException("队列为空....");
}
//思路：从 front 开始遍历遍历多少个元素
for (int i = front; i < front + size(); i++) {
System.out.printf("元素arr[%d]=%dn",i % maxSize,arr[i % maxSize]);
}
}
public int peekFront(){
if (isEmpty()){
throw new RuntimeException("队列为空....");
}
return arr[front];
}
public int size(){
return (rear + maxSize - front) % maxSize;
}
}
源码
完结
