您好,登录后才能下订单哦!
本篇文章为大家展示了怎么在java中利用数组实现一个环形队列,内容简明扼要并且容易理解,绝对能使你眼前一亮,通过这篇文章的详细介绍希望你能有所收获。
Java是一门面向对象编程语言,可以编写桌面应用程序、Web应用程序、分布式系统和嵌入式系统应用程序。
及具体代码
队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。
总结起来两点:
1.一种线性表
2.添加操作只能在表尾,删除操作在表头(先进先出)
初始化一个大小固定的数组,并将头指针,尾指针都指向下表为0的位置,但其实这种初始化头指针指向的是队首,尾指针指向的是队尾的后一个元素。
往队列里添加元素,尾指针后移一位。
一直添加直到队列满
这个时候尾指针已经出现在数组下标外了
每消费一个队列元素,头指针指向的元素出队,并且后移一位
再消费两个
这个时候我们想往队列里继续添加元素,尾指针后移,然后发现出现了假溢出的情况,因为尾指针无法再向后移动,而队列实际上并没有满,我们又无法继续往队列里添加数据。这个时候其实有两种解决方案。
方案一:我们每消费一个元素,其后面的元素都整体往前移动一位,就像我们生活中排队打饭一样,后面的人都往前挪一挪。但这种方案带来的后果是,带来的时间开销太大,因为基本上要操作所有的元素,所以这种方案不可行。
方案二:尾指针在指向下表为最后一个元素时,再添加元素,如果还有空位,就将尾指针重新指向0,头指针在取到下表数组末尾时,如果前面还有元素,头指针也指向0,这就是我们说的环形队列。
尾指针重新指向零
再添加一个元素
连续消费三个元素,如果前面还有元素,头指针也指向0
这个时候我们发现那个原来熟悉的队列又回来了。
/** * description:数组实现环形队列 * author: xiaowang * */ public class MyQueue<E> { // 队列最大个数 private int size; // 元素真实个数 private int number; // 头指针,指向队列的第一个元素即队头 private int front; // 尾指针,指向队尾的后一个元素(非队尾) private int rear; // 队列具体值 private Object[] values; // 队列满标记,当队列是满的时候为true private boolean isFullFlag; /**构造器*/ public MyQueue(int size){ if (size<0){ throw new RuntimeException("初始化队列时,队列最大元素个数不能为负"); } this.front = 0; this.rear = 0; this.number = 0; this.isFullFlag = false; this.size = size; this.values = new Object[size]; } /**往队列里添加元素 添加成功返回true 失败返回false*/ public boolean addToQueue(E e){ // 判断队列是否已经满了 if (isFullFlag){ System.out.println("队列已满,无法继续添加元素"); return false; } // 添加元素 values[rear] = e; // 元素个数加一 number++; // 尾指针后移一位,若已经指向数组最后的下表,则重新指向0 if (rear == size-1){ rear = 0; }else{ rear++; } // 添加完这个元素,判断队列是否已经满了,若满则标记为true if (rear==front){ isFullFlag = true; } return true; } /**从队列里取出数据,队头数据*/ public E getFromQueue(){ // 判断队列是否为空 if (number==0||size==0){ System.out.println("队列为空,无法从队列中获取数据"); return null; } // 临时变量 E e = (E) values[front]; // 队头置空 values[front] = null; // 个数减一 number--; // 头指针后移,若已经指向数组最后的下表,则重新指向0 if (front==size-1){ front = 0; }else { front++; } // 取队列之前若是满的状态,则更新状态 if (isFullFlag){ isFullFlag = false; } return e; } /**获取目前有几个元素正在进行排队*/ public int getNumber(){ return number; } /**获取队列的最大个数*/ public int getSize(){ return size; } /**查看队列在数组里保存的详细情况*/ public String toString(){ StringBuffer valueStr = new StringBuffer(); valueStr.append("["); for (int i = 0; i < size; i++) { if (i!=size-1){ valueStr.append(values[i]+","); }else{ valueStr.append(values[i]+"]"); } } return valueStr.toString(); } }
测试代码
public class TestQueue { public static void main(String[] args) { MyQueue<String> queue = new MyQueue<String>(5); Scanner scanner = new Scanner(System.in); Scanner scanner2 = new Scanner(System.in); boolean isCan = true; while (isCan){ System.out.println("欢迎来到小王排队系统,您可以使用以下功能。\n添加:1;取出:2;展示:3;获取排队个数:4;退出:0。"); int flag = scanner.nextInt(); switch (flag){ case 1 : System.out.println("请输入一个数据:"); String data = scanner2.nextLine(); boolean isSuccess = queue.addToQueue(data); if (isSuccess){ System.out.println("添加成功~~~"); } break; case 2 : String dataFromQueue = queue.getFromQueue(); if (dataFromQueue!=null){ System.out.println("本次取出的数据为:"+dataFromQueue); } break; case 3 : System.out.println("队列详情为:\n"+queue.toString()); break; case 4 : System.out.println("目前有"+queue.getNumber()+"个元素正在进行排队"); break; default: isCan = false; System.out.println("已退出..."); break; } } } }
上述内容就是怎么在java中利用数组实现一个环形队列,你们学到知识或技能了吗?如果还想学到更多技能或者丰富自己的知识储备,欢迎关注亿速云行业资讯频道。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。