java如何实现队列queue数据结构

这篇文章主要介绍java如何实现队列queue数据结构，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！

概念

队列是一种非原始（特殊）的线性表，是一种先进先出（FIFO）的数据结构。它只允许在表的前端（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("队列空的，没有数据~~");return;}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 exceptionSystem.out.println(e.getMessage());}break;case 'h': //查看队列头指向try {int res = queue.headQueue();System.out.printf("队列头的数据是%d\n", res);} catch (Exception e) {// TODO: handle exceptionSystem.out.println(e.getMessage());}break;case 'e': //退出程序scanner.close();loop = false;break;default:break;}}System.out.println("程序退出~~");}

以上是“java如何实现队列queue数据结构”这篇文章的所有内容，感谢各位的阅读！希望分享的内容对大家有帮助，更多相关知识，欢迎关注编程网精选频道！