2021 - 9 -下旬 数据结构- 线性表 -双端循环队列 - java实现
2021/10/6 20:11:01
本文主要是介绍2021 - 9 -下旬 数据结构- 线性表 -双端循环队列 - java实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
//循环双端队列:Circle Double Ended Queue //本质是对动态数组的优化 //队头队尾都可以添加或删除元素 //相比于普通循环队列需要注意的点是在队头插入元素时的对front前移的处理 public class CircleDequeZH<E> { private int size; private int front; private E elements[]; private static final int DEFAULT_CAPACITY = 10; public CircleDequeZH() { elements = (E[]) new Object[DEFAULT_CAPACITY]; } private int getMo(int a, int b){ return a > b ? (a-b) : a; //%运算效率太低,当a<2b时可以用这个表达式替代取模,而循环队列front+index最大等于2*length-1,恰好符合要求 } //计算队头队尾元素下标可以写一个函数,用来映射循环队列中的真实索引 public int realIndexCaculate(int index){ if (index<0){ return getMo((index + front + elements.length), elements.length); //当front=0时,我们在队头插入元素,front要前移,也就是到整个数组的末尾,所以单独写一个if应对这种情况 //这时候front的新位置为(front-1+length)%length } return getMo((index+front),elements.length);//!!! //就是要找队列中的下标为index的(第index+1个)元素,返回它在我们数组里的真实下标 //我觉得影响以后的可读性就没用 } private void ifNeedEnLarge(int needCapacity){ int oldcapacity = elements.length; if (needCapacity<=oldcapacity){ return; }else{ int newcapacity = oldcapacity + (oldcapacity>>1); E[] newElements = (E[]) new Object[newcapacity]; for (int i=0;i<size;i++){ //循环队列获取第i个元素的下标的方式: newElements[i]=elements[(i+front)%elements.length]; //这个扩容的方式就是把队列里的元素依次出队到另一个队列里,同时重置队头的位置 } front = 0; elements = newElements; System.out.println("enLarge Success"+" newCapacity = "+newcapacity); } } public int size(){ return size; } public boolean isEmpty(){ return size == 0; } //清空循环队列,涉及到元素的真实下标计算,同扩容那里 public void clear(){ for (int i = 0;i<size;i++){ elements[(i+front)%elements.length]=null; } size = 0; front = 0; } //出队,主要注意对front的处理 public E deQueueFront(){ E element = elements[front]; elements[front] = null; front = (front+1)%elements.length; size--; return element; } //从队尾出队 public E deQueueNear(){ E element = elements[realIndexCaculate(size-1)]; elements[realIndexCaculate(size-1)] = null; size--; return element; } //从队头入队 public void enQueueFront(E element){ ifNeedEnLarge(size+1); elements[realIndexCaculate(-1)] = element; front = realIndexCaculate(-1); size++; } //入队,主要注意对入队位置的计算 public void enQueueNear(E element){ ifNeedEnLarge(size+1); elements[(front+size)% elements.length] = element; size++; } public String arrayPrint(){ StringBuilder string = new StringBuilder(); string.append("size = ").append(size).append(" ").append("front= ").append(elements[front]).append(" ["); for (int i = 0; i< elements.length; i++ ){ if (elements[i]==null){ string.append("null,"); }else { string.append(elements[i]).append(","); } } string.append("]"); return string.toString(); } }
这篇关于2021 - 9 -下旬 数据结构- 线性表 -双端循环队列 - java实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)