list.h

#ifndef LINKED_LIST_LIST_H_
#define LINKED_LIST_LIST_H_

#include <stdexcept>
#include <ostream>

using namespace std;

template<class T>
class Node {
 public:
  Node();
  Node(const T&, Node *, Node *);
  T data_;
  Node *next_;
  Node *previous_;
};

template<class T>
inline Node<T>::Node()
{
  this->next_ = 0;
  this->previous_ = 0;
  this->data_ = NULL;
}

template<class T>
inline Node<T>::Node(const T &element, Node *next, Node *previous) {
  this->data_ = element;
  this->next_ = next;
  this->previous_ = previous;
}

template<class T>
class List {
 private:
  int size_;

 public:
  List();
  ~List();
  bool IsEmpty() const;
  int size() const;
  void AddToFront(const T&);
  void AddToEnd(const T&);
  void AddBeforeNode(const T&, Node<T> *);
  T DeleteFromFront();
  Node<T>* PeekHead();

  Node<T> *head_;
  Node<T> *tail_;
 protected:
  friend ostream& operator<<(ostream& out, const List<T>& list) {
    Node<T> *temp = list.head_;
    while (temp != nullptr) {
      out << temp->data_ << ' ';
      temp = temp->next_;
    }
    return out;
  }
};

template<class T>
inline List<T>::List() {
  this->size_ = 0;
  this->head_ = nullptr;
  this->tail_ = nullptr;
}

template<class T>
inline List<T>::~List() {
  Node<T> *temp;
  while (this->head_ != nullptr) {
    temp = this->head_;
    this->head_ = this->head_->next_;
    delete temp;
  }
  this->size_ = 0;
}

template<class T>
inline bool List<T>::IsEmpty() const {
  return this->size() == 0;
}

template<class T>
inline int List<T>::size() const {
  return this->size_;
}

template<class T>
void List<T>::AddToFront(const T &element) {
  if (this->IsEmpty()) {
    this->head_ = this->tail_ = new Node<T>(element, nullptr, nullptr);
  } else {
    // step 1 and 2!
    this->head_ = new Node<T>(element, this->head_, nullptr);
    // step 3 (remove the nullptr from the old head.
    this->head_->next_->previous_ = this->head_;
  }

  this->size_++;
}

template<class T>
inline void List<T>::AddToEnd(const T &element) {
  if (this->IsEmpty()) {
    this->tail_ = this->head_ = new Node<T>(element, nullptr, nullptr);
  } else {
    this->tail_ = new Node<T>(element, nullptr, this->tail_);
    this->tail_->previous_->next_ = this->tail_;
  }

  this->size_++;
}

template<class T>
inline T List<T>::DeleteFromFront() {
  if (!this->IsEmpty()) {
    T data = this->head_->data_;
    if (this->size() == 1) {
      // head and tail are the same.
      delete this->head_;
      this->head_ = this->tail_ = nullptr;
    } else {
      // we must have more than 1 element.
      this->head_ = this->head_->next_;
      delete this->head_->previous_;
      this->head_->previous_ = nullptr;
    }

    this->size_--;
    return data;
  } // else, Empty list DoNothing();

  throw std::out_of_range("List is empty!");

}

template<class T>
inline Node<T>* List<T>::PeekHead() {
  if (!this->IsEmpty()) {
    return this->head_;
  } // else, the list is empty DoNothing();

  throw std::out_of_range("List is empty!");
}

template<class T>
void List<T>::AddBeforeNode(const T &element, Node<T> *node) {
  if (node != nullptr) {
    auto *new_node = new Node<T>(element, node, node->previous_);

    // Need to update the head, since this is a new head node.
    if (node->previous_ == nullptr) {
      node->previous_ = new_node;
      this->head_ = new_node;
    } else {
      // else, it's just a regular node and we update both node links.
      node->previous_->next_ = new_node;
      node->previous_ = new_node;
    }
    this->size_++;
  } else {
    throw std::out_of_range("Can't add a node before a non-existent Node.");
  }
}

#endif

priority_queue.h

#ifndef LINKED_LIST_QUEUE_H_
#define LINKED_LIST_QUEUE_H_

#include <stdexcept>

#include "list.h"

template<typename T>
class PriorityQueue {
 private:
  List<T> *data_;
 public:
  PriorityQueue();
  ~PriorityQueue();
  bool IsEmpty();
  void Enqueue(const T&);
  T Dequeue();
  T Front();
};

template<typename T>
inline PriorityQueue<T>::PriorityQueue() {
  this->data_ = new List<T>;
}

template<typename T>
inline PriorityQueue<T>::~PriorityQueue() {
  delete this->data_;
}

template<typename T>
inline bool PriorityQueue<T>::IsEmpty() {
  return this->data_->IsEmpty();
}

template<typename T>
inline void PriorityQueue<T>::Enqueue(const T &element) {
  if (this->data_->IsEmpty()) {
    this->data_->AddToEnd(element);
  } else {
    Node<T> *node = this->data_->PeekHead();
    // Iterate through each of the elements in the Queue
    while (node != nullptr) {
      // Only consider adding an element if it doesn't exist.
      if (node->data_ != element) {
        if (element < node->data_) {
          this->data_->AddBeforeNode(element, node);
          return;
        }
      } else return; // the element already exists in the PriorityQueue, StopLoop();
      node = node->next_;
    }
  }
}

template<typename T>
inline T PriorityQueue<T>::Dequeue() {
  if (!this->IsEmpty()) {
    return this->data_->DeleteFromFront();
  } // else, the queue is empty, DoNothing();

  throw std::out_of_range("PriorityQueue is empty");
}

template<typename T>
inline T PriorityQueue<T>::Front() {
  if (!this->IsEmpty()) {
    return this->data_->PeekHead();
  } // else, the queue is empty, DoNothing();

  throw std::out_of_range("PriorityQueue is empty");
}

#endif