Java语言通过三种方法实现队列的示例代码

下面是关于“Java语言通过三种方法实现队列”的详细攻略：

一、队列的定义

在计算机科学中，队列是一种特殊的线性数据结构，它只允许在一端进行插入操作，在另一端进行删除操作。在队列中，进行插入操作的一端被称为队尾，进行删除操作的一端被称为队头。

二、常见的队列实现方法

实现队列的方法有很多，其中比较常见的包括：

1、使用数组实现队列

使用数组来实现队列，可以通过数组的下标来判断队列是否为空或已满。当队列已满时，需要进行队列扩容，将数组大小增加一倍。

下面是使用数组实现队列的示例代码：

class ArrayQueue {

    private int[] queue; // 存储队列元素的数组

    private int head;   // 队头

    private int tail;   // 队尾

    public ArrayQueue(int capacity) {
        queue = new int[capacity];
    }

    public boolean enqueue(int item) {
        if (tail == queue.length) {
            if (head == 0) {
                return false; // 队列已满
            } else {
                // 数据搬移，空出队列空间
                for (int i = head; i < tail; i++) {
                    queue[i-head] = queue[i];
                }
                tail -= head;
                head = 0;
            }
        }
        queue[tail] = item;
        tail++;
        return true;
    }

    public int dequeue() {
        if (head == tail) {
            return -1; // 队列为空
        }
        int item = queue[head];
        head++;
        return item;
    }

}

2、使用链表实现队列

使用链表来实现队列，可以通过链表的头尾指针来判断队列是否为空，并且不需要进行队列扩容。

下面是使用链表实现队列的示例代码：

class LinkedQueue {

    private Node head;  // 队头指针

    private Node tail;  // 队尾指针

    public LinkedQueue() {
        head = tail = null;
    }

    public boolean enqueue(int item) {
        Node node = new Node(item);
        if (tail == null) {
            head = tail = node;
        } else {
            tail.next = node;
            tail = node;
        }
        return true;
    }

    public int dequeue() {
        if (head == null) {
            return -1; // 队列为空
        }
        int item = head.data;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        return item;
    }

    private class Node {

        private int data;   // 节点的数据

        private Node next;  // 指向下一个节点的指针

        public Node(int data) {
            this.data = data;
            this.next = null;
        }

    }

}

3、使用Java集合框架中的Queue接口实现队列

Java集合框架中提供了一个Queue接口，它是用来表示队列的。其中比较常用的实现类有ArrayDeque和LinkedList。

下面是使用Java集合框架中的Queue接口实现队列的示例代码：

class CollectionQueue {

    private Queue<Integer> queue;

    public CollectionQueue() {
        queue = new LinkedList<>();
    }

    public boolean enqueue(int item) {
        return queue.offer(item);
    }

    public int dequeue() {
        Integer item = queue.poll();
        return item == null ? -1 : item;
    }

}

三、示例说明

下面给出两个示例，分别说明如何使用上述三种方法来实现队列。

1、使用数组实现队列

// 创建一个数组实现的队列，容量为 3
ArrayQueue queue = new ArrayQueue(3);

// 往队列中加入元素
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.enqueue(4); // 队列已满，数据无法入队

// 从队列中取出元素并输出
System.out.println(queue.dequeue()); // 输出 1
System.out.println(queue.dequeue()); // 输出 2
System.out.println(queue.dequeue()); // 输出 3
System.out.println(queue.dequeue()); // 输出 -1，队列为空

2、使用Java集合框架中的Queue接口实现队列

// 创建一个使用LinkedList实现的队列
CollectionQueue queue = new CollectionQueue();

// 往队列中加入元素
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);

// 从队列中取出元素并输出
System.out.println(queue.dequeue()); // 输出 1
System.out.println(queue.dequeue()); // 输出 2
System.out.println(queue.dequeue()); // 输出 3
System.out.println(queue.dequeue()); // 输出 -1，队列为空

希望这篇攻略能够对你有所帮助！