java队列实现方法(顺序队列,链式队列,循环队列)

Java中队列数据结构可以通过顺序队列、链式队列和循环队列三种方法来实现。下面我们将针对这三种方法分别进行详细讲解。

顺序队列实现方法

1. 定义数据结构

首先我们需要定义一个存储元素的数组，以及头尾指针front和rear来记录队列中的元素位置。

public class SeqQueue<T> {
    private T[] data; // 存储元素的数组
    private int front; // 头指针
    private int rear; // 尾指针

    // 构造函数，初始化队列大小
    public SeqQueue(int size) {
        data = (T[]) new Object[size]; // 创建泛型数组
        front = -1;
        rear = -1;
    }
}

2. 入队操作

在队列中插入一个元素需要将元素放在队列的尾部，并更新rear指针。

public boolean enqueue(T element) {
    if (isFull()) { // 判断队列是否已满
        return false;
    }
    rear++;
    data[rear] = element; // 插入元素
    return true;
}

private boolean isFull() { // 判断队列是否已满
    return rear == data.length - 1;
}

3. 出队操作

从队列中取出一个元素需要将元素从队列的头部取出，并更新front指针。

public T dequeue() {
    if (isEmpty()) { // 判断队列是否为空
        return null;
    }
    front++;
    return data[front]; // 返回被取出的元素
}

private boolean isEmpty() { // 判断队列是否为空
    return front == rear;
}

链式队列实现方法

1. 定义数据结构

链式队列的底层数据结构采用链表的方式来实现，因此我们需要定义一个节点Node类来存储元素，以及一个链表类来维护队列。

public class LinkedListQueue<T> {
    private class Node<T> {
        private T data; // 存储元素的值
        private Node<T> next; // 指向下一个节点的指针

        public Node() {
            data = null;
            next = null;
        }

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

    private Node<T> head; // 队列头部指针
    private Node<T> tail; // 队列尾部指针

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

2. 入队操作

入队操作需要创建一个新的节点，并将节点插入到队列的尾部。

public void enqueue(T data) {
    Node<T> newNode = new Node<T>(data); // 创建新节点
    if (head == null) { // 队列为空
        head = newNode;
        tail = newNode;
    } else {
        tail.next = newNode; // 尾部节点指向新节点
        tail = newNode; // 更新尾部指针
    }
}

3. 出队操作

取出队列中的元素需要将队列头部的节点取出，并将头指针指向下一个节点。

public T dequeue() {
    if (head == null) { // 队列为空
        return null;
    }
    Node<T> node = head; // 取出队头节点
    head = head.next; // 更新队列头指针
    return node.data; // 返回节点存储的元素
}

循环队列实现方法

1. 定义数据结构

循环队列需要定义一个数组来存储元素，并且设置头指针和尾指针。

public class CircularQueue<T> {
    private T[] data;
    private int front; // 头指针
    private int rear; // 尾指针

    public CircularQueue(int size) {
        data = (T[]) new Object[size]; // 创建泛型数组
        front = 0;
        rear = 0;
    }
}

2. 入队操作

入队操作需要将元素添加到队列的尾部，并更新尾指针。当尾指针到达数组末尾时，需要将尾指针指向数组开头来实现循环。

public boolean enqueue(T element) {
    if ((rear + 1) % data.length == front) { // 判断队列是否已满
        return false;
    }
    data[rear] = element; // 插入元素
    rear = (rear + 1) % data.length; // 更新尾指针
    return true;
}

3. 出队操作

出队操作需要将头部的元素取出，并更新头指针。当头指针到达数组末尾时，需要将头指针指向数组开头来实现循环。

public T dequeue() {
    if (front == rear) { // 判断队列是否为空
        return null;
    }
    T element = data[front]; // 取出元素
    front = (front + 1) % data.length; // 更新头指针
    return element;
}

示例说明

顺序队列示例

SeqQueue<Integer> queue = new SeqQueue<>(5);
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

链式队列示例

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

循环队列示例

CircularQueue<Integer> queue = new CircularQueue<>(5);
queue.enqueue(1); // 入队
queue.enqueue(2);
queue.enqueue(3);
System.out.println(queue.dequeue()); // 出队，输出1
System.out.println(queue.dequeue()); // 出队，输出2
queue.enqueue(4); // 入队
queue.enqueue(5);
System.out.println(queue.dequeue()); // 出队，输出3
queue.enqueue(6); // 入队
System.out.println(queue.dequeue()); // 出队，输出4
System.out.println(queue.dequeue()); // 出队，输出5
System.out.println(queue.dequeue()); // 出队，输出6
System.out.println(queue.dequeue()); // 出队，输出null