java怎么实现环形队列

今天小编给大家分享一下java怎么实现环形队列的相关知识点,内容详细,逻辑清晰,相信大部分人都还太了解这方面的知识,所以分享这篇文章给大家参考一下,希望大家阅读完这篇文章后有所收获,下面我们一起来了解一下吧。

创新互联是一家专注于网站建设、网站制作与策划设计,大田网站建设哪家好?创新互联做网站,专注于网站建设十载,网设计领域的专业建站公司;建站业务涵盖:大田等地区。大田做网站价格咨询:13518219792

1、普通队列存在什么问题?

队列大家都知道,有几个重要的属性:

  • rear:指向队列的尾巴,即最后一个元素所在的位置,初始值为-1
  • front:指向队列的头部的前一个位置,初始值也为-1
  • capacity:队列的容量

空队列的rear和front都等于-1,入队时,front不动,rear++,当 rear == capacity - 1时,队列已满;出队时,rear不动,front++,当front == rear时,队列为空。看起来很完美,但实际上有问题。假如一个队列capacity = 3,入队了三个元素,此时front = -1; rear = 2,然后再将三个元素都出队,此时front = 2, rear = 2。这时队列明明是空的,但是却不能再入队元素的,因为满足rear = capacity - 1,也就是相当于这队列是一次性的,用过之后就不能再用了,即使为空也不能再入队了,造成空间的浪费,所以环形队列就出现了。

2、环形队列实现思路:

环形队列中的几个重要属性:

  • rear:指向队列尾巴的后一个位置,初始值为0
  • front:指向队列的头部,即第一个元素所在的位置,初始值为0
  • capacity:队列的容量

下面是环形队列的一些算法:

  • 队列为空时:      front == rear
  • 队列已满时:      (rear + 1) % capacity == front
  • 获取队列元素个数:      (rear + capacity - front) % capacity
  • 入队操作时:      rear = (rear + 1) % capacity
  • 出队操作时:      front = (front + 1) % capacity;

判断队列是否已满是环形队列中最重要也是最难理解的地方。假如有一个队列capacity = 3,入队操作如下:

  • 第一个元素入队:      front = 0,因为      (rear + 1) % capacity = 1 % 3 != front,所以元素可以入队,元素入队后      rear = 1
  • 第二个元素入队:      front = 0,因为      (rear + 1) % capacity = 2 % 3 != front,所以元素可以入队,元素入队后      rear = 2
  • 第三个元素入队:      front = 0,因为      (rear + 1) % capacity = 3 % 3 == front,所以元素不能入队,队列已满;

队列容量明明是3,只入队了两个元素就告诉我队列满了?没错,这种判断队列是否已满的算法需要牺牲数组的一个空间。

现在进行出队操作:

  • 第一个元素出队:      front = 1,      rear = 2,      (rear + 1) % capacity = 3 % 3 = 0 != front

可以发现,当一个元素出队后,又满足入队条件了,所以数组空间就可以重复利用了。

3、代码实操:

public class CircleQueue {
    private int capacity;
    private int front;
    private int rear;
    private Object[] arr;

    public CircleQueue(int capacity){
        this.capacity = capacity;
        this.arr = new Object[capacity];
        this.front = 0;
        this.rear = 0;
    }

    public boolean isFull(){
        return (rear + 1) % capacity == front;
    }

    public boolean isEmpty(){
        return rear == front;
    }

    public void addQueue(E e){
        if (isFull()){
            throw new RuntimeException("队列已满,入队失败");
        }
        arr[rear] = e;
        // rear指针后移
        rear = (rear + 1) % capacity;
    }

    public E getQueue(){
        if (isEmpty()){
            throw new RuntimeException("队列为空,出队失败");
        }
        E val = (E) arr[front];
        front = (front + 1) % capacity;
        return val;
    }


    public int getSize(){
        return (rear + capacity - front) % capacity;
    }

    // 遍历
    public void showQueue(){
        if (isEmpty()){
            return;
        }
        for (int i = front; i < front + getSize(); i++) {
            System.out.printf("arr[%d]=%d\n", i%capacity, arr[i%capacity]);
        }
    }

    public static void main(String[] args){
        CircleQueue queue = new CircleQueue<>(3);
        queue.addQueue(1);
        queue.addQueue(2);
        queue.showQueue();
        //queue.addQueue(3);
        System.out.println(queue.getSize());
        System.out.println(queue.getQueue());;
        queue.addQueue(3);
        queue.showQueue();
    }
}

以上就是“java怎么实现环形队列”这篇文章的所有内容,感谢各位的阅读!相信大家阅读完这篇文章都有很大的收获,小编每天都会为大家更新不同的知识,如果还想学习更多的知识,请关注创新互联行业资讯频道。


本文标题:java怎么实现环形队列
当前地址:http://scyanting.com/article/pcssdc.html