Queue

队列定义

队列是一个实体的集合，它们按顺序维护，并可以通过在序列的一端添加实体以及从序列的另一端移除实体来进行修改。按照约定，元素被添加的序列末端称为队列的后端、尾部或尾端，而移除元素的末端称为队列的前端或头部，这与人们排队等待商品或服务时使用的词汇类似。

VisualizeQueue

队列特点

队列是一种线性数据结构
队列具有先进先出（FIFO）的特性
队列的操作只能在队列的一端进行
队列的实现方式有数组和链表两种

队列操作

enqueue: 将元素添加到队列的末尾
dequeue: 将队列的头部元素移出
peek: 查看队列的头部元素
isEmpty: 判断队列是否为空
size: 获取队列中元素个数

队列实现

Java 链表实现

public class LinkedListQueue<T> {
    // 定义节点类
    private class Node {
        T data;
        Node next;

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

    private Node front;  // 队首指针
    private Node rear;   // 队尾指针
    private int size;    // 队列大小

    // 构造函数
    public LinkedListQueue() {
        front = null;
        rear = null;
        size = 0;
    }

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

    // 获取队列大小
    public int size() {
        return size;
    }

    // 入队
    public void enqueue(T data) {
        Node newNode = new Node(data);
        if (isEmpty()) {
            front = rear = newNode;
        } else {
            rear.next = newNode;
            rear = newNode;
        }
        size++;
    }

    // 出队
    public T dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }

        T data = front.data;
        front = front.next;
        size--;

        if (isEmpty()) {
            rear = null;  // 如果队列变空，需要更新rear指针
        }

        return data;
    }

    // 查看队首元素
    public T peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        return front.data;
    }

    // 清空队列
    public void clear() {
        front = rear = null;
        size = 0;
    }

    // 打印队列中的所有元素
    public void print() {
        if (isEmpty()) {
            System.out.println("Queue is empty");
            return;
        }

        Node current = front;
        System.out.print("Queue: ");
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
}

use example

public class Main {
    public static void main(String[] args) {
        LinkedListQueue<Integer> queue = new LinkedListQueue<>();

        // 测试入队
        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        queue.print(); // Queue: 1 2 3

        // 测试出队
        System.out.println("Dequeued: " + queue.dequeue()); // Dequeued: 1
        queue.print(); // Queue: 2 3

        // 测试peek
        System.out.println("Front element: " + queue.peek()); // Front element: 2

        // 测试size
        System.out.println("Queue size: " + queue.size()); // Queue size: 2

        // 再次入队
        queue.enqueue(4);
        queue.print(); // Queue: 2 3 4

        // 测试清空
        queue.clear();
        System.out.println("Is queue empty? " + queue.isEmpty()); // Is queue empty? true

        // 测试异常情况
        try {
            queue.dequeue(); // 将抛出异常
        } catch (IllegalStateException e) {
            System.out.println("Exception: " + e.getMessage());
        }
    }
}

队列定义

队列特点

队列操作

队列实现

Java 链表实现

Read Next

Linked List

Hash Table