数组实现Java 自定义Queue队列及应用操作

队列（Queue）是一种基本数据结构，它在算法和程序设计中得到了广泛应用。队列主要是用来存储和管理一系列元素，并在这些元素中进行插入和删除操作。本篇攻略将详细介绍如何用Java数组来实现自定义队列，并列举相应的应用操作。

Queue定义

队列最基本的功能就是FIFO（先进先出），可在队列尾插入一个元素，也可在队列头删除一个元素。队列的操作分为如下几种：

• Insert：在队列尾插入一个元素
• Delete: 在队列头删除一个元素
• Peek：获取队列头元素
• isEmpty：判断队列是否空
• isFull：判断队列是否已满

数组实现Java自定义Queue队列

下面我们将用Java语言来实现队列。为了方便起见，我们先定义一个简单的队列类，包含两个成员变量——队列的大小和队列元素数组：

public class MyQueue{
    private int size;
    private int[] elements;
}

Insert操作

队列的Insert操作主要涉及到向队列尾插入一个元素。如果队列已满则不能再插入元素。否则将新元素插入，同时将队尾指针往后移动。

public boolean add(int element){
    if(size == elements.length){ //判断队列是否已满
        return false;
    }
    elements[size++] = element; //将新元素插入队列尾
    return true;
}

Delete操作

队列的Delete操作主要涉及到删除队列头元素。如果队列为空则不能进行此操作。否则将队头指针往后移动，并返回被删除的元素。

public int remove(){
    if(size == 0){ //判断队列是否为空
        throw new NoSuchElementException();
    }
    int removedElement = elements[0]; //获取队头元素
    System.arraycopy(elements, 1, elements, 0, --size); //将元素往前移动
    return removedElement;
}

Peek操作

Peek操作主要涉及到获取队列头元素，但并不删除该元素。如果队列为空则返回null，否则返回队头元素。

public int peek(){
    if(size == 0){ //判断队列是否为空
        return null;
    }
    return elements[0];
}

isEmpty操作

isEmpty操作直接判断队列当前的元素个数是否为0即可。

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

isFull操作

isFull操作判断队列当前的元素个数是否等于队列的大小。

public boolean isFull(){
    return size == elements.length;
}

队列应用示例

1. 实现二叉树层序遍历

队列一般用在树的遍历上，广度优先搜索就是基于队列的。

具体实现方式：从队列中取出一个元素作为根节点，将根节点的左右儿子放入队列尾，然后从队列头取出下一个节点作为待遍历的节点，同样将其左右儿子放入队列尾…依次循环直到队列为空。

public void levelOrderTraversal(TreeNode node) {
    if (node == null)
        return;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(node);
    while (!queue.isEmpty()) {
        TreeNode tmp = queue.poll();
        System.out.print(tmp.value + " ");
        if (tmp.left != null) {
            queue.offer(tmp.left);
        }
        if (tmp.right != null) {
            queue.offer(tmp.right);
        }
    }
}

1. 实现热土豆游戏

热土豆游戏是一种经典的应用场景，它采用了队列数据结构，游戏中的玩家形成一个队列。在游戏中，一旦开始传递土豆，它就以一定的速度在玩家之间传递下去，直到时间结束，最后持有土豆的玩家输掉游戏。

具体实现方法：将各个玩家的编号存入数组，将一个编号数组进行自定义队列存储，随着传递次数的增加，队头出队并重新插入队尾，模拟土豆传递的过程。

public int lastRemaining(int n, int m) {
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        queue.offer(i);
    }
    while (queue.size() > 1) {
        for (int i = 0; i < m - 1; i++) {
            queue.offer(queue.poll());
        }
        queue.poll();
    }
    return queue.poll();
}

以上就是关于数组实现Java自定义Queue队列及应用操作的详细攻略，希望对大家有所帮助。

阅读剩余 65%