要实现一个带有优先级的队列（不一定先进先出），可以使用优先队列（Priority Queue）这种数据结构。优先队列会根据元素的优先级决定出队顺序，优先级高的元素先出队，而不是按照入队的先后顺序。

优先队列的实现方式

在 C++ 中，优先队列通常有两种实现方式：

1. 基于堆（Heap）：这是最常见的实现方式，使用二叉堆（通常是最大堆或最小堆）来维护元素的优先级。插入和删除操作的时间复杂度都是 O (log n)。
2. 基于有序列表：元素在插入时就按照优先级排序，出队操作的时间复杂度为 O (1)，但插入操作的时间复杂度为 O (n)。

C++ 标准库中的优先队列

C++ 标准库提供了std::priority_queue，它默认基于最大堆实现：

cpp

#include <iostream>
#include <queue>

int main() {
    // 创建一个存储整数的优先队列，默认按降序排列（大顶堆）
    std::priority_queue<int> pq;

    // 插入元素（自动按优先级排序）
    pq.push(30);
    pq.push(10);
    pq.push(20);

    // 依次取出元素（优先级高的先出队）
    while (!pq.empty()) {
        std::cout << pq.top() << " ";  // 输出：30 20 10
        pq.pop();
    }
    std::cout << std::endl;

    // 使用自定义比较函数，实现小顶堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    minHeap.push(30);
    minHeap.push(10);
    minHeap.push(20);

    while (!minHeap.empty()) {
        std::cout << minHeap.top() << " ";  // 输出：10 20 30
        minHeap.pop();
    }
    std::cout << std::endl;

    return 0;
}

自定义优先级队列示例

如果需要自定义元素类型和优先级规则，可以这样实现：

cpp

#include <iostream>
#include <queue>
#include <string>

// 定义一个任务结构体，包含任务ID和优先级
struct Task {
    int id;
    int priority;

    // 构造函数
    Task(int _id, int _priority) : id(_id), priority(_priority) {}

    // 重载小于运算符，用于优先级比较
    bool operator<(const Task& other) const {
        // 优先级高的任务排在前面（大顶堆）
        return priority < other.priority;
    }
};

int main() {
    // 创建一个存储Task的优先队列
    std::priority_queue<Task> taskQueue;

    // 添加任务
    taskQueue.push(Task(1, 2));  // ID=1，优先级=2
    taskQueue.push(Task(2, 5));  // ID=2，优先级=5
    taskQueue.push(Task(3, 1));  // ID=3，优先级=1

    // 按优先级处理任务
    while (!taskQueue.empty()) {
        Task current = taskQueue.top();
        std::cout << "Processing Task ID: " << current.id 
                  << ", Priority: " << current.priority << std::endl;
        taskQueue.pop();
    }

    return 0;
}

输出结果：

plaintext

Processing Task ID: 2, Priority: 5
Processing Task ID: 1, Priority: 2
Processing Task ID: 3, Priority: 1

手动实现基于堆的优先队列

如果需要更底层的实现，可以手动实现一个基于堆的优先队列：

cpp

#include <iostream>
#include <vector>
#include <algorithm>

template<typename T>
class PriorityQueue {
private:
    std::vector<T> heap;

    // 上浮操作，维护堆的性质
    void siftUp(int index) {
        while (index > 0) {
            int parent = (index - 1) / 2;
            if (heap[parent] < heap[index]) {
                std::swap(heap[parent], heap[index]);
                index = parent;
            } else {
                break;
            }
        }
    }

    // 下沉操作，维护堆的性质
    void siftDown(int index) {
        int size = heap.size();
        while (true) {
            int leftChild = 2 * index + 1;
            int rightChild = 2 * index + 2;
            int largest = index;

            if (leftChild < size && heap[leftChild] > heap[largest]) {
                largest = leftChild;
            }

            if (rightChild < size && heap[rightChild] > heap[largest]) {
                largest = rightChild;
            }

            if (largest != index) {
                std::swap(heap[index], heap[largest]);
                index = largest;
            } else {
                break;
            }
        }
    }

public:
    // 判断队列是否为空
    bool empty() const {
        return heap.empty();
    }

    // 返回队列大小
    size_t size() const {
        return heap.size();
    }

    // 插入元素
    void push(const T& value) {
        heap.push_back(value);
        siftUp(heap.size() - 1);
    }

    // 返回优先级最高的元素
    const T& top() const {
        if (empty()) {
            throw std::out_of_range("Priority queue is empty");
        }
        return heap[0];
    }

    // 删除优先级最高的元素
    void pop() {
        if (empty()) {
            throw std::out_of_range("Priority queue is empty");
        }
        std::swap(heap[0], heap.back());
        heap.pop_back();
        siftDown(0);
    }
};

int main() {
    PriorityQueue<int> pq;
    pq.push(30);
    pq.push(10);
    pq.push(20);

    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }
    std::cout << std::endl;

    return 0;
}

应用场景

优先队列适用于以下场景：

1. 任务调度：根据任务的优先级决定执行顺序。
2. 图算法：如 Dijkstra 最短路径算法中，需要不断取出距离最小的节点。
3. 事件模拟：按照事件发生的时间顺序处理事件。
4. 数据压缩：如 Huffman 编码中，需要频繁取出频率最小的节点。

通过使用优先队列，你可以轻松实现一个不依赖先进先出顺序，而是根据元素优先级进行操作的队列。