本文共 5050 字，大约阅读时间需要 16 分钟。
一、队列
1.1 顺序一般队列
1.1.1 概述
这种队列有重大缺陷，不能够充分运用空间，只可作为学习使用。
1.1.2 代码及详细注释
package queue;
import java.util.Scanner;
public class ArrayQueue {
private int maxSize; // 队列的实际容量大小
private int front; // 第1个元素所在位置的前1个位置的索引
private int rear; // 最后1个元素所在位置的索引
private int[] queue; // 队列本身
/**
* 构造队列的方法
* @param logicSize 队列的逻辑大小，就是指用户觉得队列大小为3时，实际需要4个。
*/
public ArrayQueue(int logicSize){
maxSize = logicSize + 1;
queue = new int[maxSize];
}
/**
* 判断队列是否已满
* @return 满为true，不满为false
*/
public boolean isFull(){
return rear == maxSize-1;
}
/**
* 判断队列是否为空
* @return 如果为空，则返回true，否则返回false
*/
public boolean isEmpty(){
return front == rear;
}
/**
* 返回队列目前的元素个数
* @return 队列目前的元素个数
*/
public int size(){
return rear - front;
}
/**
* 入队
* @param n
* @return 入队成功返回true，否则返回false
*/
public boolean push(int n){
// 入队前先检查是否已满
if(isFull()){
System.out.println("队满！");
return false;
}
rear++;
queue[rear] = n;
return true;
}
/**
* 出队
* @return 出队的元素
*/
public int pop(){
// 出队前先检查是否为空，如果为空抛出异常
if (isEmpty()){
throw new RuntimeException("队空！");
}
front++;
return queue[front];
}
/**
* 拿到队首元素
* @return
*/
public int front(){
// 判断是否队空
if (isEmpty()){
throw new RuntimeException("队空！");
}
return queue[front+1];
}
/**
* 打印队列
*/
public void showQueue(){
if(isEmpty()){
System.out.println("[]");
return;
}
for (int i = front+1; i <= rear; i++) {
System.out.printf("queue[%d]=%d\n",i,queue[i]);
}
}
/**
* 测试菜单
* @param args
*/
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("请输入生成队列的大小：");
int n = sc.nextInt();
// 去除多余的换行符
sc.nextLine();
ArrayQueue arrayQueue = new ArrayQueue(n);
// 菜单
loop:
while (true) {
System.out.println("1、查看队列元素个数");
System.out.println("2、入队");
System.out.println("3、出队");
System.out.println("4、拿队首元素");
System.out.println("5、打印队列");
System.out.println("6、退出");
System.out.print("请选择：");
String choice = sc.nextLine();
switch (choice){
case "1":
int size = arrayQueue.size();
System.out.println("size="+size);
break;
case "2":
System.out.print("入队元素：");
int el = sc.nextInt();
// 去除多余的换行符
sc.nextLine();
arrayQueue.push(el);
break;
case "3":
try {
int pop = arrayQueue.pop();
System.out.println("出队元素："+pop);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case "4":
try {
int front = arrayQueue.front();
System.out.println("队首元素"+front);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case "5":
arrayQueue.showQueue();
break;
default:
break loop;
}
}
}
}
1.2 顺序循环队列
1.2.1 概述
循环队列是一个普遍的队列实现方法，空间利用率比顺序一般队列有较大的提升。
1.2.2 代码及详细注释
package queue;
import java.util.Scanner;
public class ArrayCircleQueue {
private int maxSize; // 队列的实际容量大小
private int front; // 第1个元素所在位置的前1个位置的索引
private int rear; // 最后1个元素所在位置的索引
private int[] queue; // 队列本身
/**
* 构造队列的方法
* @param logicSize 队列的逻辑大小，就是指用户觉得队列大小为3时，实际需要4个。
*/
public ArrayCircleQueue(int logicSize){
maxSize = logicSize + 1;
queue = new int[maxSize];
}
/**
* 判断队列是否已满
* @return 满为true，不满为false
*/
public boolean isFull(){
return (rear + 1) % maxSize == front;
}
/**
* 判断队列是否为空
* @return 如果为空，则返回true，否则返回false
*/
public boolean isEmpty(){
return front == rear;
}
/**
* 返回队列目前的元素个数
* @return 队列目前的元素个数
*/
public int size(){
return (rear - front + maxSize) % maxSize;
}
/**
* 入队
* @param n
* @return 入队成功返回true，否则返回false
*/
public boolean push(int n){
// 入队前先检查是否已满
if(isFull()){
System.out.println("队满！");
return false;
}
rear = (rear + 1) % maxSize;
queue[rear] = n;
return true;
}
/**
* 出队
* @return 出队的元素
*/
public int pop(){
// 出队前先检查是否为空，如果为空抛出异常
if (isEmpty()){
throw new RuntimeException("队空！");
}
front = (front + 1) % maxSize;
return queue[front];
}
/**
* 拿到队首元素
* @return
*/
public int front(){
// 判断是否队空
if (isEmpty()){
throw new RuntimeException("队空！");
}
return queue[(front + 1) % maxSize];
}
/**
* 打印队列
*/
public void showQueue(){
if(isEmpty()){
System.out.println("[]");
return;
}
for (int i = (front+1) % maxSize; i <= front+size(); i++) {
System.out.printf("queue[%d]=%d\n",i % maxSize,queue[i % maxSize]);
}
}
/**
* 测试菜单
* @param args
*/
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("请输入生成队列的大小：");
int n = sc.nextInt();
// 去除多余的换行符
sc.nextLine();
ArrayCircleQueue arrayQueue = new ArrayCircleQueue(n);
// 菜单
loop:
while (true) {
System.out.println("1、查看队列元素个数");
System.out.println("2、入队");
System.out.println("3、出队");
System.out.println("4、拿队首元素");
System.out.println("5、打印队列");
System.out.println("6、退出");
System.out.print("请选择：");
String choice = sc.nextLine();
switch (choice){
case "1":
int size = arrayQueue.size();
System.out.println("size="+size);
break;
case "2":
System.out.print("入队元素：");
int el = sc.nextInt();
// 去除多余的换行符
sc.nextLine();
arrayQueue.push(el);
break;
case "3":
try {
int pop = arrayQueue.pop();
System.out.println("出队元素："+pop);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case "4":
try {
int front = arrayQueue.front();
System.out.println("队首元素"+front);
} catch (Exception e) {
System.out.println(e.getMessage());
}
break;
case "5":
arrayQueue.showQueue();
break;
default:
break loop;
}
}
}
}
转载地址：https://blog.csdn.net/weixin_33865450/article/details/114468124 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！
发表评论
最新留言
关于作者
