ArrayList链表实现循环队列

布满荆棘的人生 2022-06-11 00:46 180阅读 0赞

首先介绍下非循环队列的实现形式，不管用链表还是数组实现，总会有两个变量记录队头和队尾的位置

![20170726143858573][]

当头尾都指向了索引0位置时，则代表队列中没有元素。

![20170726144057794][]

当进行第一次入队操作后，头指向第一个位置。而尾指向最后一个元素的下一个位置。

![20170726144813104][]

进行了四次入队操作后。

![20170726144904301][]

当第一次进行出队操作后，头指向的位置往后移动一位。

从这里就可以看出，这种队列实现，**头永远指向的是第一个元素，而尾永远指向的是最后一个元素的下一个位置**。

![20170726145109824][]

当尾代表的索引值，已经是最大索引值+1时，则代表队列已满。

![20170726145450743][]

但是如果一直出队，直到队列元素只有一个时，队列此时也会认为队列已经满了。这样的队列就没有意义了，这种现象也叫做队列假溢出。

而循环队列则解决这个问题，如果尾到达最大索引+1时且队列实际还有位置没有用，就把尾位置指向0索引。

![20170726151324577][]

但是如果队列中不留出一个永远不会去用的位置，那么判断队列满的条件就判断队列空的条件是一样的了，都是head==tail。

比如上图，tail的位置根据循环队列的思想就会变成0索引，此时，队满，而head=tail=0。

![20170726151645463][]

而如果拿出一个位置不使用，只是用来帮助判断队满的情况，就解决了这个问题。通过(rear + 1) % maxSize == front来判断。

代码如下：

package three;
    
    import java.util.*;
    
    public class SingleQueueArray<AnyType>
    {
    SingleQueueArray()
    { this(101); } // note: actually holds one less than given size
                   //实际上使用的是给定的大小减一
    SingleQueueArray(int s)
    {
    maxSize = s;
    front = 0;
    rear = 0;
    elements = new ArrayList<AnyType>(maxSize);
    }
    void enqueue(AnyType x)//入队
    {
    if ( !full() )
    {
    if (elements.size() < maxSize) // add elements until size is reached
    elements.add(x);  //如果队尾从来没有到达过最后位置
    else
    elements.set(rear, x); // after size is reached, use set
    //如果已经到达了最后位置，即链表已经被装满了，以后的情况也会是装满的情况了
    rear = (rear + 1) % maxSize;
    }
    }
    AnyType dequeue()//出队
    {
    AnyType temp=null;
    if ( !empty() )
    {
    temp = elements.get(front);
    front = (front+1) % maxSize;
    }
    return temp;
    }
    
    boolean empty()
    { return front == rear; }
    
    boolean full()
    { return (rear + 1) % maxSize == front; }
    
    private int front, rear;
    private int maxSize;
    private ArrayList<AnyType> elements;
    }

[20170726143858573]: /images/20220611/0f6c5adc5831492280b4ee72b449e597.png
[20170726144057794]: /images/20220611/2b85739a62a24bdbb303cc5a760a185c.png
[20170726144813104]: /images/20220611/560ebfbc43dc49d8b92fd96c1a49279d.png
[20170726144904301]: /images/20220611/25fb9f7560164784ae2306a15e70db4d.png
[20170726145109824]: /images/20220611/deb31cf17fb444f58658298b4cdaafe7.png
[20170726145450743]: /images/20220611/a18ca73107004db7afbd18ac320113e8.png
[20170726151324577]: /images/20220611/bfd29791a30d42a1a967992ed1741247.png
[20170726151645463]: /images/20220611/deae48a877c945e78558183070c504cc.png