Java实现队列
java厂长 人气:0队列
- 队列是一种特殊的线性表，只允许在表的前端进行删除操作，在表的后端进行插入操作。
- 队列是一个有序列表，可以用数组或是链表来实现。
- 遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出。
- 就相当于我们日常生活中的排队，先来先服务，后来的只能在后面进行排队等待。
图解
数组模拟队列
通过对定义的了解，发现队列很像我们的数组，那我们是不是可以通过数组来模拟队列，下面我们来实践一下。
首先先分析一下：
- 队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队 列的最大容量。
- 因为队列的输出、输入是分别从前后端来处理，所以我们需要两个变量 front 及 rear 分别记录队列前后端的下标， front 会随着数据输出而改变，而 rear 则是随着数据输入而改变。
- 当我们将数据存入队列时称为addQueue，addQueue 的处理需要有两个步骤：思路分析
- 当 front == rear 【队列空无数据】，将尾指针往后移：rear + 1
- 若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear 所指的数组元素中，否则无法存入数据。 rear == maxSize - 1【表示队列满】无法存入数据。
代码
package com.cz.Queuearray;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.concurrent.BlockingQueue;
/**
* @ProjectName: Data_structure
* @Package: com.cz.Queuearray
* @ClassName: QueueArray
* @Author: 张晟睿
* @Date: 2022/2/21 18:42
* @Version: 1.0
*/
public class QueueArray {
public static void main(String[] args) {
// TODO Auto-generated method stub
QueueArray1 qArray1 = new QueueArray1(3);
Scanner scanner = new Scanner(System.in);
char key = ' ';
boolean f = true;
while(f){
System.out.println("s(show):显示队列");
System.out.println("e(exit):退出程序");
System.out.println("a(add):添加数据到队列");
System.out.println("g(get):从队列里面取出数据");
System.out.println("h(head):查看队列头部的数据");
key = scanner.next().charAt(0);
switch (key) {
case 's':
qArray1.getQueue();
break;
case 'a':
System.out.println("请输出一个数字：");
int value = scanner.nextInt();
qArray1.addQueue(value);
case 'g':
try {
int res = qArray1.exitQueue();
System.out.printf("输出的数据是%d\n",res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
case 'h':
int res = qArray1.headQueue();
System.out.printf("对头的数据是%d\n",res);
case 'e':
scanner.close();
f=false;
default:
}
}
System.out.println("退出程序！！！！！！！");
}
}
//数组模拟队列
class QueueArray1{
private int maxSize;//最大容量、
private int arr[]; //声明数组
private int front;//队头元素
private int rear;//队尾
//构造器
public QueueArray1(int arrMaxSize) {
maxSize = arrMaxSize;
arr = new int [maxSize];
front = -1;//指向队列头部，分析出front是指向队列头的前一 个位置。
rear = -1;//指向队列尾，指向队列尾的数据(即就是队列最后一个数据)
//判断队空
public boolean isEmety(){
return rear==front;
//判断队满
public boolean isFull(){
return rear == maxSize - 1;
//入队
public void addQueue(int n){
if (isFull()) {
System.out.println("队列已满，无法插入");
return;//不加return
//Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 3
//at day1.QueueArray1.insert(QueueArray.java:89)
//at day1.QueueArray.main(QueueArray.java:32)
arr[++rear] = n;
//出队
public int exitQueue(){
if (isEmety()) {
throw new RuntimeException("队列为空，无元素");
return arr[++front];
//输出全部元素
public void getQueue(){
System.out.println("队列为空，无法输出数据~~~~~~~~~~");
for (int i = 0; i < arr.length; i++) {
System.out.printf("arr[%d]=%d\n",i,arr[i]);
//显示队列的头数据，不是取数据
public int headQueue(){
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 - front + maxSize) % maxSize - 我们就可以在原来的队列上修改得到，一个环形队列
代码
package com.cz.Queuearray;
import java.util.Scanner;
/**
* @ProjectName: Data_structure
* @Package: com.cz.Queuearray
* @ClassName: CircleQueueArray
* @Author: 张晟睿
* @Date: 2022/2/22 14:58
* @Version: 1.0
*/
public class CircleQueueArray {
public static void main(String[] args) {
CircleQueueArray1 circlequeue = new CircleQueueArray1(3);
Scanner scanner = new Scanner(System.in);
char key = ' ';
boolean f = true;
while(f){
System.out.println("s(show):显示队列");
System.out.println("e(exit):退出程序");
System.out.println("a(add):添加数据到队列");
System.out.println("g(get):从队列里面取出数据");
System.out.println("h(head):查看队列头部的数据");
key = scanner.next().charAt(0);
switch (key) {
case 's':
circlequeue.showQueue();
break;
case 'a':
System.out.println("请输出一个数字：");
int value = scanner.nextInt();
circlequeue.addQueue(value);
case 'g':
try {
int res = circlequeue.getQueue();
System.out.printf("输出的数据是%d\n",res);
} catch (Exception e) {
System.out.println(e.getMessage());
}
case 'h':
int res = circlequeue.headQueue();
System.out.printf("对头的数据是%d\n",res);
case 'e':
scanner.close();
f=false;
default:
}
}
System.out.println("退出程序！！！！！！！");
}
}
class CircleQueueArray1{
private int maxSize; // 表示数组的最大容量
//front 变量的含义做一个调整： front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素
//front 的初始值 = 0
private int front;
//rear 变量的含义做一个调整：rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定. //rear 的初始值 = 0
private int rear; // 队列尾
private int[] arr; // 该数据用于存放数据, 模拟队列
public CircleQueueArray1(int MaxSize){
maxSize = MaxSize;
arr = new int [maxSize];
//判断队满
public boolean isFull(){
return (rear + 1) % maxSize == front;
//判断队列空
public boolean isEmpty(){
return rear == front;
// 添加数据到队列
public void addQueue(int n) {
if (isFull()){
System.out.println("队列满，不能加入数据~");
return;
//将数据直接插入到数组，用队尾rear来进行位置的确定
arr[rear] = n;
//将 rear 后移, 这里必须考虑取
rear = (rear + 1) % maxSize;
//获取队列的数据, 出队列
public int getQueue() {
if (isEmpty()) throw new RuntimeException("队列空，不能取数据");
// 这里需要分析出 front 是指向队列的第一个元素,因为这里是循环的，所以我们考虑用一个临时变量来获取当前的队头
// 1. 先把 front 对应的值保留到一个临时变量
// 2. 将 front 后移, 考虑取模
// 3. 将临时保存的变量返回
int value = front;
front = (front + 1) % maxSize;
return arr[value];
// 求出当前队列有效数据的个数
public int size() {
return (rear - front + maxSize) % maxSize;
// 显示队列的所有数据
public void showQueue() {
for (int i = front; i < front + size(); i++) {
System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
// 显示队列的头数据， 注意不是取出数据
public int headQueue() {
// 判断队列是空
if (isEmpty()) {
throw new RuntimeException("队列空的，没有数据~~");
return arr[front];使用java内部队列
LinkedList 类实现了 Queue 接口，因此我们可以把 LinkedList 当成 Queue 来用。
代码
package com.cz.Queuearray;
import java.util.LinkedList;
import java.util.Queue;
/**
* @ProjectName: Data_structure
* @Package: com.cz.Queuearray
* @ClassName: LinkedListDemo
* @Author: 张晟睿
* @Date: 2022/2/22 15:43
* @Version: 1.0
*/
public class LinkedListDemo {
public static void main(String[] args) {
//add()和remove()方法在失败的时候会抛出异常(不推荐)
Queue<Integer> queue = new LinkedList<>();
//offer() 将指定的元素添加为此列表的尾部（最后一个元素）。
queue.offer(1);
queue.offer(2);
queue.offer(3);
queue.offer(4);
queue.offer(5);
for (Integer nums:queue) {
System.out.println(nums);
}
//poll() 检索并删除此列表的头（第一个元素）。
//当集合为空时，返回 null
queue.poll();
//queue.poll();
//remove() 检索并删除此列表的头（第一个元素）。
//当集合为空时，出现异常 java.util.NoSuchElementException;
queue.remove();
//element() 检索但不删除此列表的头（第一个元素）。
//当队列为空时，java.util.NoSuchElementException
//System.out.println("队列的头部：" + queue.element());
//peek() 检索但不删除此列表的头（第一个元素）。
//当队列为空时，返回null
System.out.println("队列的头部：" + queue.peek());
}
}poll，remove 区别：
remove() 和 poll() 方法都是从队列中删除第一个元素。remove() 的行为与 Collection 接口的版本相似， 但是新的 poll() 方法在用空集合调用时不是抛出异常，只是返回 null。因此新的方法更适合容易出现异常条件的情况。
peek，element区别：
element() 和 peek() 用于在队列的头部查询元素。与 remove() 方法类似，在队列为空时， element() 抛出一个异常，而 peek() 返回 null。
所以推荐大家使用peek() 和 poll()。
加载全部内容