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

数据结构之循环队列

程序员文章站 2022-06-06 20:46:29
...

循环队列:
为充分利用向量空间,克服”假溢出”现象的方法是:将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。
循环队列结构
数据结构之循环队列

判读循环队列为满或者为空的方法
1、当head=rear的时候,队列为空
2、当head=rear+1的时候,队列为满

/**
 * 循环队列,先进先出
 * 
 * 
 * */
class queuelink{
    int []elem;
    int front;//队头
    int rear;//队尾
    int usesize=0;//当前循环队列的有效数据个数
    int allsize=10;//

    public queuelink(){
        this(10);
    }
    public queuelink(int size) {

        this.elem=new int[size];
        this.front=0;
        this.rear=0;

    }
    //判断是否为满
    public boolean isfull(){
        if((this.rear+1)%this.allsize==this.front){
            return true;
        }
        return false;
    }

    //入队
    public void push(int val){
        if(isfull()){//如果数组为满的,直接跳出
            return;

        }
        this.elem[this.rear]=val;
        this.rear=(this.rear+1)%this.allsize;
        this.usesize++;
    }
    //判断是否为空
    public boolean isempty(){
        return this.front==this.rear;
    }
    //出队
    public void pop(){
        if(isempty()){
            return ;
        }
        this.elem[this.front]=-1;//把原来第一号元素给覆盖掉
        this.front=(this.front+1)%this.allsize;//让数组下标像后面移动
        this.usesize--;

    }
    //得到第一个元素
    public int  getfront(){
        if(isempty()){//如果数组为空,返回-1
            return -1;
        }
        return  this.elem[this.front];}//如果不为空直接返回elem[this.front]  
    //打印队列
    public void show(){
        for(int i=this.front;i<rear;i=(i+1)%this.allsize){//此处不能使用i++           
        System.out.println(this.elem[i]);
        }
    }
}

public class test1 {

    public static void main(String[] args) {
        queuelink t1=new queuelink();
        for(int i=0;i<9;i++){
            t1.push(i);
        }

    System.out.println("原队列");
        t1.show();
        t1.pop();
        System.out.println("删除一个元素之后");
        t1.show();


        // TODO Auto-generated method stub

    }

}

运行结果:
原队列
0
1
2
3
4
5
6
7
8
删除一个元素之后
1
2
3
4
5
6
7
8