#include <iostream>
#include <string>

using namespace std;

struct node {
    int priority;
    string info;
    struct node *link;
};

class Priority_Queue {
private:
    node *front;
public:
    Priority_Queue() {
        front = NULL;
    }
    void insert(string item, int priority) {
        node *tmp, *q;
        tmp = new node;
        (*tmp).info = item;
        (*tmp).priority = priority;
        if (front == NULL || priority < (*front).priority) {
            (*tmp).link = front;
            front = tmp;
        }
        else {
            q = front;
            while ((*q).link != NULL && (*q).priority <= priority) {
                q = (*q).link;
            }
            (*tmp).link = (*q).link;
            (*q).link = tmp;
        }
    }

    void del() {
        node *tmp;
        if (front == NULL) {
            cout << "Kolejka jest pusta\n";
        }
        else {
            tmp = front;
            cout << "Usunieta rzecz to: " << (*tmp).info << "\n";
            front = (*front).link;
            free(tmp);
        }
    }

    void display() {
        node *ptr;
        ptr = front;
        if (front == NULL) {
            cout << "Kolejka jest pusta\n";
        }
        else {
            cout << "Twoja kolejka to: \n";
            cout << "Priorytet      rzecz\n";
            while (ptr != NULL) {
                cout << (*ptr).priority << "          " << (*ptr).info << endl;
                ptr = (*ptr).link;
            }
        }
    }
};

int main() {
    int choice, priority;
    string item;
    Priority_Queue pq;
    do {
        cout << "1. Wstaw\n"
            << "2. Usun\n"
            << "3. Wyswietl\n"
            << "4. Wyjscie\n"
            << "Co chcesz zrobic?\n";
        cin >> choice;
        switch (choice) {
        case 1:
            cout << "Wprowadz rezcz, ktora ma byc dodana do kolejki: \n";
            cin.ignore();
            getline(cin, item);
            cout << "Wprowadz priorytet:\n";
            cin >> priority;
            pq.insert(item, priority);
            break;
        case 2:
            pq.del();
            break;
        case 3:
            pq.display();
            break;
        case 4:
            return 0;
            break;
        default:
            cout << "Bledny wybor! Sprobuj ponownie!";
            break;
        }
    } while (choice != 4);
    return 0;
}