java实现队列queue数据结构详解

java实现队列queue数据结构详解

目录概念队列中两个主要操作队列遵循以下条件：队列的数组实现总结

概念

队列是一种非原始（特殊）的线性表，是一种先进先出（FIFO）的数据结构。它只允许在UDloikPL表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。

FIFO：first input first output，即先添加的元素，先移除，最后添加的元素，最后移除。

工作方式类似于商场排队结账情形：

数组模拟队列图示：

队列中两个主要操作

插入值操作：insert ——》 enqueue（入队） ——》参数是要插入的数据data

删除值操作：remove ——》 dequeue （出队）——》 无参

队列遵循以下条件：

如果 FRONT = 0，那么队列就是空的。

如果 REAR = size of the queue，那么队列就是满了。

如果 FRONT = REAR，那么队列中至少有一个元素。

如果你想知道队列中元素的总数，那么使用这个公式计算（REAR - FRONT）+1。

队列的数组实现

我们可以通过数组、堆栈和链表来实现队列。其中数组是实现队列的最简单方法。

创建一个大小为 n 的数组。将 FRONT 和 REAR 的值初始化为 -1，该值表示该数组当前为空。

编写一个ArrayQueue类如下：

class ArrayQueue {

private int maxSize; // 数组的最大容量

private int front; // 队列头

private int rear; // 队列尾

private int[] arr; // 存放数据, 模拟队列

// 创建构造器，初始化

public ArrayQueue(int arrMaxSize) {

maxSize = arrMaxSize;

arr = new int[maxSize];

front = -1; // front 是指向队列头的前一个位置

rear = -1; // rear 是指向队列尾的数据(最后一个数据)

}

// 判断队列是否已满

public boolean isFull() {

return rear == maxSize - 1;

}

// 判断队列是否为空

public boolean isEmpty() {

return rear == front;

}

// 添加数据

public void addQueue(int n) {

if (isFull()) {

System.out.println("队列已满，不能再添加数据了！");

return;

}

rear++; // 让rear 后移

arr[rear] = n;

}

// 获取数据

public int getQueue() {

if (isEmpty()) {

// 通过抛出异常

throw new RuntimeException("队列为空，无数据可取！");

}

front++; // front后移

return arr[front];

}

// 显示队列的所有数据

public void showQueue() {

if (isEmpty()) {

System.out.println("队列空的，没有数据~~");

rehttp://turn;

}

for (int i = 0; i < arr.length; i++) {

System.out.printf("arr[%d]=%d\n", i, arr[i]);

}

}

// 显示队列的头部指向的下一个

public int headQueue() {

if (isEmpty()) {

throw new RuntimeException("队列为空，没有数据~~");

}

return arr[front + 1];

}

}

编写测试方法：

//创建一个队列

ArrayQueue queue = new ArrayQueue(3);

char key = ' ';

Scanner scanner = new Scanner(System.in);//

boolean loop = true;

//输出一个菜单选项

while(loop) {

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': //显示队列所有数据

queue.showQueue();

break;

case 'a': //添加数据

System.out.println("输出一个数");

int value = scanner.nextInt();

queue.addQueue(value);

break;

case 'g': //依次取出数据

try {

int res = queue.getQueue();

System.out.printf("取出的数据是%d\n", res);

} catch (Exception e) {

// TODO: handle exception

System.out.println(e.getMessage());

}

break;

case 'h': //查看队列头指向

try {

int res = queue.headQueue();

System.out.printf("队列头的数据是%d\n", res)UDloikPL;

} catch (Exception e) {

// TODO: handle exception

System.out.println(e.getMessage());

}

break;

case 'e': //退出程序

scanner.close();

loop = false;

break;

default:

break;

}

}

System.out.println("程序退出~~")http://;

}

总结

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