数据结构1.5:循环队列-学习
程序员文章站
2022-07-14 13:48:30
...
百度百科对于循环队列的解释:
为充分利用向量空间,克服"假溢出"现象的方法是:将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。循环队列是把顺序队列首尾相连,把存储队列元素的表从逻辑上看成一个环,成为循环队列。
通过学习视频,并自己手写了一下循环队列
package com.study.queue;
import java.util.Random;
/**
* 学习循环队列
* Created by Administrator on 2019/8/11.
*/
public class LoopQueue<E> implements Queue<E>{
//采用原生数组来实现循环队列
E[] es;
int front,tail,size;
public LoopQueue(int capacity){
//循环队列中 浪费一个位置 原因当front==tail==0时,为空队列,
// 如果不加一个空间,当向队列中添加最后个元素时,也会使得front==tail,然而此时是满的了
es = (E[])new Object[capacity + 1];
front=0;
tail=0;
size = 0;
}
public LoopQueue(){
this(10);
}
public void add(E e) {
if((tail + 1) % es.length ==front){
//说明循环队列满了,需要做扩容
resize(getCapacity() * 2 );
}
es[tail] = e;
tail = (tail + 1)%es.length;
size++;
}
public E poll(){
if(isEmpty()){
throw new IllegalArgumentException("空的数组");
}
//取出队列头的元素
E e = es[front];
//避免内存溢出
es[front] = null;
//队列头元素 索引位置向后移动一位,循环数组,所以得求余数组的容量
front = (front + 1)%es.length;
size--;
//当数组的长度达到1/4时,缩容,节约空间
if(size == getCapacity() / 4 && getCapacity() / 2!=0){
resize(getCapacity() / 2);
}
return e;
}
private void resize(int capacity) {
E[] newObject = (E[]) new Object[capacity + 1];
for(int i=0;i<size;i++){
//循环数组,队列的头部数据是front
newObject[i] = es[(i+front)%es.length];
}
es = newObject;
front =0;
tail=size;
}
public E peek(){
if(isEmpty()){
throw new IllegalArgumentException("空的数组");
}
//得到队列头的元素
return es[front];
}
public boolean isEmpty() {
return front==tail;
}
public int getSize() {
return size;
}
public int getCapacity(){
return es.length - 1;
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder("Array-length:").append("-容量").append(getCapacity()).append("大小-").append(size).append("-content:[[[[[[");
builder.append("front");
for(int i=0;i<size;i++){
//循环数组,队列的头部数据是front
builder.append(es[(i+front)%es.length]);
if((i+front + 1)%es.length == tail){
builder.append("末尾");
}else{
builder.append(",");
}
}
return builder.toString();
}
public static void main(String[] args) {
LoopQueue<Integer> loopQueue = new LoopQueue();
Random random = new Random();
for(int i=0;i<10;i++){
Integer integer = random.nextInt(10);
System.out.println("入队的值:i"+i+"--"+integer);
loopQueue.add(integer);
}
System.out.println("队列的值:"+loopQueue.toString());
loopQueue.add(500);
System.out.println("队列的值:"+loopQueue.toString());
System.out.println("获取队列的值:"+loopQueue.peek());
System.out.println("队列的值:"+loopQueue.toString());
System.out.println("获取队列的值:"+loopQueue.poll());
System.out.println("队列的值:"+loopQueue.toString());
System.out.println("队列的长度:"+loopQueue.getSize());
System.out.println("队列是否为空:"+loopQueue.isEmpty());
}
}
上一篇: 4-36Flink Distributed Cache分布式缓存
下一篇: 循环队列的C++实现