I have written this code for Priority Queue using Singly Linked List. I want to improve this code. Is there any other method to write program for priority queue?
#include <iostream>
template<typename T>
class priorityQueue
{
struct Node
{
int priority;
T info;
Node* next;
Node(T item) : info(item), next(nullptr) {}
};
Node* front;
public:
priorityQueue() : front(nullptr) {}
~priorityQueue()
{
Node *tmp = nullptr;
while (front){
tmp = front;
front = front->next;
delete tmp;
}
front = nullptr;
}
priorityQueue(const priorityQueue<T> & pq) = delete;
priorityQueue& operator=(priorityQueue const&) = delete;
void insert(T item, int priority)
{
Node* tmp;
Node* node = new Node(item);
node->priority = priority;
if(front == nullptr || priority < front->priority)
{
node->next = front;
front = node;
}
else
{
tmp = front;
while(tmp->next != nullptr && tmp->next->priority <= priority)
tmp = tmp->next;
node->next = tmp->next;
tmp->next = node;
}
}
void deleteItem(T item)
{
Node* find = search(item);
Node* node = front;
if(node == find)
front = node->next;
else
{
while(find != nullptr)
{
if(node->next == find)
{
node->next = find->next;
delete find;
return;
}
node = node->next;
}
}
}
friend std::ostream & operator<<(std::ostream & os, const priorityQueue<T> & pq)
{
pq.display(os);
return os;
}
private:
Node *search(T item)
{
Node *node = front;
while(node != nullptr)
{
if(node->info == item)
return node;
node = node->next;
}
std::cerr << "No such element in the list \n";
return nullptr;
}
void display(std::ostream& out = std::cout) const
{
Node *node = front;
out << "\nItem \tPriority \n";
while(node != nullptr)
{
out << node->info << "\t" << node->priority <<"\n";
node = node->next;
}
}
};
int main()
{
priorityQueue<std::string> pq1;
pq1.insert("code", 1);
pq1.insert("sleep", 3);
pq1.insert("food", 2);
pq1.insert("date", 4);
std::cout << pq1;
}
2 Answers 2
Data structures
Although the name "priority queue" is technically correct, I find it a bit misleading, because priority queues are usually implemented using a heap data structure, with insert and find operations in \$O(\log n)\$ time. Your implementation is practically a sorted linked list, with insert and find operations in \$O(n)\$ time. I'd clarify as "naive priority queue" to avoid confusion.
Memory leak
Watch out for memory leaks.
When deleting the first item,
the deleteItem
function simply advances the pointer of front
,
without actually deleting the item,
leaving allocated memory behind.
Performance
deleteItem
is inefficient,
because it iterates to the node to delete twice:
once to find the node to delete,
and then one more time to actually delete it.
-
\$\begingroup\$ The name is correct. It is still a priority queue. Albeit a slow one. \$\endgroup\$Emily L.– Emily L.2017年09月02日 11:26:38 +00:00Commented Sep 2, 2017 at 11:26
Pass by Reference
Be more conscious of passing by value and passing by reference, all your functions take objects of type T
as value parameters, in most cases that should be const T&
. Otherwise you will end up making a copy for every function call and the Node constructor.
API
There are no functions to get and/or remove the first item in the list. If this is supposed to be a priority queue i would at least want to be able to retrieve or pop the first item in the list.
Every item is uniquely identified by itself and the priority, but deletion only uses the item as an identifier, if I add two items e.g.
queue.add("sleep", 1);
queue.add("sleep", 3);
You would only be able to delete the first item
You have insert
but deleteItem
, using Item
in the member function name is unnecessary.
Bad constructor
priority
is not initialized in the constructor, if you forget to assign it, it will be uninitialized. Additionally it takes T in its constructor but the priority has to be set "manually" this is not a good pattern, if you pass it in the constructor your constructor indicates that both of these items are necessary to make a valid Node
object.
Blocks without braces
This borders into taste issues, i personally try not to use blocks without braces e.g.
if (value)
return true;
It is too easy to forget that this block is not extended by just keeping the indentation and just add another line to this 'block'. This can lead to bugs that are hard to find
if (value)
othervalue = 5;
return true;
This comes into play once you have code that has been sitting around for a bit, I prefer either just using the braces for everything (a lot of code styling tools will do this substitution for you anyway), or only using this if the whole statement fits in one line.
if (value) {
return true;
}
if (value) return true;