Create custom Queue container

Hello everyone,

I’m currently want to implement a sorted queue, so everytime a new item enters it is sorted by some kind of priority value.

So what I’ve got in mind is create a linked list with “Node structure” such as:

template <class StoredType>
class SortedQueue
public :
]struct Node
   StoredType Data;
   Node * Next;
   Node() : Next(nullptr), Previous(nullptr) {}

Node * Head;

My question comes when a new item is entered, I need to create a node, there is anyway to avoid heap allocation (new Node()) or, if there isn’t, how bad is using in it?

Thanks in advance