java 顺序结构循环队列（源代码）

心已赠人 2023-10-13 16:12 54阅读 0赞

1.import java.util.Arrays;  
    2.public class LoopQueue<T>  
    3.{  
    4.    private int DEFAULT_SIZE = 10;  
    5.    //保存数组的长度。  
    6.    private int capacity;  
    7.    //定义一个数组用于保存循环队列的元素  
    8.    private Object[] elementData;  
    9.    //保存循环队列中元素的当前个数  
    10.    private int front = 0;  
    11.    private int rear = 0;  
    12.    //以默认数组长度创建空循环队列  
    13.    public LoopQueue()  
    14.    {  
    15.        capacity = DEFAULT_SIZE;  
    16.        elementData = new Object[capacity];  
    17.    }  
    18.    //以一个初始化元素来创建循环队列  
    19.    public LoopQueue(T element)  
    20.    {  
    21.        this();  
    22.        elementData[0] = element;  
    23.        rear++;  
    24.    }  
    25.    /** 
    26.     * 以指定长度的数组来创建循环队列 
    27.     * @param element 指定循环队列中第一个元素 
    28.     * @param initSize 指定循环队列底层数组的长度 
    29.     */  
    30.    public LoopQueue(T element , int initSize)  
    31.    {  
    32.        this.capacity = initSize;  
    33.        elementData = new Object[capacity];  
    34.        elementData[0] = element;  
    35.        rear++;  
    36.    }  
    37.    //获取循环队列的大小  
    38.    public int length()  
    39.    {  
    40.        if (empty())  
    41.        {  
    42.            return 0;  
    43.        }  
    44.        return rear > front ? rear - front   
    45.            : capacity - (front - rear);  
    46.    }  
    47.    //插入队列  
    48.    public void add(T element)  
    49.    {  
    50.        if (rear == front   
    51.            && elementData[front] != null)  
    52.        {  
    53.            throw new IndexOutOfBoundsException("队列已满的异常");  
    54.        }  
    55.        elementData[rear++] = element;  
    56.        //如果rear已经到头，那就转头  
    57.        rear = rear == capacity ? 0 : rear;  
    58.    }  
    59.    //移除队列  
    60.    public T remove()  
    61.    {  
    62.        if (empty())  
    63.        {  
    64.            throw new IndexOutOfBoundsException("空队列异常");  
    65.        }  
    66.        //保留队列的rear端的元素的值  
    67.        T oldValue = (T)elementData[front];  
    68.        //释放队列的rear端的元素  
    69.        elementData[front++] = null;   
    70.        //如果front已经到头，那就转头  
    71.        front = front == capacity ? 0 : front;  
    72.        return oldValue;  
    73.    }  
    74.    //返回队列顶元素，但不删除队列顶元素  
    75.    public T element()  
    76.    {  
    77.        if (empty())  
    78.        {  
    79.            throw new IndexOutOfBoundsException("空队列异常");  
    80.        }  
    81.        return (T)elementData[front];  
    82.    }  
    83.    //判断循环队列是否为空队列  
    84.    public boolean empty()  
    85.    {  
    86.        //rear==front且rear处的元素为null  
    87.        return rear == front   
    88.            && elementData[rear] == null;  
    89.    }  
    90.    //清空循环队列  
    91.    public void clear()  
    92.    {  
    93.        //将底层数组所有元素赋为null  
    94.        Arrays.fill(elementData , null);  
    95.        front = 0;  
    96.        rear = 0;  
    97.    }  
    98.    public String toString()  
    99.    {  
    100.        if (empty())  
    101.        {  
    102.            return "[]";  
    103.        }  
    104.        else  
    105.        {  
    106.            //如果front < rear，有效元素就是front到rear之间的元素  
    107.            if (front < rear)  
    108.            {  
    109.                StringBuilder sb = new StringBuilder("[");  
    110.                for (int i = front  ; i < rear ; i++ )  
    111.                {  
    112.                    sb.append(elementData[i].toString() + ", ");  
    113.                }  
    114.                int len = sb.length();  
    115.                return sb.delete(len - 2 , len).append("]").toString();  
    116.            }  
    117.            //如果front >= rear，有效元素为front->capacity之间、0->front之间的  
    118.            else  
    119.            {  
    120.                StringBuilder sb = new StringBuilder("[");  
    121.                for (int i = front  ; i < capacity ; i++ )  
    122.                {  
    123.                    sb.append(elementData[i].toString() + ", ");  
    124.                }  
    125.                for (int i = 0 ; i < rear ; i++)  
    126.                {  
    127.                    sb.append(elementData[i].toString() + ", ");  
    128.                }  
    129.                int len = sb.length();  
    130.                return sb.delete(len - 2 , len).append("]").toString();  
    131.            }  
    132.        }  
    133.    }  
    134.}

队列是一种特殊的线性表，它只允许在表的前端(front)进行删除操作，只允许在表的后端（rear）进行插入操作。