关于java:Java实现循环队列

9次阅读

共计 1678 个字符，预计需要花费 5 分钟才能阅读完成。

队列是一种非凡的线性表，非凡之处在于它只容许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作

1、链表队列

2、动态队列（数组）

class Queue {
    private int front;
    private int rear;
    private Object[] objects;
    private int size;
    
    public Queue(int size) {
        front = 0;
        rear = 0;
        this.size = size + 1;
        objects = new Object[size];
    }
    
    public void add(Object o) {if (isFull()) {System.out.println("队列已满，无奈增加");
            return;
        }
        objects[rear] = o;
        rear = (rear + 1) % size;
    }
    
    public Object get() throws EmptyException {if (isEmpty()) {throw new EmptyException("队列为空，无奈取出元素");
        }
        Object o = objects[front];
        front = (front + 1) % size;
        return o;
    }
    
    public boolean isEmpty() {return front == rear;}
    
    public boolean isFull() {return (rear + 1) % size == front;
    }
    
    public int getCount() {return (rear - front + size) % size;
    }
    
    public void show() {int count = getCount();
        for(int i = 0; i < count; i++) {System.out.println(objects[front]);
            front = (front + 1) % size;
        }
    }
}

class EmptyException extends Exception {public EmptyException() { }
    
    public EmptyException(String s) {super(s);
    }
}

front 永远指向队列的 第一个元素
rear 永远指向队列的最初一个元素的 下一个地位

队列进行初始化，front = 0，rear = 0;

为什么要 this.size = size + 1; 前面在解释

依据 front rear 的意义，不难得出判断队列是否为空就是 front == rear
咱们来看下判断队满的条件

如图，此时在增加元素 5，队列就满了，同时 rear = 0

这个时候咱们发现，rear == front
因而队列满的条件为：rear == front
这与判断队列空的条件雷同，然而此时队列是有元素的
队列元素：2，6，3，0，1，5
因而队列满的条件不能是：rear == front
咱们通常会舍弃一个空间（不用来存放数据），也就是说，大小为 n 的数组，寄存的元素的个数为 n – 1
这样判断队满的条件就变为：(rear + 1) % size == front
这也就是为什么 this.size = size + 1
因为他人不晓得，你只能寄存 n – 1 个数据

获取元素的个数
当 rear > front
元素个数为：rear – front

元素个数为：5 – 0 = 5
当 rear < front

第一段为：size – front
第二段为：rear – 0
因而，元素个数为：(rear – front + size)
联合两种状况：
rear > front
(rear – front + size) % size = rear – front
rear < front
(rear – front + size) % size = rear – front + size
因而，通用公式为：(rear – front + size) % size