每日算法 — 使用java实现队列：银行叫号系统与优先级调度

引言

队列（Queue）是一种先进先出（FIFO, First In First Out）的线性数据结构。与栈的后进先出相反，队列确保了最早进入的元素最先被处理。这种特性使队列成为模拟排队、任务调度、消息传递等场景的理想选择。本文将以银行叫号系统为切入点，逐步引入普通队列、循环队列、双端队列和优先级队列，并用Java实现完整代码。

队列的基本概念

队列的核心操作：
– enqueue（入队）：在队尾添加元素
– dequeue（出队）：从队首移除元素
– peek/front：查看队首元素
– isEmpty：判断队列是否为空

基于数组的队列实现

/**
 * 基于数组的循环队列实现
 * 使用头尾指针避免频繁搬移元素
 */
public class ArrayQueue<T> {
    private Object[] data;
    private int front;    // 队首索引
    private int rear;     // 队尾索引（下一个入队位置）
    private int size;
    private static final int DEFAULT_CAPACITY = 16;

    public ArrayQueue() {
        this.data = new Object[DEFAULT_CAPACITY];
        this.front = 0;
        this.rear = 0;
        this.size = 0;
    }

    /**
     * 入队操作
     */
    public void enqueue(T item) {
        ensureCapacity();
        data[rear] = item;
        rear = (rear + 1) % data.length; // 循环移动
        size++;
    }

    /**
     * 出队操作
     */
    @SuppressWarnings("unchecked")
    public T dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException("队列为空");
        }
        T item = (T) data[front];
        data[front] = null; // 防止内存泄漏
        front = (front + 1) % data.length;
        size--;
        return item;
    }

    /**
     * 查看队首元素
     */
    @SuppressWarnings("unchecked")
    public T peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("队列为空");
        }
        return (T) data[front];
    }

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

    public int size() {
        return size;
    }

    private void ensureCapacity() {
        if (size == data.length - 1) { // 留一个空位区分满和空
            resize();
        }
    }

    private void resize() {
        Object[] newData = new Object[data.length * 2];
        for (int i = 0; i < size; i++) {
            newData[i] = data[(front + i) % data.length];
        }
        data = newData;
        front = 0;
        rear = size;
    }
}

银行叫号系统实现

import java.util.*;

/**
 * 银行客户类
 */
public class BankCustomer {
    public final int id;           // 客户编号
    public final String name;      // 客户姓名
    public final String type;      // 客户类型：VIP / 普通
    public final long arrivalTime; // 到达时间

    public BankCustomer(int id, String name, String type) {
        this.id = id;
        this.name = name;
        this.type = type;
        this.arrivalTime = System.currentTimeMillis();
    }

    @Override
    public String toString() {
        return String.format("[%s客户 #%d] %s", type, id, name);
    }
}

/**
 * 银行叫号系统
 * 使用普通队列管理客户，VIP客户可插队到普通客户前面
 */
public class BankQueueSystem {
    private final ArrayQueue<BankCustomer> vipQueue;
    private final ArrayQueue<BankCustomer> normalQueue;
    private int ticketCounter;
    private int servedCount;

    public BankQueueSystem() {
        this.vipQueue = new ArrayQueue<>();
        this.normalQueue = new ArrayQueue<>();
        this.ticketCounter = 1000;
        this.servedCount = 0;
    }

    /**
     * 客户取号
     */
    public int takeTicket(BankCustomer customer) {
        int ticket = ticketCounter++;
        if ("VIP".equals(customer.type)) {
            vipQueue.enqueue(customer);
            System.out.println(customer + " 取号成功，VIP通道，号码: " + ticket);
        } else {
            normalQueue.enqueue(customer);
            System.out.println(customer + " 取号成功，普通通道，号码: " + ticket);
        }
        return ticket;
    }

    /**
     * 叫号服务
     * VIP队列优先，VIP队列为空时才服务普通客户
     */
    public BankCustomer callNext() {
        BankCustomer customer;
        if (!vipQueue.isEmpty()) {
            customer = vipQueue.dequeue();
            System.out.println("请 " + customer + " 到窗口办理业务");
        } else if (!normalQueue.isEmpty()) {
            customer = normalQueue.dequeue();
            System.out.println("请 " + customer + " 到窗口办理业务");
        } else {
            System.out.println("当前无等待客户");
            return null;
        }
        servedCount++;
        return customer;
    }

    /**
     * 显示当前排队情况
     */
    public void showQueueStatus() {
        System.out.println("\n=== 当前排队情况 ===");
        System.out.println("VIP队列等待人数: " + vipQueue.size());
        System.out.println("普通队列等待人数: " + normalQueue.size());
        System.out.println("今日已服务客户数: " + servedCount);
    }
}

优先级队列实现

/**
 * 基于二叉堆的优先级队列
 * 支持自定义优先级比较
 */
public class PriorityQueue<T> {
    private Object[] heap;
    private int size;
    private final Comparator<? super T> comparator;
    private static final int DEFAULT_CAPACITY = 16;

    public PriorityQueue(Comparator<? super T> comparator) {
        this.heap = new Object[DEFAULT_CAPACITY];
        this.size = 0;
        this.comparator = comparator;
    }

    /**
     * 入队操作
     */
    public void enqueue(T item) {
        ensureCapacity();
        heap[size] = item;
        siftUp(size);
        size++;
    }

    /**
     * 出队操作：返回优先级最高的元素
     */
    @SuppressWarnings("unchecked")
    public T dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException("队列为空");
        }
        T result = (T) heap[0];
        heap[0] = heap[--size];
        heap[size] = null;
        siftDown(0);
        return result;
    }

    @SuppressWarnings("unchecked")
    public T peek() {
        if (isEmpty()) throw new NoSuchElementException("队列为空");
        return (T) heap[0];
    }

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

    public int size() {
        return size;
    }

    // 上浮：将新元素调整到正确位置
    @SuppressWarnings("unchecked")
    private void siftUp(int index) {
        T item = (T) heap[index];
        while (index > 0) {
            int parent = (index - 1) / 2;
            T parentItem = (T) heap[parent];
            if (comparator.compare(item, parentItem) >= 0) break;
            heap[index] = parentItem;
            index = parent;
        }
        heap[index] = item;
    }

    // 下沉：将根元素调整到正确位置
    @SuppressWarnings("unchecked")
    private void siftDown(int index) {
        T item = (T) heap[index];
        int half = size / 2;
        while (index < half) {
            int child = index * 2 + 1;
            T childItem = (T) heap[child];
            int right = child + 1;
            if (right < size && comparator.compare((T) heap[right], childItem) < 0) {
                child = right;
                childItem = (T) heap[child];
            }
            if (comparator.compare(item, childItem) <= 0) break;
            heap[index] = childItem;
            index = child;
        }
        heap[index] = item;
    }

    private void ensureCapacity() {
        if (size == heap.length) {
            heap = Arrays.copyOf(heap, heap.length * 2);
        }
    }
}

任务调度系统

/**
 * 任务类
 */
public class Task {
    public final int id;
    public final String name;
    public final int priority;    // 数字越小优先级越高
    public final int duration;    // 预计执行时间（毫秒）

    public Task(int id, String name, int priority, int duration) {
        this.id = id;
        this.name = name;
        this.priority = priority;
        this.duration = duration;
    }

    @Override
    public String toString() {
        return String.format("[任务#%d] %s (优先级:%d, 预计耗时:%dms)", 
                            id, name, priority, duration);
    }
}

/**
 * 多级反馈队列调度器
 * 模拟操作系统中的进程调度策略
 */
public class TaskScheduler {

    // 高优先级队列（短时间任务）
    private final ArrayQueue<Task> highPriorityQueue;
    // 中优先级队列
    private final ArrayQueue<Task> mediumPriorityQueue;
    // 低优先级队列（长时间任务）
    private final ArrayQueue<Task> lowPriorityQueue;

    public TaskScheduler() {
        this.highPriorityQueue = new ArrayQueue<>();
        this.mediumPriorityQueue = new ArrayQueue<>();
        this.lowPriorityQueue = new ArrayQueue<>();
    }

    /**
     * 提交任务
     */
    public void submit(Task task) {
        if (task.priority <= 2) {
            highPriorityQueue.enqueue(task);
            System.out.println("任务进入高优先级队列: " + task.name);
        } else if (task.priority <= 5) {
            mediumPriorityQueue.enqueue(task);
            System.out.println("任务进入中优先级队列: " + task.name);
        } else {
            lowPriorityQueue.enqueue(task);
            System.out.println("任务进入低优先级队列: " + task.name);
        }
    }

    /**
     * 调度执行：按优先级从高到低处理
     */
    public void run() {
        System.out.println("\n=== 开始任务调度 ===");
        int totalExecuted = 0;

        // 先处理高优先级
        while (!highPriorityQueue.isEmpty()) {
            executeTask(highPriorityQueue.dequeue());
            totalExecuted++;
        }

        // 再处理中优先级
        while (!mediumPriorityQueue.isEmpty()) {
            executeTask(mediumPriorityQueue.dequeue());
            totalExecuted++;
        }

        // 最后处理低优先级
        while (!lowPriorityQueue.isEmpty()) {
            executeTask(lowPriorityQueue.dequeue());
            totalExecuted++;
        }

        System.out.println("\n调度完成，共执行 " + totalExecuted + " 个任务");
    }

    private void executeTask(Task task) {
        System.out.println("执行 " + task);
        try {
            Thread.sleep(Math.min(task.duration, 100)); // 模拟执行
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
    }
}

主程序与测试

public class QueueMain {
    public static void main(String[] args) {
        // 测试银行叫号系统
        System.out.println("=== 银行叫号系统测试 ===\n");
        BankQueueSystem bank = new BankQueueSystem();

        bank.takeTicket(new BankCustomer(1, "张三", "普通"));
        bank.takeTicket(new BankCustomer(2, "李四", "VIP"));
        bank.takeTicket(new BankCustomer(3, "王五", "普通"));
        bank.takeTicket(new BankCustomer(4, "赵六", "VIP"));
        bank.takeTicket(new BankCustomer(5, "孙七", "普通"));

        bank.showQueueStatus();

        bank.callNext();
        bank.callNext();
        bank.callNext();
        bank.showQueueStatus();

        // 测试优先级队列
        System.out.println("\n=== 优先级队列测试 ===");
        PriorityQueue<Task> pq = new PriorityQueue<>(Comparator.comparingInt(t -> t.priority));
        pq.enqueue(new Task(1, "数据备份", 5, 2000));
        pq.enqueue(new Task(2, "用户请求", 1, 100));
        pq.enqueue(new Task(3, "日志清理", 8, 500));
        pq.enqueue(new Task(4, "报警处理", 1, 50));
        pq.enqueue(new Task(5, "报表生成", 3, 1000));

        while (!pq.isEmpty()) {
            System.out.println("处理: " + pq.dequeue());
        }

        // 测试任务调度器
        System.out.println("\n=== 多级反馈队列调度 ===");
        TaskScheduler scheduler = new TaskScheduler();
        scheduler.submit(new Task(1, "紧急修复", 1, 500));
        scheduler.submit(new Task(2, "日常巡检", 6, 3000));
        scheduler.submit(new Task(3, "接口优化", 3, 1500));
        scheduler.submit(new Task(4, "安全补丁", 1, 800));
        scheduler.submit(new Task(5, "数据归档", 8, 5000));
        scheduler.run();
    }
}

复杂度分析

总结

队列的FIFO特性天然适合模拟排队和顺序处理场景。循环队列通过头尾指针优化了数组队列的空间利用率；优先级队列（堆）则允许按优先级而非到达顺序处理元素，广泛应用于任务调度、Dijkstra算法、哈夫曼编码等场景。理解队列的不同变体，有助于在实际问题中选择最合适的实现方案。