Java数据结构与算法之队列-蒲公英云

Java数据结构与算法之队列

队列的知识点也不是很复杂，所以直接上代码

package com.wayne.QueueX;
/* * 1， 队列特性：先进先出。 * 2， 折断的序列：队列中的数据项存在数组两个不同的序列中。 * 3， 队列的两个基本操作： * a) 插入一个数据项：把数据项放入队尾 * b) 删除一个数据项：移除队头数据 * 4， 队列的效率 * 队列的插入和移除数据项的时间复杂度均为O(1). */
public class MyQueue { 
    /* * 队列需要有五个元素： * 队列的最大长度maxSize,队列的实际类型queArray, * 队头索引front,队尾索引rear,队列的实际个数nItems */
    private int maxSize;
    private int[] queArray;
    private int front;
    private int rear;
    private int nItems;
    /** * 初始化一个长度为length的空队列 * @param length 队列的预计长度 */
    public MyQueue(int length){
        maxSize = length;
        queArray = new int[maxSize];
        front = 0;//队头删除元素
        rear = -1;//队尾插入元素
        nItems=0;
    }
    /** * 向队尾插入一个元素 * @param i 待插入的元素 */
    public void insert(int i){
        if(rear == maxSize -1)
            rear = -1;
        queArray[++rear] = i;
        nItems++;
    }
    /** * 从队头删除一个元素 * @return 返回移除的元素 */
    public int remove(){
        int temp = queArray[front++];
        if(front == maxSize)
            front = 0;
        nItems--;
        return temp;
    }
    /** * 判断队列是否为空， * @return 如果为空，则返回true;如果不为空，则返回false; */
    public boolean isEmpty(){
        return nItems == 0;
    }
    /** * 判断队列是否满 * @return 如果为满，则返回true；如果不满，则返回false; */
    public boolean isFull(){
        return nItems == maxSize;
    }
    /** * 获取队列的实际长度 * @return 返回队列的实际长度 */
    public int size()
    {
        return nItems;
    }
}

测试用例

package com.wayne.test;
import com.wayne.QueueX.MyQueue;
public class MyQueueTest {
    public static void main(String[] args) {
        MyQueue myQueue = new MyQueue(5);
        myQueue.insert(4);
        myQueue.insert(5);
        myQueue.insert(2);
        myQueue.insert(1);
        myQueue.insert(6);
        myQueue.insert(7);
        myQueue.insert(8);
        myQueue.insert(9);
        System.out.println("the length of the array is "+myQueue.size());
        while(!myQueue.isEmpty())
        {
            System.out.println(myQueue.remove());
        }
    }
}