Learn C++ Online

This lesson contains approximately 25 minutes of video content.

Motivation

Class templates

Class templates and separate compilation

Additional Practice

Priority queue

Drop your src and includes folders, the whole project folder, or individual files here, or click to choose files.

In this problem, you will implement the class template PriorityQueue. Any type used to instantiate your class template will implement the comparison operators (==, !=, <, >, <=, >=). Our priority queue will maintain a singly linked list of Node<T> typed objects. In your workspace, you can find the definition of Node<T> in includes/node.hpp. The behaviors and data members of PriorityQueue follow:

PriorityQueue Member Functions

public:
`PriorityQueue()`	Default constructor: `head_` is initalized to the nullptr.
`PriorityQueue(const PriorityQueue<T>& rhs) = delete;`	Since we have defined a destructor for this type, we must define this function too (per the rule of three). However, we do not need it in this problem. Therefore, you should `= delete` this function to ensure that the compiler does not generate a definition of it for you.
`PriorityQueue<T>& operator=(const PriorityQueue<T>& rhs) = delete;`	Since we have defined a destructor for this type, we must define this function too (per the rule of three). However, we do not need it in this problem. Therefore, you should `= delete` this function to ensure that the compiler does not generate a definition of it for you.
`~PriorityQueue()`	Destructor: frees all dynamcially allocated objects comprising the singly linked list.
`void Enqueue(const T& data);`	Inserts a `Node<T>` storing `data` into the singly linked list in ascending order.
`T Dequeue();`	Returns a copy of the data stored in the node pointed to by `head_`, frees the memory associated with that node object, and updates `head_` to point to the next node in the sequence. If the list is empty, an exception should be thrown.

PriorityQueue Data members

private:
`Node<T>* head_`

Graded Files

Only the following files are transferred to the autograder.

solution.hpp
solution.cc

#include "solution.hpp" int main() {}

#ifndef SOLUTION_HPP #define SOLUTION_HPP #endif

#include "solution.hpp"

#ifndef NODE_HPP #define NODE_HPP // DO NOT MODIFY THIS FILE: OUR GRADER USES THE ORIGINAL NODE.HPP PROVIDED TO YOU. // WE DO NOT COPY THIS FILE FROM YOUR WORKSPACE TO OUR AUTO-GRADER. template <typename T> struct Node { T data; // NOLINT Node<T>* next; // NOLINT Node(T data) : data(data), next(nullptr) {} // NOLINT Node(T data, Node<T>* next) : data(data), next(next) {} // NOLINT }; #endif

Program input (stdin)

> Click Run to compile and run your code.