当前位置： 首页>编程语言>正文

java有限长度队列 java有序队列

编程语言2024-04-25 15:09:30

目录

队列定义

队列案例

数组模拟队列

普通队列

环形队列

队列定义

队列是一个有序列表，可以用数组或是链表来实现。
遵循先入先出的原则即：先存入队列的数据，要先取出。后存入的要后取出。

队列案例

例如在学校食堂排队买早餐，排在前面的（队首）就先出对，排在后面的（队尾）就后出队列，这是一个最简单的实例。

数组模拟队列

普通队列

队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队列的最大容量。

因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front及 rear分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear则是随着数据输入而改变，如图所示:

java有限长度队列 java有序队列,java有限长度队列 java有序队列_退出程序,第1张

在添加队列的时候，我们需要做到以下几步：

  1. 将尾指针往后移：rear+1 , 当front == rear 【队列为空】
  2. 若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear所指的数组元素中，否则无法存入数据。 rear  == maxSize - 1[队列满]

在出队列的时候，需要做到以下几步：

  1. 将尾指针往后移：rear-1 , 当front == rear 【队列为空】
  2. 将结果返回

下面，我们以学生排队为例子，代码实现一下：

package com.chtw.queue;

import java.util.Scanner;

public class ArrayQueueTest {

	public static void main(String[] args) {
		//测试一把
		
		//1. 创建几个学生对象，等待使用
		Student stu1 = new Student(1, "Ailce");
		Student stu2 = new Student(2, "Bob");
		Student stu3 = new Student(3, "Covler");
		Student stu4 = new Student(4, "Piter");
		
		//2. 创建队列
		StuArrayQueue queue = new StuArrayQueue(3);
		
		//入队
		/*queue.addQueue(stu1);
		queue.addQueue(stu2);
		queue.addQueue(stu3);
		
		Student stu5 = queue.remove();
		System.out.println(stu5);
		
		
		
		queue.show();*/
		char key = ' ';
		Scanner scanner = new Scanner(System.in);
		boolean loop = true;
		//写一个菜单
		while(true) {
			System.out.println("s(show): 表示显示队列");
			System.out.println("a(add): 表示添加队列数据");
			System.out.println("r(remove): 表示取出队列数据");
			System.out.println("p(peek): 队首数据");
			System.out.println("e(exit): 表示退出程序");
			
			key = scanner.next().charAt(0);

			switch (key) {
			case 's':
				queue.show();
				break;
			case 'a':
				System.out.println("请输入一个数");
				System.out.println("stu1: Alice");
				System.out.println("stu2: Bob");
				System.out.println("stu3: Covler");
				System.out.println("stu4: Piter");
				String value = scanner.next();
				if(value.equals("stu1")) {
					queue.addQueue(stu1);
				}
				if(value.equals("stu2")) {
					queue.addQueue(stu2);
				}
				if(value.equals("stu3")) {
					queue.addQueue(stu3);
				}
				if(value.equals("stu4")) {
					queue.addQueue(stu4);
				}
				break;
			case 'r':
				try {
					Student res = queue.remove();
					System.out.println("取出数据是"+res);
				} catch (Exception e) {
					// TODO: handle exception
					System.out.println(e.getMessage());
				}
				break;
			case 'e':
				scanner.close(); // 关闭下scanner,否则会有警告信息
				loop = false;
				break;
			default:
				break;
			}
		}
		
	}

}
/**
 * 学生类
 * @author CHTW
 *
 */
class Student{
	public int no;
	public String name;
	
	
	public Student(int no, String name) {
		super();
		this.no = no;
		this.name = name;
	}


	@Override
	public String toString() {
		return "Student [no=" + no + ", name=" + name + "]";
	}
}

/**
 * 队列
 * @author CHTW
 *
 */
class StuArrayQueue{
	private int maxSize;
	private Student[] stuQueue; // 该数组存放数据，模拟队列
	private int front;
	private int rear;
	
	/**
	 * 构造方法，初始化
	 * @param maxSize
	 */
	public StuArrayQueue(int maxSize) {
		super();
		this.maxSize = maxSize;
		this.stuQueue = new Student[maxSize];
		front = -1; // 指向队列头部, 分析出front 是指向队列数据的前一个位置
		rear = -1; // 指向队列的尾部，分析出rear 是指向队列的最后数据
	}
	/**
	 * 判断队列是否满
	 * @return
	 */
	public boolean isFull() {
		return rear == maxSize - 1;
	}

	/**
	 * 判断队列是否空
	 * @return
	 */
	public boolean isEmpty() {
		return front == rear;
	}
	
	/**
	 * 入队
	 * @param stu
	 */
	public void addQueue(Student stu) {
		//判断是否队满
		if(isFull()) {
			System.out.println("队满，请稍等~");
			return;
		}else {
			//如果不是队满，则加入进行排队
			stuQueue[++rear] = stu;
		}
	}
	
	/**
	 * 出队
	 * @return
	 */
	public Student remove() {
		if(isEmpty()) {
			throw new RuntimeException("对空~");
		}else {
			front += 1;
			Student temp = stuQueue[front];
			stuQueue[front] = null;
			return temp;
		}
	}
	
	/**
	 * 获取队首
	 * @return
	 */
	public Student peek() {
		if(isEmpty()) {
			throw new RuntimeException("对空~");
		}else {
			return stuQueue[front + 1];
		}
	}
	/**
	 * 遍历
	 */
	public void show() {
		if (isEmpty()) {
			System.out.println("队列空的，没有数据..");
			return;
		}
		for (int i = 0; i < stuQueue.length; i++) {
			if(stuQueue[i]!=null) {
				System.out.println(stuQueue[i]);
			}
		}
	}
	
}

运行结果如下：

s(show): 表示显示队列
a(add): 表示添加队列数据
r(remove): 表示取出队列数据
p(peek): 队首数据
e(exit): 表示退出程序
s
队列空的，没有数据..
s(show): 表示显示队列
a(add): 表示添加队列数据
r(remove): 表示取出队列数据
p(peek): 队首数据
e(exit): 表示退出程序
a
请输入一个数
stu1: Alice
stu2: Bob
stu3: Covler
stu4: Piter
stu1
s(show): 表示显示队列
a(add): 表示添加队列数据
r(remove): 表示取出队列数据
p(peek): 队首数据
e(exit): 表示退出程序
s
Student [no=1, name=Ailce]
s(show): 表示显示队列
a(add): 表示添加队列数据
r(remove): 表示取出队列数据
p(peek): 队首数据
e(exit): 表示退出程序
a
请输入一个数
stu1: Alice
stu2: Bob
stu3: Covler
stu4: Piter
stu4
s(show): 表示显示队列
a(add): 表示添加队列数据
r(remove): 表示取出队列数据
p(peek): 队首数据
e(exit): 表示退出程序
s
Student [no=1, name=Ailce]
Student [no=4, name=Piter]
s(show): 表示显示队列
a(add): 表示添加队列数据
r(remove): 表示取出队列数据
p(peek): 队首数据
e(exit): 表示退出程序
a
请输入一个数
stu1: Alice
stu2: Bob
stu3: Covler
stu4: Piter
stu2
s(show): 表示显示队列
a(add): 表示添加队列数据
r(remove): 表示取出队列数据
p(peek): 队首数据
e(exit): 表示退出程序
s
Student [no=1, name=Ailce]
Student [no=4, name=Piter]
Student [no=2, name=Bob]
s(show): 表示显示队列
a(add): 表示添加队列数据
r(remove): 表示取出队列数据
p(peek): 队首数据
e(exit): 表示退出程序
a
请输入一个数
stu1: Alice
stu2: Bob
stu3: Covler
stu4: Piter
stu3
队满，请稍等~
s(show): 表示显示队列
a(add): 表示添加队列数据
r(remove): 表示取出队列数据
p(peek): 队首数据
e(exit): 表示退出程序
r
取出数据是Student [no=1, name=Ailce]
s(show): 表示显示队列
a(add): 表示添加队列数据
r(remove): 表示取出队列数据
p(peek): 队首数据
e(exit): 表示退出程序
a
请输入一个数
stu1: Alice
stu2: Bob
stu3: Covler
stu4: Piter
stu2
队满，请稍等~
s(show): 表示显示队列
a(add): 表示添加队列数据
r(remove): 表示取出队列数据
p(peek): 队首数据
e(exit): 表示退出程序
s
Student [no=4, name=Piter]
Student [no=2, name=Bob]
s(show): 表示显示队列
a(add): 表示添加队列数据
r(remove): 表示取出队列数据
p(peek): 队首数据
e(exit): 表示退出程序

从测试结果中，我们发现了一个问题，为什么我们在队满后出队依然还是不能再次入队呢？给我们的提示是队满，请稍等~。

java有限长度队列 java有序队列,java有限长度队列 java有序队列_System_02,第2张

出现这个问题的原因很简单，就是我们的remove函数中，没有对rear进行处理，第一次队满的时候，rear就一直处于rear==maxSize的状态。但是我们就不能直接将rear-1，如果直接减一就删除了队尾的信息。因此为了满足可以循环使用队列，引出了环形队列。

环形队列

分析说明：

  1. 尾索引的下一个为头索引时表示队列满，即将队列容量空出一个作为约定,这个在做判断队列满的时候需要注意 (rear + 1) % maxSize == front 满]
  2. rear == front [空]

具体代码如下

package com.chtw.queue;

import java.util.Scanner;

public class CircleArrayQueueTest {

	public static void main(String[] args) {
		// 测试一把

		// 1. 创建几个学生对象，等待使用
		Student stu1 = new Student(1, "Ailce");
		Student stu2 = new Student(2, "Bob");
		Student stu3 = new Student(3, "Covler");
		Student stu4 = new Student(4, "Piter");

		// 2. 创建队列,需要预留一个空间
		CircleStuArrayQueue queue = new CircleStuArrayQueue(4);

		char key = ' ';
		Scanner scanner = new Scanner(System.in);
		boolean loop = true;
		// 写一个菜单
		while (true) {
			System.out.println("s(show): 表示显示队列");
			System.out.println("a(add): 表示添加队列数据");
			System.out.println("r(remove): 表示取出队列数据");
			System.out.println("p(peek): 队首数据");
			System.out.println("e(exit): 表示退出程序");

			key = scanner.next().charAt(0);

			switch (key) {
			case 's':
				queue.show();
				break;
			case 'a':
				System.out.println("请输入选择");
				System.out.println("stu1: Alice");
				System.out.println("stu2: Bob");
				System.out.println("stu3: Covler");
				System.out.println("stu4: Piter");
				String value = scanner.next();
				if (value.equals("stu1")) {
					queue.addQueue(stu1);
				}
				if (value.equals("stu2")) {
					queue.addQueue(stu2);
				}
				if (value.equals("stu3")) {
					queue.addQueue(stu3);
				}
				if (value.equals("stu4")) {
					queue.addQueue(stu4);
				}
				break;
			case 'r':
				try {
					Student res = queue.remove();
					System.out.println("取出数据是" + res);
				} catch (Exception e) {
					// TODO: handle exception
					System.out.println(e.getMessage());
				}
				break;
			case 'e':
				scanner.close(); // 关闭下scanner,否则会有警告信息
				loop = false;
				break;
			default:
				break;
			}
		}

	}

}

class CircleStuArrayQueue {
	private int maxSize;
	private Student[] stuQueue; // 该数组存放数据，模拟队列
	private int front;
	private int rear;

	/**
	 * 构造方法，初始化
	 * 
	 * @param maxSize
	 */
	public CircleStuArrayQueue(int maxSize) {
		super();
		this.maxSize = maxSize;
		this.stuQueue = new Student[maxSize];
	}

	/**
	 * 判断队列是否满
	 * 
	 * @return
	 */
	public boolean isFull() {
		return (rear + 1) % maxSize == front;
	}

	/**
	 * 判断队列是否空
	 * 
	 * @return
	 */
	public boolean isEmpty() {
		return rear == front;
	}

	/**
	 * 添加
	 * 
	 * @param stu
	 */
	public void addQueue(Student stu) {
		// 判断是否满
		if (isFull()) {
			System.out.println("队列满，无法加入..");
			return;
		}
		// 将数据加入
		stuQueue[rear] = stu;
		// 然后将rear 后移, 这里必须考虑取模
		rear = (rear + 1) % maxSize;
	}

	/**
	 * 出队
	 * 
	 * @return
	 */
	public Student remove() {
		if (isEmpty()) {
			throw new RuntimeException("对空~");
		} else {
			Student temp = stuQueue[front];
			stuQueue[front] = null;
			front = (front + 1) % maxSize;
			return temp;
		}
	}

	/**
	 * 获取队首
	 * 
	 * @return
	 */
	public Student peek() {
		if (isEmpty()) {
			throw new RuntimeException("对空~");
		} else {
			return stuQueue[front%maxSize];
		}
	}

	/**
	 * 获取队列长度
	 * 
	 * @return
	 */
	public int size() {
		// rear = 1
		// front = 0
		// maxSize = 3
		return (rear + maxSize - front) % maxSize;
	}

	/**
	 * 遍历
	 */
	public void show() {
		if (isEmpty()) {
			System.out.println("队列空的，没有数据..");
			return;
		}
		for (int j = front; j < front + size(); j++) {
			System.out.println(stuQueue[j % maxSize]);
		}
	}

}

测试结果：

s(show): 表示显示队列
a(add): 表示添加队列数据
r(remove): 表示取出队列数据
p(peek): 队首数据
e(exit): 表示退出程序
a
请输入选择
stu1: Alice
stu2: Bob
stu3: Covler
stu4: Piter
stu1
s(show): 表示显示队列
a(add): 表示添加队列数据
r(remove): 表示取出队列数据
p(peek): 队首数据
e(exit): 表示退出程序
a
请输入选择
stu1: Alice
stu2: Bob
stu3: Covler
stu4: Piter
stu2
s(show): 表示显示队列
a(add): 表示添加队列数据
r(remove): 表示取出队列数据
p(peek): 队首数据
e(exit): 表示退出程序
a
请输入选择
stu1: Alice
stu2: Bob
stu3: Covler
stu4: Piter
stu3
s(show): 表示显示队列
a(add): 表示添加队列数据
r(remove): 表示取出队列数据
p(peek): 队首数据
e(exit): 表示退出程序
s
Student [no=1, name=Ailce]
Student [no=2, name=Bob]
Student [no=3, name=Covler]
s(show): 表示显示队列
a(add): 表示添加队列数据
r(remove): 表示取出队列数据
p(peek): 队首数据
e(exit): 表示退出程序
a
请输入选择
stu1: Alice
stu2: Bob
stu3: Covler
stu4: Piter
stu4
队列满，无法加入..
s(show): 表示显示队列
a(add): 表示添加队列数据
r(remove): 表示取出队列数据
p(peek): 队首数据
e(exit): 表示退出程序
r
取出数据是Student [no=1, name=Ailce]
s(show): 表示显示队列
a(add): 表示添加队列数据
r(remove): 表示取出队列数据
p(peek): 队首数据
e(exit): 表示退出程序
s
Student [no=2, name=Bob]
Student [no=3, name=Covler]
s(show): 表示显示队列
a(add): 表示添加队列数据
r(remove): 表示取出队列数据
p(peek): 队首数据
e(exit): 表示退出程序
a
请输入选择
stu1: Alice
stu2: Bob
stu3: Covler
stu4: Piter
stu4
s(show): 表示显示队列
a(add): 表示添加队列数据
r(remove): 表示取出队列数据
p(peek): 队首数据
e(exit): 表示退出程序
s
Student [no=2, name=Bob]
Student [no=3, name=Covler]
Student [no=4, name=Piter]
s(show): 表示显示队列
a(add): 表示添加队列数据
r(remove): 表示取出队列数据
p(peek): 队首数据
e(exit): 表示退出程序

从测试结果中可以看出，现在就可以循环使用队列的空间了。

 


https://www.xamrdz.com/lan/5tx1934101.html

相关文章：