Java数组模拟队列

队列

1、队列的理解

​ 个人理解,所有的数据结构都是给数据加的抽象规则,大家都学过数组,我们可以在数组的任意位置实现插入和取数据,但是,如果我给这个插入和取数据施加这样一个规则,我只允许你像排队一样,从队尾插入数据,从队头取数据,这就构成了队列这个数据结构,那么我们需要做什么呢?写代码描述这个规则

上图可能方便理解

如图:
定义一个数组
插入数据:a、b、c、d、e依次按顺序从队尾(rear)端插入数据,array[0] = a,array[1]=b.......
取出数据:只能从队头取,先取队头a

2、先进先出

​ 通过上图,你会发现队列满足先进先出原则,就和排队一样,你先排队,就可以先离开

3、java代码实现

1、确定有哪些元素

  • 头尾标志:rear,front,并且初值都为-1
  • 最大长度
  • 定义一个int类型数组

【代码实现】

public class ArrayQueue {
    //最大长度
    int maxSize;
    //定义一个数组,存储数据
    private int[] queue;
    //定义对头和队尾标志
    private int front;
    private int rear;
    //初始化一个数组
    public void init(int maxSize){
        front = -1;
        rear = -1;
        this.maxSize = maxSize;
        this.queue = new int[maxSize];
    }
    //判断对满
    public boolean isFull(){
         return rear == maxSize-1;
    }
    //判断队空
    public boolean isEnpty(){
        return front == rear;
    }
    //加入数据,只能从队头加入
    public void add(int num){
        if(isFull()){
            System.out.println("队列满了,插入失败");
            return;
        }
        //要理清楚先后顺序
        rear++;
        queue[rear] = num;
    }
    //取数据,只能从队尾取
    public int get(){
        if(isEnpty()){
            System.out.println("队列为空");
            //数组初始化之后默认值就是0
            return 0;
        }
        front++;
        return queue[front];
    }
    //查看队头元素
    public int showFront(){
        if(isEnpty()){
            System.out.println("队列为空");
            //数组初始化之后默认值就是0
            return 0;
        }
        return queue[front+1];
    }
    //遍历所有数
    public void showAll(){
        if(isEnpty()){
            System.out.println("队列为空");
            //数组初始化之后默认值就是0
            return;
        }
        System.out.println("显示队列:======");
        for(int i = front+1; i <= rear; i++){
            System.out.println(queue[i]);
        }
        System.out.println("===============");
    }
}

4、代码改进

【代码改进】
使用这个队列,你会觉得很难受,因为你定义了它的长度,它的长度就不能改变了,我们可以设计一个长度可以增加的队列

【设计思路】
当rear==maxSize,即数组满了的时候,我们新建一个数组,比原数组长一倍,然后将原数组的值赋值到新数组

【代码实现】
我们只要修改add方法的代码

public void add(int num){
    if(isFull()){
        //新建一个长度为原来两倍的数组
        int[] newQueue = new int[maxSize*2];
        //原数组赋值到新数组
        for(int i = front+1; i <= rear; i++){
            newQueue[i] = queue[i];
        }
        rear++;
        queue[rear] = num;
        return;
    }
    rear++;
    queue[rear] = num;
}

【思考】
其实代码还有很多改进空间
1.比如这里我们写死了只能使用int类型的数组,那么我们能不能将类型像参数一样,在初始化队列的时候再确认呢?这里可以用到泛型知识
2.再比如取数据的时候,当这个数不存在的时候我们返回的是默认值0,能不能不返回0,也能使代码正常结束呢,这里可以用到异常知识

5、数据结构的改进

我们会发现,如果使用这种结构来创建队列,当rear增加到指向分配的连续空间之外时,队列无法再插入新元素,
但这时往往还有大量可用空间未被占用,这些空间是已经出队的队列元素曾经占用过得存储单元。环形队列可以解决这种“假溢出现象”

下一篇环形队列:https://www.cnblogs.com/yxm2020/p/12753564.html

原文地址:https://www.cnblogs.com/yxm2020/p/12676323.html