优先队列（PriorityQueue）

> 此代码是在最大堆的基础上二次封装，请先阅读底层代码MaxHeap

优先队列

• 普通队列：先进先出；后进后出
• 优先队列：出队顺序和⼊入队顺序无关；和优先级相关；

为什么使用堆

代码清单

Queue.h

代码语言：javascript复制

//
// Created by cheng on 2021/7/11.
//

#ifndef MAXHEAP_QUEUE_H
#define MAXHEAP_QUEUE_H

template<typename T>
class Queue {
public:
    virtual int getSize() = 0;

    virtual bool isEmpty() = 0;

    virtual void enqueue(const T &e) = 0;

    virtual T dequeue() = 0;

    virtual T getFront() = 0;
};

#endif //MAXHEAP_QUEUE_H

PriorityQueue.h

代码语言：javascript复制

//
// Created by cheng on 2021/7/11.
//

#ifndef MAXHEAP_PRIORITYQUEUE_H
#define MAXHEAP_PRIORITYQUEUE_H

#include "MaxHeap.h"
#include "Queue.h"

template<typename T>
class PriorityQueue : public Queue<T> {

private:
    MaxHeap<T> *maxHeap;

public:
    PriorityQueue() {
        maxHeap = new MaxHeap<T>();
    }

    constexpr int getSize() {
        return maxHeap->getSize();
    }

    constexpr bool isEmpty() {
        return maxHeap->isEmpty();
    }

    void enqueue(const T &e) {
        maxHeap->add(e);
    }

    T dequeue() {
        return maxHeap->extractMax();
    }

    T getFront() {
        return maxHeap->findMax();
    }

    ~PriorityQueue() {
        delete maxHeap;
        maxHeap = nullptr;
    }

    void print() {
        std::cout << "Queue: size = " << maxHeap->getSize() << std::endl;
        std::cout << "front ";
        maxHeap->print();
        std::cout << " tail" << std::endl;
    }
};

#endif //MAXHEAP_PRIORITYQUEUE_H

queue 队列 基础

0 人点赞