Java数组实现循环队列的两种方法RingBuffer

爱被打了一巴掌 2021-09-19 17:12 658阅读 0赞

用java实现循环队列的方法：

1、增加一个属性size用来记录目前的元素个数。目的是当head=rear的时候，通过size=0还是size=数组长度，来区分队列为空，或者队列已满。

2、数组中只存储数组大小-1个元素，保证rear转一圈之后不会和head相等，也就是队列满的时候，rear+1=head，中间刚好空一个元素。

当rear=head的时候，一定是队列空了。

队列(Queue)两端允许操作的类型不一样：

可以进行删除的一端称为队头，这种操作也叫出队dequeue；

可以进行插入的一端称为队尾，这种操作也叫入队enqueue。

队列的示意图

![Center][]

实现队列时，要注意的是假溢出现象，如上图的最后一幅图。

如图所示的假溢出现象

![Center 1][]

解决办法：使用链式存储，这显然可以。在顺序存储时，我们常见的解决办法是把它首尾相接，构成循环队列，这可以充分利用队列的存储空间。

循环队列示意图：

![Center 2][]

在上图中，front指向队列中第一个元素，rear指向队列队尾的下一个位置。

但依然存在一个问题：当front和rear指向同一个位置时，这代表的是队空还是队满呢？大家可以想象下这种情景。

解决这种问题的常见做法是这样的：

使用一标记，用以区分这种易混淆的情形。

牺牲一个元素空间。当front和rear相等时，为空；当rear的下一个位置是front时，为满。

如下图：

![Center 3][]![Center 4][]

下面我们给出循环队列，并采用第二种方式，即牺牲一个元素空间来区分队空和队满的代码.

几个重点：

1、front指向队头，rear指向队尾的下一个位置。

2、队为空的判断：front==rear；队为满的判断：(rear+1)%MAXSIZE==front。

import java.io.*;
        public class QueueArray {   
        Object[] a; //对象数组，队列最多存储a.length-1个对象   
        int front;  //队首下标   
        int rear;   //队尾下标   
        public QueueArray(){   
            this(10); //调用其它构造方法   
        }   
        public QueueArray(int size){   
            a = new Object[size];   
            front = 0;   
            rear =0;   
        }   
        /**  
         * 将一个对象追加到队列尾部  
         * @param obj 对象  
         * @return 队列满时返回false,否则返回true  
         */  
        public boolean enqueue(Object obj){   
            if((rear+1)%a.length==front){   
                return false;   
            }   
            a[rear]=obj;   
            rear = (rear+1)%a.length;   
            return true;   
        }   
        /**  
         * 队列头部的第一个对象出队  
         * @return 出队的对象，队列空时返回null  
         */  
        public Object dequeue(){   
            if(rear==front){   
                return null;   
            }   
            Object obj = a[front];   
            front = (front+1)%a.length;   
            return obj;   
        }   
        public static void main(String[] args) {   
            QueueArray q = new QueueArray(4);   
            System.out.println(q.enqueue("张三"));   
            System.out.println(q.enqueue("李斯"));   
            System.out.println(q.enqueue("赵五"));   
            System.out.println(q.enqueue("王一"));//无法入队列，队列满   
            for(int i=0;i<4;i++){   
                System.out.println(q.dequeue());   
            }   
        }   
    }

[Center]: /images/20210527/6853a6eafee04c8f8b3b471801820785.png
[Center 1]: /images/20210527/41d74c3e5a3f4739a6add77547a8e2b9.png
[Center 2]: /images/20210527/9c48b690ae00459c9296bacacdb5c4db.png
[Center 3]: https://img-blog.csdn.net/20150623125730736?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvVmljdG9yX0NpbmR5MQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 4]: /images/20210527/f3b98bba70f242af81f7d7b8818f6b0b.png