Need help with implementing this in C++. Priority Queue. Linked List. Here is my
ID: 3551232 • Letter: N
Question
Need help with implementing this in C++. Priority Queue. Linked List. Here is my code below. Make sure all the functions output correctly. I need the insert function to add a node and sort also. I believe everything is correct but the insert function.
#include<iostream>
using namespace std;
//our node
struct node
{
node * next;
int d;
};
//head and tail pointers
node * head = 0;
node * tail = 0;
void insert(int);
int dq(void);
int peek(void);
bool isEmpty(void);
void display(void);
void main()
{
insert(11);
insert(4);
insert(13);
display();
cout << "Removed: " << dq() << endl;
display();
peek();
cout << "Removed: " << dq() << endl;
display();
peek();
cout << "Removed: " << dq() << endl;
display();
cout << "Removed: " << dq() << endl;
cout << isEmpty() << endl;
}
//traverses the list from head to tail, prints each char element.
void display(void)
{
node*p=head;
cout << "The queue contains: ";
while(p)
{
cout << (int)p->d<< " ";
p=p->next;
}
cout << endl;
}
//insert data and sort in order
void insert(int y)
{
//Insert and sort in order
}
int peek(void)
{
if(!head)
{
return -1;
}
else
{
cout<< "The head is: ";
return head->d;
}
}
int dq(void)
{
node * p;
int temp;
//return if list is empty
if(!head)
return -1;
//only one node?
if(head==tail)
{
//remove and destroy head node
temp = head->d;
delete head;
head = tail = 0;
return temp;
}
//more than one node
//remove and destroy head node
p = head;
head = head->next;
temp = p->d;
delete p;
return temp;
}
bool isEmpty(void)
{
if(!head)
{
cout << "Is empty: ";
return true;
}
else
{
cout << "Is not empty: ";
return false;
}
}
Explanation / Answer
// rewrite with char
#include<iostream>
using namespace std;
//our node
struct node
{
node * next;
char d;
};
//head and tail pointers
node * head = 0;
node * tail = 0;
void insert(char);
char dq(void);
char peek(void);
bool isEmpty(void);
void display(void);
void main()
{
insert('B');
insert('A');
insert('C');
insert('D');
display();
cout << "Removed: " << dq() << endl;
display();
peek();
cout << "Removed: " << dq() << endl;
display();
peek();
cout << "Removed: " << dq() << endl;
display();
cout << "Removed: " << dq() << endl;
cout << isEmpty() << endl;
}
//traverses the list from head to tail, prints each char element.
void display(void)
{
node*p=head;
cout << "The queue contains: ";
while(p)
{
cout << p->d<< " ";
p=p->next;
}
cout << endl;
}
//insert data and sort in order
void insert(char y)
{
//Insert and sort in order
node*p = new node();
p->d = y;
p->next = 0;
node*cur = head;
node*prev = 0;
while (cur != 0 && cur->d < y)
{
prev = cur;
cur = cur->next;
}
p->next = cur;
if (prev)
prev->next = p;
else
head = p;
if (p->next == 0)
tail = p;
}
char peek(void)
{
if(!head)
{
return 0;
}
else
{
cout<< "The head is: ";
return head->d;
}
}
char dq(void)
{
node * p;
char temp;
//return if list is empty
if(!head)
return 0;
//only one node?
if(head==tail)
{
//remove and destroy head node
temp = head->d;
delete head;
head = tail = 0;
return temp;
}
//more than one node
//remove and destroy head node
p = head;
head = head->next;
temp = p->d;
delete p;
return temp;
}
bool isEmpty(void)
{
if(!head)
{
cout << "Is empty: ";
return true;
}
else
{
cout << "Is not empty: ";
return false;
}
}