priority-queue.cpp

/*
 * ============================================================================
 * Topic : Priority queue (linked list)
 * Level : Data structures — priority queues
 * ----------------------------------------------------------------------------
 * What you'll learn
 *   Store nodes ordered by priority (higher priority nearer the front).
 *   Enqueue walks the list to find the correct insertion spot.
 *   Dequeue always removes from the front (highest priority).
 * ----------------------------------------------------------------------------
 * How to run
 *   • OnlineGDB: https://www.onlinegdb.com/online_c++_compiler
 *     Open this file on GitHub → copy → paste into OnlineGDB → C++ → Run
 *   • Codespaces (whole repo): https://codespaces.new/baheesa/cpp-practice?quickstart=1
 *   • Local: g++ -std=c++17 -Wall -o app "03-data-structures/priority-queue.cpp" && ./app
 * ----------------------------------------------------------------------------
 * Example input
 *   enqueue (value,priority) pairs → dequeue → display
 * Example output
 *   Dequeued: 50 (priority 1)
 *   Remaining: 20(p2) 10(p5)
 * ============================================================================
 */

#include <iostream>
using namespace std;

struct Node {
    int value;
    int priority;  // larger number = higher priority in this implementation
    Node* next;
    Node(int v, int p) : value(v), priority(p), next(nullptr) {}
};

class PriorityQueue {
    Node* front;
    int size;
public:
    PriorityQueue() : front(nullptr), size(0) {}
    ~PriorityQueue() {
        while (front) {
            Node* t = front;
            front = front->next;
            delete t;
        }
    }

    void enqueue(int value, int priority) {
        Node* n = new Node(value, priority);
        // Insert so the list stays sorted: highest priority at front.
        if (!front || priority > front->priority) {
            n->next = front;  // new head (empty queue, or beats current front)
            front = n;
        } else {
            Node* cur = front;
            // Stop just before the first node with strictly lower priority than n.
            while (cur->next && cur->next->priority >= priority)
                cur = cur->next;
            n->next = cur->next;
            cur->next = n;
        }
        size++;
    }

    void dequeue() {
        if (!front) { cout << "Empty.\n"; return; }  // edge: nothing to remove
        // Front is always the highest-priority node by construction.
        cout << "Dequeued " << front->value
             << " (priority " << front->priority << ")\n";
        Node* t = front;
        front = front->next;
        delete t;
        size--;
    }

    void display() const {
        if (!front) { cout << "(empty)\n"; return; }
        for (Node* cur = front; cur; cur = cur->next)
            cout << cur->value << "(p" << cur->priority << ") ";
        cout << "\nsize=" << size << '\n';
    }

    void menu() {
        int c, v, p;
        do {
            cout << "\n1 Enqueue  2 Dequeue  3 Display  0 Exit\nChoice: ";
            cin >> c;
            if (c == 1) {
                cout << "Value: "; cin >> v;
                cout << "Priority: "; cin >> p;
                enqueue(v, p);
            } else if (c == 2) {
                dequeue();
            } else if (c == 3) {
                display();
            }
        } while (c != 0);
    }
};

int main() {
    PriorityQueue q;
    q.menu();
    return 0;
}