JAVA数据结构之队列

在计算机科学中，队列是一种数据结构，有点类似栈，只是在队列中第一个插入的数据也会最先被移除（先进先出，FIFO），而在栈中，最后插入的数据项最先移除。队列的作用就像电影院前的人们站成一排：第一个进入队尾的人就最先到达队头

基于数组的队列：

当在队列中插入一个新的数据项，队头的下标加一，移向数组下标大的位置。当移除数据时，队尾front指针也会向上移动，但是这样设计的问题是队尾指针很快就会移动到数组的末端（数组下标最大的地方），当一直先插入的数组的时候，队头一直向上移动，那么在数组的开始部分就会空出数据项单元（注意：队尾rear的下标为-1，队头为0），为了避免队列不满却不能插入新数据项的问题，可以让队头队尾的指针绕回数组的开始位置，这就是循环队列，也称为缓冲环

public class Queue {
    private int maxSize;

    private long[] queArray;

    private int rear;

    private int front;

    private int nItems;

    public Queue(int s){
        maxSize=s;
        queArray=new long[maxSize];
        front=0;
        rear=-1;
        nItems=0;
    }

    public void insert(long j) throws Exception {
        if (isFull()){
             throw new Exception("队列已满");
        }
//        判断是否已满
        if(rear==maxSize-1){
            rear=-1;
        }
        //插入元素队头下标++
        queArray[++rear]=j;
        nItems++;
    }

    public long remove() throws Exception {
        if(isEmpty()){
            throw new Exception("队列已空");
        }
        long temp=queArray[front++];
        if(front==maxSize){
            front=0;
        }
        nItems--;
        return temp;
    }

    public long peekFront(){
        return queArray[front];
    }

    public boolean isEmpty(){
        return (nItems==0);
    }

    public boolean isFull(){
        return (nItems==maxSize);
    }

    public int size(){
        return nItems;
    }

    public static void main(String[] args) throws Exception {
        Queue queue=new Queue(5);
        queue.insert(10);
        queue.insert(120);

        queue.insert(130);

        queue.insert(410);

        queue.remove();
        queue.remove();
        queue.remove();

        queue.insert(50);
        queue.insert(60);
        queue.insert(70);
        queue.insert(80);

        while (!queue.isEmpty()){
            System.out.println(queue.remove());
        }

    }
}

和栈一样，队列中插入数据项和移除数据项的时间复杂度均为O(1)