I am new to data structures and have been trying to implement the below code but can't get it to work. I don't fully understand what I am doing so need some help, I am creating a priority queue using linked list and classes. The takes age as input and displays all age values in descending order. Here is the code.
#include <iostream>
using namespace std;
class Node
{
private:
int age;
Node* next;
public:
int getAge() {
return this->age;
}
void setAge(int age) {
this->age = age;
}
Node* getNext() {
return this->next;
}
Node* setNext(Node* next) {
this->next = next;
}
};
class Priority_Queue
{
private:
Node* front;
Node* rear;
public:
Priority_Queue()
{
front = NULL;
rear = NULL;
}
void enqueue(int x)
{
if (front == NULL && rear == NULL) {
Node* newNode = new Node();
newNode->setAge(x);
newNode->setNext(NULL);
}
else if (front != NULL && front->getAge() < x) {
Node* newNode = new Node();
newNode->setAge(x);
newNode->setNext(rear);
front = newNode;
}
else if (front != NULL && front->getAge() > x) {
Node* newNode = new Node();
newNode->setAge(x);
newNode->setNext(NULL);
rear = newNode;
}
}
void dequeue()
{
if (front == NULL)
cout << "Can't remove from an empty queue!" << endl;
else{
int x = front->getAge();
Node* p = front;
front = front->getNext();
delete p;
cout << "Deleted Age is " << x << endl;
}
}
void display()
{
Node* ptr;
ptr = rear;
if (front == NULL)
cout << "Queue is empty\n";
else
{
cout << "Queue is :\n";
while (ptr != NULL)
{
cout << ptr->getAge() << endl;
ptr = ptr->getNext();
}
}
}
};
int main()
{
int c, p;
Priority_Queue pq;
cout << "\nWelcome to Patient information system" << endl;
cout << "\Enter Your choice of the activity" << endl;
do
{
cout << "1.Insert\n";
cout << "2.Delete\n";
cout << "3.Display\n";
cout << "4.Exit\n";
cout << "Enter your choice : ";
cin >> c;
switch (c)
{
case 1:
cout << "Input the age value to be added in the queue : ";
cin >> p;
pq.enqueue(p);
break;
case 2:
pq.dequeue();
break;
case 3:
pq.display();
break;
case 4:
break;
default:
cout << "Wrong choice\n";
}
} while (c != 4);
cout << endl;
return 0;
}
CodePudding user response：
Here's a quick code review:
#include <iostream>
using namespace std; // Bad practice; especially in a multi-file project which
// this should be.
// The Node should be an "implementation detail." I care about the queue, not
// the plumbing that makes it work.
class Node {
private:
int age;
Node* next; // A sorted queue using only a singly linked list seems like a
// bad idea.
public:
// Use of this is not needed; it can hurt readability
int getAge() { return this->age; }
void setAge(int age) { this->age = age; }
Node* getNext() { return this->next; }
// Return should be void; you don't return anything
Node* setNext(Node* next) { this->next = next; }
};
class Priority_Queue {
private:
Node* front;
Node* rear;
public:
Priority_Queue() {
front =
NULL; // Prefer default member initialization, then default this ctor
rear = NULL; // Prefer nullptr over NULL, it's been around for a decade now
}
/*
* SUPER BAD: No destructor, copy constructor, or assignment operator
* overload. This class manages heap-allocated resources, and no care is taken
* to ensure that proper copies are made, or that the object is properly
* destroyed.
*
* This is known as the Rule of 3, but has recently been called the Rule of
* 0/3/5. Ideally, you would be adhering to the Rule of 5.
*/
void enqueue(int x) {
if (front == NULL && rear == NULL) { // Unnecessarily redundant
Node* newNode = new Node(); // Why not provide a constructor for this?
newNode->setAge(x);
newNode->setNext(NULL);
}
else if (front != NULL &&
front->getAge() < x) { // Pointers can be directly checked
Node* newNode = new Node();
newNode->setAge(x);
newNode->setNext(rear);
front = newNode;
}
else if (front != NULL && front->getAge() > x) {
Node* newNode = new Node();
newNode->setAge(x);
newNode->setNext(NULL);
rear = newNode;
}
}
void dequeue() {
if (front == NULL)
cout << "Can't remove from an empty queue!"
<< endl; // Do nothing, no need for a message
else {
int x = front->getAge();
Node* p = front;
front = front->getNext();
delete p;
cout << "Deleted Age is " << x
<< endl; // Printing in general is a bad idea from within a data
// structure
}
}
void display() {
Node* ptr;
ptr = rear; // Starting at end of list for printing
if (front == NULL)
cout << "Queue is empty\n";
else {
cout << "Queue is :\n";
while (ptr != NULL) {
cout << ptr->getAge() << endl;
ptr = ptr->getNext();
}
}
}
};
As far as student code goes, this is not bad. When it comes to the sorting, we won't bother actually moving nodes around; it's unnecessary given the layout of your Node class.
The first thing I'm going to do is split this into multiple files. It actually makes the writing a bit easier. The first file is our priority queue header.
PriorityQueue.hpp
#ifndef PQUEUE_HPP
#define PQUEUE_HPP
class Priority_Queue {
private:
struct Node; // Prevents Nodes from being declared outside of this class
Node* front = nullptr;
Node* rear = nullptr;
// Helper functions
void sort();
void push_front(int x); // Very simple with singly linked list
friend void swap(Priority_Queue& lhs, Priority_Queue& rhs);
public:
Priority_Queue() = default;
// Only going for Rule of 3 for brevity
Priority_Queue(const Priority_Queue& other);
~Priority_Queue();
Priority_Queue& operator=(Priority_Queue other);
void enqueue(int x);
void dequeue();
void display();
};
// Now that we're nested, a struct can be used instead
// Will make things a lot easier
struct Priority_Queue::Node {
int age = 0;
Node* next = nullptr;
Node() = default;
Node(int a);
Node(int a, Node* n);
};
#endif
This declares the classes and the functions they contain. The biggest single change is that Node is now a struct and is declared privately in Priority_Queue. I should not be able to see, let alone declare Nodes outside of the class. They are what's known as an implementation detail. They help us write the class, but have no business being visible.
Making Node a struct also allowed us to delete all of the member functions. We'll let the class manipulate the data directly.
PriorityQueue.cpp
#include "PriorityQueue.hpp"
#include <algorithm>
#include <iostream>
// This is sloppy, but time contraints won't allow me to make this nicer.
Priority_Queue::Priority_Queue(const Priority_Queue& other) {
Node* otherNode = other.front;
while (otherNode) {
push_front(otherNode->age);
}
sort();
}
Priority_Queue::~Priority_Queue() {
while (front) {
Node* d = front;
front = front->next;
delete d;
}
rear = nullptr;
}
// Untested
Priority_Queue& Priority_Queue::operator=(Priority_Queue other) {
swap(*this, other);
return *this;
}
void Priority_Queue::enqueue(int x) {
if (!front) { // Simpler pointer check
front = new Node(x); // Provided ctor makes this simpler
rear = front;
// Single node, no need to sort
return;
}
push_front(x);
sort();
// Separate your concerns. Enqueue gets a node into the list, we worry about
// sorting elsewhere.
}
// Should be called pop(); not changing so that your main() can be left alone
void Priority_Queue::dequeue() {
if (!front) return;
Node* p = front;
front = front->next;
delete p;
}
void Priority_Queue::display() {
Node* ptr = front;
if (!front)
std::cout << "Queue is empty\n";
else {
std::cout << "Queue is :\n";
while (ptr) {
std::cout << ptr->age << '\n';
ptr = ptr->next;
}
}
}
void Priority_Queue::sort() {
// We'll go with a bubble sort
bool madeSwap;
do {
madeSwap = false;
Node* node = front;
while (node->next) {
if (node->age > node->next->age) {
std::swap(node->age, node->next->age);
madeSwap = true;
}
node = node->next;
}
} while (madeSwap);
}
void Priority_Queue::push_front(int x) { front = new Node(x, front); }
// Untested
void swap(Priority_Queue& lhs, Priority_Queue& rhs) {
using std::swap;
swap(lhs.front, rhs.front);
swap(lhs.rear, rhs.rear);
}
// Nested class
Priority_Queue::Node::Node(int a) : age(a) {} // next is automatically nullptr
Priority_Queue::Node::Node(int a, Node* n) : age(a), next(n) {}
Your main.cpp is largely untouched. It now includes the PriorityQueue.hpp, but not much else is different.
You must compile both cpp files in order to get a working program. Something like g -Wall -Wextra -std=c 17 main.cpp PriorityQueue.cpp. You'll note that I also sort in ascending order, to avoid blatant copy/paste. It's not a huge deterrent, but it's better than nothing.
To see it running, you can visit this link.
CodePudding user response：
There are way too many issues with your code, you are too far away from an working code for me to be able to help you with it.
Please read this: https://www.programiz.com/dsa/priority-queue
There is also an example in C that you can test and debug to understand exactly how it's working.
Some of the issues:
- setNext should return void.
- you never set the front in enque(see first if in enque).
- you should use std::vector or std::list as underlying type.
- you don't need to use "this" pointer(e.g "this->age = age")
- the algorithm doesn't do what you think is doing(not near close) ... I could go for a long time with this.