欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构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());
    }

}

 

相关标签: 循环队列