1.用数组的方式实现队列和循环队列

2020年11月3日 11点热度 0条评论 来源: 爱就码上行动

1.队列的认知

1.1队列的初认知:

  • 生活实际中的队列:例如银行排队,取餐排队等等
  • 队列的特点:先进先出

2实现队列的方式:

  • 数组(顺序存储)
  • 链表(非线性存储);

3.数组实现队列的思路

如图所示:

Maxsize为数组的最大长度。front 为队列的头指针,rear为队列的尾指针,最开始他们都指向-1;

当队列为空时:rear= front;

当队列已满时:rear = Maxsize-1;

4.数组模拟队列的构建,出队,入队的操作

4.1队列的构造和入队出队

public class Queue { 
    int maxSize;//队列最大容量
    int rear;//模拟队尾头指针
    int front;//模拟队列头指针
    Object[] array; //使用数组模拟队列

    /** * 队列初始化 * * @param maxSize 队列最大容量 * @return */
    public Queue(int maxSize) { 
        rear = -1;
        front = -1;
        this.maxSize = maxSize;
        this.array = new Object[maxSize];
    }


    /** * 入队方法 * * @param e 入队元素 * @return */
    public boolean enQueue(int e) { 
        if (rear >= maxSize - 1) { 
            System.out.println("队满,入队失败!");
            return false;
        } else { 
            rear++;//指针后移
            array[rear] = e;//存入元素,入队
        }
        return true;

    }

    /** * 出队方法 * * @return */
    public Object deQueue() { 
        if (front == rear) { 
            System.out.println("队空,出队失败!");
            throw new RuntimeException("队空!");
        } else { 
            front++; //指针后移,出队
        }
        Object obj = array[front];//暂存出队元素
        array[front] = null;
        return obj;

    }

    /** * 重写toString 用于格式化输出队列 */
    public String toString() { 
        StringBuilder sb = new StringBuilder();
        sb.append("队首<");
        for (int i = 0; i < 10; i++) { 
            sb.append(array[i]);
            if (i == 9)
                continue;
            sb.append("-");
        }
        sb.append("<队尾");
        String s = "" + sb;
        return s;
    }

}

4.2编写测试用例测试上述的各种方法

public class Test { 
    public static void main(String[] args) { 
        Queue queue = new Queue(10);
        //入队6个元素
        for(int i = 0;i<6;i++) { 
            queue.enQueue(i);
        }
        //输出队列
        System.out.println("入队后队列状态:"+queue);
        //出队两个元素
        Object e1 = queue.deQueue();
        Object e2 = queue.deQueue();
        //输出出队的元素
        System.out.println("出队元素:"+e1+","+e2);
        //输出出队操作后的队列
        System.out.println("出队后队列状态:"+queue);

    }

但是这种方式往往使得数组无法复用,需要进行优化。(即数组进行出队操作以后,会有使数组的前列无法使用)

5.优化的思路

5.1解决方案:用数组模拟环形队列

5.2思路改进:

如图:

5.2.1在这里我们让front指向第一个元素,将rear指向队尾元素的下一个元素(用来留下一个元素空间,便于区分队列为空为满的条件),初始:front = 0,rear = 0。

5.2.2问题:当队列满了的时候,front=rear,如何才能分别队列为空还是为满呢??

两种实现方案:

  • 设置一个标志变量flag,当front == rear,并且flag= 0时,队列为空,当 front = rear,且flag=1时,队列为满。
  • 当队列为空的时候front = rear,当队列满的时候,保留一个元素空间,即(rear+1)%Maxszie时为满,这种方法的有效个数为(rear+Maxsize-front)%Maxsize

在循环中,取模是一种非常重要的实现方式,要善于利用取模的思想

这里重点讲第二种实现方式

5.3代码实现:

循环队列类:

package com.chen.java;

public class LoopQueue { 


    int maxSize; //定义队列最大容量
    int front;        //模拟头指针
    int rear;        //模拟尾指针
    Object[] array;    //使用数组模拟内存空间

    //循环队列的初始化
    public LoopQueue(int maxSize) { 
        front = 0;
        rear = 0;
        this.array = new Object[maxSize];
        this.maxSize = maxSize;
    }

    //入队操作
    public void enQueue(Object obj) { 
        if ((rear + 1) % maxSize == front) { //判断队满与否
            System.out.println("队满,入队失败");
            throw new RuntimeException("队满无法入队!");
        } else { 

            //一定要理解取模的思想
            array[rear] = obj;
            rear = (rear + 1) % maxSize;
        }
    }

    //出队列
    public Object deQueue() { 

        if (rear == front) { //判断队空与否
            System.out.println("队空,出队失败");
            throw new RuntimeException("队空无法出队!");
        } else { 
            Object objTemp = array[front];//暂存出队元素
            front = (front + 1) % maxSize;
            return objTemp;//返回出队元素
        }

    }

    //重写toString方法
    public String toString() { 
        StringBuilder sb = new StringBuilder();

        sb.append(array[1]);
        sb.append("—————————");
        sb.append(array[2]);
        sb.append("—————————");
        sb.append(array[3]);
        sb.append("\n| |");
        sb.append("\n| |");
        sb.append("\n| |");
        sb.append("\n");
        sb.append(array[7]);
        sb.append(" ");
        sb.append(array[4]);
        sb.append("\n| |");
        sb.append("\n| |");
        sb.append("\n| |");
        sb.append("\n");
        sb.append(array[6]);
        sb.append("———————————————————");
        sb.append(array[5]);

        String s = "" + sb;
        String str = s.replaceAll("null", "*");
        return str;
    }


}

ppend("\n");
sb.append(array[6]);
sb.append("———————————————————");
sb.append(array[5]);

    String s = "" + sb;
    String str = s.replaceAll("null", "*");
    return str;
}

}


- 实现类同上
    原文作者:爱就码上行动
    原文地址: https://blog.csdn.net/qq_41665826/article/details/109468717
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。