Dodanie do kolejki dwukierunkowej priorytetu

Mam za zadanie do stworzonej kolejki dwukierunkowej dodać priorytet by z przodu kolejki były liczby parzyste. Zrobiłem to dodając kolejnego ifa do funkcji add. Teraz chciałbym posortować to ale jak na razie nie mam pomysłu jak to zrobić

#include <iostream>
using namespace std;


struct elem
{
    elem *next;
    elem *prev;
    int data;
};
struct queue
{
    elem *head;
    elem *tail;
    elem *size;
    elem *first;
};
void init(queue &q)
{
    q.head = q.tail = NULL;
}

void printAscending(const queue &q)
{
    elem *current;
    current = q.head;
    cout << "Kolejka:          ";
    while(current != NULL)
    {
        cout << current->data << ", ";
        current = current->next;
    }
    cout << endl;
}
void printDescending(const queue &q)
{
    elem *current;
    current = q.tail;
    cout << "Kolejka od konca: ";
    while(current != NULL)
    {
        cout << current->data << ", ";
        current = current->prev;
    }
    cout << endl;
}
int remove(queue &q)
{
    if(q.head != NULL)
    {
        int value = q.head->data;
        if(q.head == q.tail)
        {
            delete q.head;
            q.head = q.tail = NULL;
        }
        else
        {
            elem *first = q.head;
            q.head = q.head->next;
            q.head->prev = NULL;
            //cout << "del remove" << endl;
            delete first;
        }
        return value;
    }
}
void clear(queue &q)
{
    if(q.head != NULL)
    {
        elem *current;
        elem *currentNext;
        current = q.head;
        while(current != NULL)
        {
            currentNext = current->next;
            //cout << "del clear" << endl;
            delete current;
            current = currentNext;
        }
        q.head = q.tail = NULL;
    }
}

void add(queue &q, const int &s)
{
    //cout << "new" << endl;
    elem *newElem = new elem;
    newElem->data = s;
    if(q.head == NULL)
    {
        //cout << "Wstawienie - pusta" << endl;
        q.head = q.tail = newElem;
        newElem->prev = newElem->next = NULL;
    }
    else if(newElem->data%2==0)
    {
        newElem->next = q.head;
        newElem->prev = NULL;
        q.head->prev = newElem;
        q.head = newElem;
    }
    else if(newElem->data >= q.tail->data)
    {
        //cout << "Wstawienie - koniec" << endl;
        newElem->next = NULL;
        newElem->prev = q.tail;
        q.tail->next = newElem;
        q.tail = newElem;
    }
    else if(newElem->data <= q.head->data)
    {
        //cout << "Wstawienie - poczatek" << endl;
        newElem->next = q.head;
        newElem->prev = NULL;
        q.head->prev = newElem;
        q.head = newElem;
    }
    else
    {
        //cout << "Wstawienie - srodek";
        elem * currentNext = q.head;
        elem * currentPrev;
        while(newElem->data > currentNext->data)
        {
            currentNext = currentNext->next;
        }
        currentPrev = currentNext->prev;

        cout << " pomiędzy " << currentPrev->data << " i " << currentNext->data << endl;

        newElem->next = currentNext;
        newElem->prev = currentPrev;
        currentNext->prev = newElem;
        currentPrev->next = newElem;
    }
}
void minimum(queue &q)
{

    elem *current;
    current = q.head;
    int mini=current->data;
    while(current != NULL)
    {
        if(mini>current->data)
        {
            mini = current->data;
        }

        current = current->next;
    }
    cout<<"Minimalna wartosc to: "<<mini<<endl;
}
int main()
{
    queue q;

    //tworzy pustą kolejkę
    init(q);

    add(q, 1);
    add(q, 2);
    add(q, 3);
    add(q, 4);
    add(q, 5);

    add(q, 6);
    add(q, 7);
    add(q, 8);
    add(q, 9);
    add(q, 10);

    add(q, 11);
    add(q, 12);
    add(q, 13);


    printAscending(q);
    printDescending(q);
    minimum(q);

    clear(q);

    return 0;
}

Pisz to po chrześcijańsku w prawdziwym C++

Być może są tu dobrze zadatki, ale ja w takim kodowaniu nie mam zamiaru czytać

elem *size; - dalej odechciało mi się czytać.

Damian Malicki napisał(a):

Mam za zadanie do stworzonej kolejki dwukierunkowej dodać priorytet by z przodu kolejki były liczby parzyste.

Prosty algorytm polskiej flagi.
Parzyste dodajesz na początek, nieparzyste na koniec.

Czemu nie używasz standardowej w tym wypadku kompozycji, (struktura, elem wewnątrz, queue)?
elem * head;, oraz, elem * first; WTF?
elem * size; WTF, WTF?
Co do sortowania, to znowu, standardowo, w przypadku struktur wskaźnikowych, wczytuje sie je do wektora, std::vector, sortuje go i kopiuje do struktury, wychodzi, .

lion137 napisał(a):

elem * head;, oraz, elem * first; WTF?

first to zmienna potrzebna w remove() :D

lion137 napisał(a):

Co do sortowania, to znowu, standardowo, w przypadku struktur wskaźnikowych, wczytuje sie je do wektora, std::vector, sortuje go i kopiuje do struktury, wychodzi, .

To ma być kolejka priorytetowa, czyli wystarczy przestawić minimalny element na górę, czyli .

@lion137: Czemu nie używasz standardowej w tym wypadku kompozycji, (struktura, elem wewnątrz, queue)?

Dlatego że to jest kod który mam zmodyfikować. Nie pisałem go sam.

@_13th_Dragon: To ma być kolejka priorytetowa, czyli wystarczy przestawić minimalny element na górę, czyli O(n).

Niestety nie wiem do końca o co chodzi z O(n)

Czy jest taka możliwość by posortować kolejkę by najpierw były liczby parzyste a później nie?

Dostałeś odpowiedź na to pytanie: https://4programmers.net/Forum/C_i_C++/352762-dodanie_do_kolejki_dwukierunkowej_priorytetu?p=1772784#id1772784

Zapoznałem się jak wygląda algorytm flaga polska tylko nie wiem jak sprawdzić ilość elementów. Próbowałem użyć size ale bez skutku

Proste jak konstrukcja bata.
W remove zmniejszasz składową size, zaś w add - zwiększasz.
Tylko że typ tego size nie jest odpowiedni, ale o tym też już mówiłem: https://4programmers.net/Forum/C_i_C++/352762-dodanie_do_kolejki_dwukierunkowej_priorytetu?p=1772784#id1772784

Dziękuje za pomoc jeśli chodzi o size. Jeśli chodzi o sam algorytm to chciałbym zapytać czy jestem chodź odrobinę blisko. Znając życie ciężko będzie na to patrzeć:

void flagaPolska(const queue &q)
{
    int i = 0, j =q.size-1;
    elem *current;
    elem *currentBack;
    current = q.head;
    currentBack = q.tail;

    while(i<j)
    {
        while((current->data%2==0)&&(i<j))i++;
        while((currentBack->data%2==1)&&(i<j))j--;
        if(i<j)
        {
            swap(current->data, currentBack->data);
            i++;
            j--;
        }
    }

    current=current->next;
    currentBack=currentBack->prev;
}

• http://forum.4programmers.net/1101404
• czemu nie zrobić tego w add zwyczajnie dodajesz na koniec lub na początek w zależności od data
• jak już musisz sortować po dodaniu zwyczajnie usuwaj z tej kolejki dodawaj do innej, po czym podmień head i tail
• nigdzie nie przechodzisz po elem kolejki, cały czas stoisz na pierwszym i ostatnim i w kółko je swapujesz
• po kiego ci te i,'jto nie jest tablica to jest twój odpowiednik++i: current=current->next;`
• warunkiem stopu może być current!=currentBack
• current, currentBack zbyt długie nazwy na mała funkcję zamień na f jak front oraz b jak back w sumie front, back też wystarczająco krótkie.