java数据结构:队列与实现

时间:2022-05-04 17:38:45

本教程的内容基本来自于《Java数据结构与算法》

队列是一种先进先出的数据结构,如下图。
java数据结构:队列与实现
每次进来新的元素,总是在队列的尾部插入;每次取出队列元素,总是在头部。队列的结构来自于生活中的排队机制。插入元素称为入队,取出元素称为出队。

使用数组实现队列,需要两个指针,一个队尾指针,一个队头指针。

1.初始化队列

class Queue{
    private int rear;               //队尾指针
    private int front;              //队头指针
    private int maxSize;            //队列最大存储
    private int nItems;             //队列中的元素个数
    int[] arr;
    Queue(int maxSize){
        this.maxSize = maxSize;
        arr = new int[maxSize];
        rear = -1;
        front = 0;
        nItems = 0;
    }
}

2.队列是否满了

public boolean isFull(){        //判断队列是否满了
    return nItems==maxSize;
}

3.队列是否为空

public boolean isEmpty(){       //判断队列是否为空
    return nItems==0;
}

4.入队
java数据结构:队列与实现

public void insert(int key){    //元素入队
    if (rear == maxSize-1)
        rear = -1;
    arr[++rear] = key;
    nItems++;
}

5.出队
java数据结构:队列与实现

public int remove(){            //元素出队
    int temp = arr[front++];
    if (front==maxSize)
        front = 0;
    nItems--;
    return temp;
}

6.查看队头元素

public int frontPeek(){         //查看队头元素
    return arr[front];
}

7.查看队列存储的元素个数

public int size(){              //查看队列真实大小
    return nItems;
}

github完整代码:
https://github.com/gamersover/data_structure_java/blob/master/Queue/QueueApp.java