Java语言通过三种方法实现队列的示例代码

Java语言通过三种方法实现队列的示例代码

目录队列图解数组模拟队列队列优化—循环队列代码使用java内部队列代码

队列

队列是一种特殊的线性表，只允许在表的前端进行删除操作，在表的后端进行插入操作。队列是一个有序列表，可以用数组或是链表来实现。遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出。就相当于我们日常生活中的排队，先来先服务，后来的只能在后面进行排队等待。

图解

数组模拟队列

通过对定义的了解，发现队列很像我们的数组，那我们是不是可以通过数组来模拟队列，下面我们来实践一下。

首先先分析一下：

队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 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(skkCCls"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 的初始值 = 0rear 变量的含义做一个调整：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 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()。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。