手把手教数据结构与算法：优先级队列（银行排队问题）

引言

数据结构是计算机科学的基础，而队列则是其中非常基础和重要的数据结构之一。队列遵循先进先出（First-In-First-Out, FIFO）的原则，是一种线性的数据结构。然而，在实际应用中，我们经常会遇到一些需要根据元素的优先级来决定元素进出顺序的场景，这时就需要用到优先级队列。本文将以银行排队问题为例，详细介绍优先级队列的概念、实现和应用。

队列的基本概念

队列的定义

队列是一种先进先出的数据结构，只允许在一端进行插入，另一端进行删除。在队列中，元素按照进入队列的顺序排列。

队首（Front）和队尾（Rear）

队首是队列中最先进入的元素，可以被访问或移除；队尾是队列中最后进入的元素，不允许进行访问和删除。

空队列

不含任何元素的队列称为空队列。

队列的特点

队列是一种先进先出的数据类型。每次元素的入队都只能添加到队列尾部，出队时从队列头部开始出。

优先级队列

优先级队列的定义

优先级队列是一种特殊的队列，元素的进出顺序不是按照先进先出的原则，而是根据元素的优先级来决定。

优先级队列的特点

在优先级队列中，元素按照优先级高低排列。每次出队操作，都会将当前队列中优先级最高的元素出队。

银行排队问题

银行排队问题是一个典型的优先级队列应用场景。在银行排队问题中，每个顾客都有一个优先级，通常是根据到达时间或者业务类型来确定的。我们需要根据顾客的优先级来安排他们办理业务，以优化顾客的等待时间。

优先级队列的实现

下面我们将使用C++泛型编程来实现一个优先级队列。首先定义一个节点类，用于表示队列中的元素：

template <typename T>
struct Node {
    T data;
    int priority;
    Node(T data, int priority) : data(data), priority(priority) {}
};

然后定义一个自定义队列类：

template <typename T>
class Queue {
private:
    Node<T>* arr;
    int front, rear, size, capacity;

public:
    Queue(int capacity);
    ~Queue();
    bool isEmpty();
    bool isFull();
    void enqueue(T data, int priority);
    T dequeue();
    T front();
    int size();
};

最后，我们实现优先级队列类：

template <typename T>
class PriorityQueue : public Queue<T> {
public:
    PriorityQueue(int capacity) : Queue<T>(capacity) {}
    void enqueue(T data, int priority);
    T dequeue();
};

在优先级队列中，我们需要对元素进行排序，以确保每次出队操作都能得到当前队列中优先级最高的元素。这通常可以通过二叉堆来实现。

总结

本文介绍了数据结构中的队列及其基本概念和特性，特别强调了优先级队列与普通队列的不同。通过银行排队问题的实例，我们了解了优先级队列在实际应用中的重要性。最后，我们给出了使用C++泛型编程实现的队列和优先级队列的代码示例，包括节点类、自定义队列类和优先级队列类。

希望这篇文章能帮助你更好地理解优先级队列的概念和应用。

---