链表实现优先级队列C++

优先级队列可以使用数组，堆..........实现，也可以使用链表实现。

代码：

//堆是堆，优先级队列是优先级队列，后者可以用前者实现，也可以使用链表或者数组等数据结构实现。后者的核心是优先而不是队列，一定要分清楚。
#include<iostream>
#include<stdexcept>
class PriorityQueue{
public:
  PriorityQueue():head(nullptr){
    std::cout << "PriorityQueue()" << std::endl;
  }
  ~PriorityQueue(){
    while(!Empty()){
      Pop();
    }
    std::cout << "~Priority()" << std::endl;
  }
  bool Empty(){
    return !head;
  }
  void Push(int val){
    Node *p = new Node(val);
    if(!head||val>head->val){
      p->next = head;
      head = p;
    }
    else{
      Node *a = head;
      Node *b = head->next;
      while(b){
        if(b->val<p->val){
          p->next = b;
          a->next = p;
          break;
        }
        else{
          a = b;
          b = b->next;
        }
      }
    }
  }
  int Pop(){
    if(!head){
      throw std::runtime_error("Cannot Pop from empty PriorityQueue\n");
    }
    int val = head->val;
    Node* cur = head;
    head = head->next;
    delete cur;
    cur = nullptr;
    return val;
  }
  int Top(){
    if(!head){
      throw std::runtime_error("Cannot get top() from empty PriorityQueue\n");
    }
    return head->val;
  }
private:
  struct Node // 结构体和类可以嵌套定义，你也可以放在类外，写一个typedef{}Node;即可
  {
    Node *next;
    int val;
    Node(int value) : val(value), next(nullptr) {}
  };
  Node *head; // Node head is error
};
int main(){
  PriorityQueue q;
  q.Push(1);
  q.Push(5);
  q.Push(2);
  q.Push(-1);
  q.Push(10);
  q.Push(3);
  q.Push(7);
  std::cout << "Push done\n";
  while(!q.Empty()){
    std::cout << q.Pop() << ' ';
  }
  std::cout << std::endl;
  return 0;
}

我们将Node封装了类内，也可以放在类外，只需要加一个typedef即可。放在类内有一个好处：加强代码可读性，这个Node就是为我们优先级队列使用的。

你实例化PriorityQueue对象，并不会 实例化一个Node对象，我们的构造函数中并没有对Node初始化。只有在调用Push操作时候会实例化Node。

编译选项：

g++ PriorityQueue.cc  -std=c++11 

结果：

PriorityQueue()
Push done
10 7 5 3 2 1 
~Priority() 

原文地址：https://blog.csdn.net/kitesxian/article/details/143934602

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！