Java实现队列数据结构代码详解

1. 队列数据结构简介

队列（Queue）是一种先进先出(FIFO)的数据结构，支持在一端插入元素，在另一端删除元素并返回删除的元素。其操作包括入队（enqueue）和出队（dequeue）。

2. 队列实现方法

队列可以通过数组或链表来实现。其中，数组实现的队列称为顺序队列，链表实现的队列称为链式队列。

2.1 顺序队列

顺序队列基于数组实现，按照队列的先进先出原则，队列头在数组的左边，队列尾在数组的右边。每次出队操作都会把队列头移动到下一个位置，每次入队操作都会把元素放到队列尾。

2.1.1 顺序队列的实现

public class ArrayQueue<E> {
    private int head;
    private int tail;
    private int size;
    private Object[] data;

    public ArrayQueue(int capacity) {
        data = new Object[capacity];
        head = 0;
        tail = 0;
        size = 0;
    }

    public boolean enqueue(E element) {
        if (size == data.length) {
            return false;
        }
        data[tail] = element;
        tail = (tail + 1) % data.length;
        size++;
        return true;
    }

    public E dequeue() {
        if (size == 0) {
            return null;
        }
        E element = (E) data[head];
        head = (head + 1) % data.length;
        size--;
        return element;
    }
}

2.1.2 顺序队列的示例说明

ArrayQueue<Integer> queue = new ArrayQueue<>(3);
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
System.out.println(queue.enqueue(4)); // false
System.out.println(queue.dequeue()); // 1
System.out.println(queue.dequeue()); // 2
queue.enqueue(4);
System.out.println(queue.dequeue()); // 3
System.out.println(queue.dequeue()); // 4
System.out.println(queue.dequeue()); // null

2.2 链式队列

链式队列基于链表实现，按照队列的先进先出原则，在链表尾部插入元素，在链表头部删除元素。

2.2.1 链式队列的实现

public class LinkedListQueue<E> {
    private Node<E> head;
    private Node<E> tail;
    private int size;

    public LinkedListQueue() {
        head = null;
        tail = null;
        size = 0;
    }

    public boolean enqueue(E element) {
        Node<E> node = new Node<>(element, null);
        if (tail == null) {
            head = node;
            tail = node;
        } else {
            tail.next = node;
            tail = tail.next;
        }
        size++;
        return true;
    }

    public E dequeue() {
        if (size == 0) {
            return null;
        }
        E element = head.data;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        size--;
        return element;
    }

    private static class Node<E> {
        E data;
        Node<E> next;

        public Node(E data, Node<E> next) {
            this.data = data;
            this.next = next;
        }
    }
}

2.2.2 链式队列的示例说明

LinkedListQueue<Integer> queue = new LinkedListQueue<>();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
System.out.println(queue.dequeue()); // 1
System.out.println(queue.dequeue()); // 2
queue.enqueue(4);
System.out.println(queue.dequeue()); // 3
System.out.println(queue.dequeue()); // 4
System.out.println(queue.dequeue()); // null

3. 总结

队列是一种非常实用的数据结构，可以帮助我们实现很多算法和应用。在Java中，队列可以通过数组或链表来实现。顺序队列基于数组实现，链式队列基于链表实现。两者都支持入队和出队操作，但它们的实现方式略有不同，可以根据具体需求选择合适的实现方式。