write linked list priority queue cs106b
- User
write linked list priority queue cs106b
- Assistant
The idea of a priority queue is to store elements based on their priorities, where the highest priority element is the first to be dequeued. A linked list can be a suitable data structure to implement a priority queue. In this case, we will write a priority queue using a sorted linked list in C++ for the CS106B course. The elements with higher priority will be stored closer to the beginning of the list.
Here, let's create a simple
PriorityQueueclass that will use a specializedNodestruct for the linked list nodes. It will contain basic functions such as inserting (in sorted order), dequeuing, checking for empty, and displaying the elements in the priority queue.#include <iostream> class PriorityQueue { public: PriorityQueue(); ~PriorityQueue(); void enqueue(int value, int priority); int dequeue(); bool isEmpty() const; void display() const; private: struct Node { int value; int priority; Node* next; }; Node* front; }; PriorityQueue::PriorityQueue() { front = nullptr; } PriorityQueue::~PriorityQueue() { while (!isEmpty()) { dequeue(); } } void PriorityQueue::enqueue(int value, int priority) { Node* newNode = new Node; newNode->value = value; newNode->priority = priority; newNode->next = nullptr; if (isEmpty() || priority > front->priority) { newNode->next = front; front = newNode; } else { Node* temp = front; while (temp->next != nullptr && temp->next->priority >= priority) { temp = temp->next; } newNode->next = temp->next; temp->next = newNode; } } int PriorityQueue::dequeue() { if (isEmpty()) { throw "The priority queue is empty, can't dequeue."; } Node* temp = front; int value = front->value; front = front->next; delete temp; return value; } bool PriorityQueue::isEmpty() const { return front == nullptr; } void PriorityQueue::display() const { Node* temp = front; while (temp != nullptr) { std::cout << temp->value << " (priority: " << temp->priority << ") -> "; temp = temp->next; } std::cout << "end" << std::endl; } int main() { PriorityQueue pq; pq.enqueue(10, 3); pq.enqueue(5, 1); pq.enqueue(3, 4); pq.enqueue(20, 2); pq.display(); std::cout << "Dequeued: " << pq.dequeue() << std::endl; std::cout << "Dequeued: " << pq.dequeue() << std::endl; pq.display(); return 0; }This simple example can be expanded to handle other data types, more complex ordering logic, or further operations depending on the requirements of the CS106B course or specific assignments.