数组实现环形队列(Java)

简介: 数组实现环形队列(Java)


实现思路:

  1. front 表示指向队列第一个元素,初始化为0。
  2. rear 表示指向队列最后一个元素的后一个位置,初始化为0。
  3. 数组实现环形队列需要预留一个空位置(不放元素)。
  4. 当队列已满时,满足:(rear + 1) % capacity == front
  5. 当队列为空时,满足:(rear + capacity - front) % capacity == 0
  6. 当出队列时,front变化满足front = (front + 1) % capacity
  7. 队列元素个数等于(rear + capacity - front) % capacity

完整代码

public class CircleArray {
    private int front;
    private int rear;
    private int capacity;
    int []queue;
    //构造器
    public CircleArray(){
        front = 0;
        rear = 0;
        capacity = 10;
        queue = new int[capacity];
    }
    public CircleArray(int capacity){
        front  = 0;
        rear = 0;
        this.capacity = capacity;
        queue = new int[capacity];
    }
    //判断队列是否已满
    public boolean isFull(){
        return (rear + 1) % capacity == front;
    }
    //判空
    public boolean isEmpty(){
        return (rear + capacity - front) % capacity == 0;
    }
    //入队列
    public void queueAdd(int x){
        if(isFull()){
            throw new RuntimeException("队列已满,不能入队列!");
        }
        queue[rear] = x;
        //会空一个位置
        rear = (rear + 1) % capacity;
    }
    //取数据
    public int queueFront(){
        if(isEmpty()){
            throw new RuntimeException("队列为空,无法取数据!");
        }
        return queue[front];
    }
    //出队列
    public int queuePop(){
        if(isEmpty()){
            throw new RuntimeException("队列为空,不能出队列!");
        }
        int value = queue[front];
        front = (front + 1) % capacity;
        return value;
    }
    //获取队列有效数据的个数
    public int queueSize(){
        return (rear + capacity - front) % capacity;
    }
    //显示队列数据
    public void showQueue(){
        if(isEmpty()){
            throw new RuntimeException("队列为空,无法显示数据!");
        }
        int tmp = front;
        for(int i = 0; i < queueSize(); i++){
            System.out.print(queue[tmp] + " ");
            tmp = (tmp + 1) % capacity;
        }
    }
}

代码测试

测试代码:

class Test01{
    public static void main(String[] args) {
        CircleArray c = new CircleArray(5);
        System.out.println("a:isFull");
        System.out.println("b:isEmpty");
        System.out.println("c:queueAdd");
        System.out.println("d:queueFront");
        System.out.println("e:queuePop");
        System.out.println("f:queueSize");
        System.out.println("g:showQueue");
        Scanner scanner  = new Scanner(System.in);
        while(true){
            char k = scanner.next().charAt(0);
            switch(k){
                case 'a':
                    System.out.println(c.isFull());
                    break;
                case 'b':
                    System.out.println(c.isEmpty());
                    break;
                case 'c':
                    try{
                        c.queueAdd(scanner.nextInt());
                    }catch(RuntimeException e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'd':
                    try{
                        System.out.println("对头数据为:" + c.queueFront());
                    }catch(RuntimeException e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    try{
                        System.out.println(c.queuePop() + "已被出队列!");
                    }catch(RuntimeException e){
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'f':
                    System.out.println(c.queueSize());
                    break;
                case 'g':
                        try{
                            c.showQueue();
                        }catch(RuntimeException e){
                            System.out.println(e.getMessage());
                        }
                        break;
                default:
                        break;
            }
        }
    }
}


相关文章
|
2月前
|
存储 缓存 算法
Java 数组
【10月更文挑战第19天】Java 数组是一种非常实用的数据结构,它为我们提供了一种简单而有效的方式来存储和管理数据。通过合理地使用数组,我们能够提高程序的运行效率和代码的可读性。更加深入地了解和掌握 Java 数组的特性和应用,为我们的编程之旅增添更多的精彩。
33 4
|
2月前
|
存储 缓存 算法
提高 Java 数组性能的方法
【10月更文挑战第19天】深入探讨了提高 Java 数组性能的多种方法。通过合理运用这些策略,我们可以在处理数组时获得更好的性能表现,提升程序的运行效率。
40 2
|
2月前
|
存储 Java
Java“(array) <X> Not Initialized” (数组未初始化)错误解决
在Java中,遇到“(array) &lt;X&gt; Not Initialized”(数组未初始化)错误时,表示数组变量已被声明但尚未初始化。解决方法是在使用数组之前,通过指定数组的大小和类型来初始化数组,例如:`int[] arr = new int[5];` 或 `String[] strArr = new String[10];`。
93 2
|
2月前
|
存储 Java
什么是带有示例的 Java 中的交错数组?
什么是带有示例的 Java 中的交错数组?
53 9
|
2月前
|
Java
Java数组动态扩容和动态缩减
Java数组动态扩容和动态缩减
25 3
|
2月前
|
存储 Java 程序员
【一步一步了解Java系列】:何为数组,何为引用类型
【一步一步了解Java系列】:何为数组,何为引用类型
31 1
|
2月前
|
存储 算法 Java
带你学习java的数组军队列
带你学习java的数组军队列
37 0
时间轮-Java实现篇
在前面的文章《[时间轮-理论篇](https://developer.aliyun.com/article/910513)》讲了时间轮的一些理论知识,然后根据理论知识。我们自己来实现一个简单的时间轮。
|
3天前
|
安全 Java API
java如何请求接口然后终止某个线程
通过本文的介绍,您应该能够理解如何在Java中请求接口并根据返回结果终止某个线程。合理使用标志位或 `interrupt`方法可以确保线程的安全终止,而处理好网络请求中的各种异常情况,可以提高程序的稳定性和可靠性。
26 6
|
18天前
|
设计模式 Java 开发者
Java多线程编程的陷阱与解决方案####
本文深入探讨了Java多线程编程中常见的问题及其解决策略。通过分析竞态条件、死锁、活锁等典型场景,并结合代码示例和实用技巧,帮助开发者有效避免这些陷阱,提升并发程序的稳定性和性能。 ####