#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct element {
	string znak;
	int priorytet;
	element *nastepny;
	element *poprzedni;
};
void queue() {
	element *wierzcholek_kolejki = NULL;
	element *koniec_kolejki = NULL;
	element *pomoc = NULL;
	element *pivot = NULL;
	element *tmp = NULL;
	cout << " Podaj jedna z instrukcji:\n"
		<< "d - aby dodac napis do kolejki\n"
		<< "u - aby usunac napis z kolejki\n"
		<< "w - aby wyswietlic zawartosc kolejki\n"
		<< "x - aby zakonczyc\n";
	char instrukcja; //info od uzytkownika
	int elements = 0;
	bool loop=true;
	while (loop) {
		cin >> instrukcja;
		switch (instrukcja) {
		case 'd': //dodawanie
			pomoc = new element; // tworzymy nowy obiekt
			tmp = new element;
			cout << "Podaj element" << endl;
			cin >> pomoc->znak;
			cout << "Podaj priorytet" << endl;
			cin >> pomoc->priorytet;
			if (wierzcholek_kolejki == NULL) // jezeli kolejka jest pusta
			{
				pomoc->nastepny = pomoc->poprzedni = NULL;
				koniec_kolejki = wierzcholek_kolejki = pomoc; // poczatek i koniec kolejki jest tym samym elementem
			}
			else if (pomoc->priorytet > 1) {
				pivot = wierzcholek_kolejki;
				while (pivot->priorytet >= pomoc->priorytet) {
					tmp = pivot;
					pivot = pivot->nastepny;
					if (pivot == NULL)
						break;
				}
				if (pivot == wierzcholek_kolejki) {
					pomoc->poprzedni = NULL;
					wierzcholek_kolejki->poprzedni = pomoc;
					pomoc->nastepny = wierzcholek_kolejki;
					wierzcholek_kolejki = pomoc;
				}
				else if (pivot == NULL)
				{
					tmp->nastepny = pomoc;
					pomoc->poprzedni = tmp;
					pomoc->nastepny = NULL;
					koniec_kolejki = pomoc; // ustawiamy koniec kolejki na nowym elemencie
				}
				else
				{
					tmp->nastepny = pomoc;
					pomoc->poprzedni = tmp;
					pivot->poprzedni = pomoc;
					pomoc->nastepny = pivot;
				}
			}
			else
			{
				pomoc->nastepny = NULL;
				koniec_kolejki->nastepny = pomoc; // dodajemy element na koniec wiec, ustawiamy wskaznik na niego w elemencie, ktory byl ostatni
				pomoc->poprzedni = koniec_kolejki; // poprzednikiem nowego elementu jest dotychczasowy ostatni element
				koniec_kolejki = pomoc; // ustawiamy koniec kolejki na nowym elemencie
			}
			break;
		case 'u': //usuwanie
			if (wierzcholek_kolejki != NULL){
				pomoc = wierzcholek_kolejki; // ustawiamy pomoc na wierzcholek kolejki
				if (wierzcholek_kolejki == koniec_kolejki) // jezeli jest tylko jeden element w kolejce
					wierzcholek_kolejki = koniec_kolejki = NULL; // to teraz kolejka bedzie usta
				else // jezeli jest wiecej elementow
					wierzcholek_kolejki = wierzcholek_kolejki->nastepny; // przestawiamy wierzcholek na drugi element (pierwszy musimy usunac)
				delete pomoc; // usuwamy element ze szczytu stosu
			}
			else
				cout << "Kolejka jest pusta\n";
			break;
		case 'w': //wyswietlanie
			if (wierzcholek_kolejki != NULL)
			{
				cout << "Zawartosc kolejki:\n";
				pomoc = wierzcholek_kolejki;
				while (pomoc != NULL) // dopoki pokazujemy na jakis element stosu (listy)
				{
					cout << pomoc->znak << "(" << pomoc->priorytet << ")" <<" ";
					pomoc = pomoc->nastepny; // przechodzimy na nastepny element na liscie
				}
			}
			else
				cout << "Kolejka jest pusta";
			cout << endl;
			break;
		case 'x': //wyjscie
			loop = false;
			break;
		default:
			cout << " Podaj jedna z instrukcji:\n"
				<< "d - aby dodac napis do kolejki\n"
				<< "u - aby usunac napis z kolejki\n"
				<< "w - aby wyswietlic zawartosc kolejki\n"
				<< "x - aby zakonczyc\n";
			break;
		}
	}
}
int main() {
	cout << "Kolejka" << endl;
	queue();


	system("pause");
	return 0;
}