侧边栏壁纸
  • 累计撰写 98 篇文章
  • 累计创建 20 个标签
  • 累计收到 3 条评论

数据结构--队列(java实现)

林贤钦
2020-04-15 / 0 评论 / 10 点赞 / 680 阅读 / 0 字
温馨提示:
本文最后更新于 2020-05-09,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

队列

队列是一种先进先出(First in First Out)的线性表,简称FIFO允许插入的一端称为队尾,允许删除的一端称为队头

最简单的来说就是“先进先出,先来先服务,站前面,后来后服务往最后站,排队,不准插队”

顺序队列

简单来理解就是,我给定一个一条队伍的位置,比如5个,第一个来的站第一个,第二个来的站第二个,直达第五个人占第五个,然后出队的时候,我先找第一个,然后第一个出去,其余人不动,我一次找下去直到第五个人出完队

顺序队列通常采用一维数组进行存储,如图:

顺序队列

用数组实现一个顺序队列

队列的四个属性

  	private int maxSize;//表示数组最大的容量
    private int front; //队列头
    private int rear; //队列尾
    private int[] arr; //存放数据,模拟队列

创建顺序队列的时候必须创建输入数组的大小arrMaxSize

public ArrayQueue(int arrMaxSize){
        maxSize=arrMaxSize;
        arr = new int[maxSize];
        front =-1; //指向队列头部,分析出front是指向队列头的前一个位置
        rear = -1; //指向队列尾 , 指向队列尾的数据(也就是队列最后的一个数据)
    }

判断队列为空 rear == front == -1

 return  rear == front;

判断队列是否满(rear达到数组最大下标的值)

return rear == maxSize -1;

进队--->后来的往后面排队加入队列、

public void addQueue(int n){
    //判断队列是否满了
    if (isFull()){
        System.out.println("队列满,不能加入数据了");
        return;
    }
    rear++; //rear后移
    arr[rear] = n;
}

出队--->先进的先出、先来的先进队列,后来的不动。

//获取队列数据,出队列
public  int getQueue(){
    //判断队列是否为空
    if (isEmpty()){
        throw new RuntimeException("队列空,不能取得数据");
    }
    front++;
    return arr[front];
}

具体代码:

public class ArrayQueue {
    private int maxSize;//表示数组最大的容量
    private int front; //队列头
    private int rear; //队列尾
    private int[] arr; //存放数据,模拟队列
    public ArrayQueue(int arrMaxSize){
        maxSize=arrMaxSize;
        arr = new int[maxSize];
        front =-1; //指向队列头部,分析出front是指向队列头的前一个位置
        rear = -1; //指向队列尾 , 指向队列尾的数据(也就是队列最后的一个数据)
    }
    //判断队列是否满
    public boolean isFull(){
        return rear == maxSize -1;
    }
    //判断队列是否为空
    public boolean isEmpty(){
        return  rear == front;
    }
    //添加数据到队列,进队
    public void addQueue(int n){
        //判断队列是否满了
        if (isFull()){
            System.out.println("队列满,不能加入数据了");
            return;
        }
        rear++; //rear后移
        arr[rear] = n;
    }
    //获取队列数据,出队列
    public  int getQueue(){
        //判断队列是否为空
        if (isEmpty()){
            throw new RuntimeException("队列空,不能取得数据");
        }
        front++;
        return arr[front];
    }
    //显示队列所有的数据
    public void showQueue(){
        //遍历
        if (isEmpty()){
            System.out.println("队列为空,没有数据");
            return;
        }
        for (int i = 0; i <arr.length ; i++) {
            System.out.println("arr["+i+"]="+i+"\n");
        }
    }
    public int headQueue(){
        //判断
        if (isEmpty()){
            throw  new RuntimeException(("队列为空,没有数据"));
        }
        return arr[front+1];
    }
}

循环队列

上面的顺序队列,有一个很大的问题,就是这个队列只能用一次,我们可以将上面的顺序队列进行改造,

循环队列,可以这么理解,同样五个位置,0 1 2 3 4 ,先来五个人,队列满了,这时候我找了第一个人,出去一个人,0位置就空出来了,然后0位置又可以进来一个人,不过,我已经从0到1位置了,我只能先服务 1 2 3 4 位置的人,才能回到0 服务最后来的这个人

属性肯定不变、改构造方法,默认 front =rear =0

public CircleArray (int arrMaxSize){
    maxSize = arrMaxSize;
    arr=new int [maxSize];
}

判断为空的条件不用变,当rear == front依然为空

判断队列是否为满的时候我们需要改变一下条件为:

(rear+1)%maxSize ==front

为什么要加一取模呢?

因为我们在加数据到队列的时候,是这样的当rear+1<maxSize的时候,进队,则直接rear++,当rear>= maxSize的时候 则rear =(rear+1)%maxSize,这样rear就能一直保持小于maxSize,也就是为什么上面需要那样写,rear可能是<front

进队、添加数据到队列

public void addQueue(int n){
    //判断队列是否满
    if (isFull()){
        System.out.println("队列满,不能加入数据了");
        return;
    }
    //直接将数据加入
    arr[rear] =n;
    //将rear后移,这里考虑取模,当rear>=maxSize的时候,rear=rear-maxSize
    rear =(rear+1)%maxSize;
}

同理出队的时候也要考虑取模,令front永远小于maxSize

//获取队列数据,出队列
public  int getQueue(){
    //判断队列是否为空
    if (isEmpty()){
        throw new RuntimeException("队列空,不能取得数据");
    }
    int value = arr[front];
    front=(front+1)%maxSize;
    return value;
}

其余代码:

public class CircleArray {
    private int maxSize;//表示数组最大的容量
    //front变量的含义做一个调整: front 指向队列的第一个元素,arr[front%maxSize] 就是队列的第一个元素
    //front的初始值=0
    private int front; //队列头
    //rear变量的含义做一个调整 :rear 指向队列的最后一个位置,因为希望空出一个空间作为约定
    //rear的初始值=0
    private int rear; //队列尾
    private int[] arr; //存放数据,模拟队列
    public CircleArray (int arrMaxSize){
        maxSize = arrMaxSize;
        arr=new int [maxSize];
    }
    //判断队列是否为空
    public boolean isEmpty(){
        return rear ==front;
    }
    //判断队列是否为满
    public boolean isFull(){
        return (rear+1)%maxSize ==front;
    }
    //添加数据到队列
    public void addQueue(int n){
        //判断队列是否满
        if (isFull()){
            System.out.println("队列满,不能加入数据了");
            return;
        }
        //直接将数据加入
        arr[rear] =n;
        //将rear后移,这里考虑取模,当rear>=maxSize的时候,rear=rear-maxSize
        rear =(rear+1)%maxSize;
    }
    //获取队列数据,出队列
    public  int getQueue(){
        //判断队列是否为空
        if (isEmpty()){
            throw new RuntimeException("队列空,不能取得数据");
        }
        int value = arr[front];
        front=(front+1)%maxSize;
        return value;
    }
    //显示队列所有的数据
    public void showQueue(){
        //遍历
        if (isEmpty()){
            System.out.println("队列为空,没有数据");
            return;
        }
        for (int i = front; i <front+size() ; i++) {
            System.out.println("arr["+i%maxSize+"]="+arr[i%maxSize]+"\n");
        }
    }
    public int size(){
        return (rear+maxSize -front)%maxSize;
    }
    public int headQueue(){
        //判断
        if (isEmpty()){
            throw  new RuntimeException(("队列为空,没有数据"));
        }
        return arr[front];
    }
}

10

评论区