优先队列(PriorityQueue)

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

优先队列

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

为什么使用堆

优先队列(PriorityQueue)

代码清单

Queue.h

//
// 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

//
// 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
上一篇:LNK2001 无法解析的外部符号 "public: virtual struct QMetaObject


下一篇:设计模式系列(大话设计模式c++版)——观察者模式