这篇文章主要介绍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 exception System.out.println(e.getMessage()); } break; case 'h': //查看队列头指向 try { int res = queue.headQueue(); System.out.printf("队列头的数据是%d\n", res); } catch (Exception e) { // TODO: handle exception System.out.println(e.getMessage()); } break; case 'e': //退出程序 scanner.close(); loop = false; break; default: break; } } System.out.println("程序退出~~"); }
以上是“java如何实现队列queue数据结构”这篇文章的所有内容,感谢各位的阅读!希望分享的内容对大家有帮助,更多相关知识,欢迎关注亿速云行业资讯频道!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。