Сортировка очереди - C/C++

Question

Я создал очередь, которая в каждом узле содержит три информации. Я хочу создать функцию-член в классе, сортирующую очередь при вызове. Я хочу, чтобы сортировка была отсортирована по времени? (это int и член q_node). Эта очередь должна сортироваться таким образом, чтобы наименьшее значение «времени» находилось спереди и сортировалось в порядке возрастания. Мой код для моей очереди находится ниже:

typedef struct Qnode{ 
    int time; 
    char name[10]; 
    char value; 

    struct Qnode *q_next; 
    struct Qnode *q_prev; 
} q_node; 

class Queue{ 
private: 
    q_node *q_rear; 
    q_node *q_front; 
    int number; 
public: 
    Queue(); 
    void enqueue(int time, char *s, char value); 
    q_node *q_top(){ 
     return q_front; 
    } 
    void dequeue(); 
    void display(); 
    void queueSort(); 
    bool isEmpty(); 
}; 

Queue::Queue(){ 
    q_rear = NULL; 
    q_front = NULL; 
    number = 0; 
} 

bool Queue::isEmpty(){ 
    if (q_front == NULL) 
     return true; 
    else 
     return false; 
} 

void Queue::enqueue(int t, char *n, char v){ 
    q_node *q_temp = new q_node; 

    q_temp->time = t; 
    strcpy(q_temp->name , n); 
    q_temp->value = v; 
    q_temp->q_next = NULL; 

    if(q_front == NULL){ 
     q_front = q_temp; 
    } 
    else{ 
     q_rear->q_next = q_temp; 
    } 
    q_rear = q_temp; 
    number++; 
} 

void Queue::dequeue(){ 
    q_node *q_temp = new q_node; 
    q_temp = q_front; 
    q_front = q_front -> q_next; 
    number--; 
    delete q_temp; 
} 


void Queue::display(){ 
    q_node *p = new q_node; 
    p = q_front; 
    while(p!=NULL){ 
     cout<< "\ntime: " << p->time; 
     cout<< "\nname: " << p->name; 
     cout<< "\nvalue: " << p->value; 
     cout << endl; 
     p = p->q_next; 
    } 
} 

void Queue::queueSort(){ 
    //Code for sorting 

} 

Answer 1

Один из способов сбросить очереди в массив или вектор с помощью dequeue, используйте std::sort, а затем восстановить очередь с нуля, используя вашу enqueue функцию. Это чисто и позволяет избежать ошибок с указателями. Это также оптимально, потому что время работы зависит от времени, которое требуется для сортировки.

Что-то вроде:

v = vector of nodes 
while(Q.isEmpty() == false) 
{ v.push_back(*Q.top()); 
    Q.dequeue(); 
} 

sort(v.begin(), v.end(), cmp); 

for(int i = 0; i < v.size(); i++) 
{ Q.enqueue(v[i].time, v[i].name, v[i].value); 
} 

Где cmp сравнивает узлы по времени.

Answer 2

Найдите узел с наименьшим размером поля time, удалите его из списка и сделайте его главой нового списка. Затем продолжайте делать это, добавляя узлы в новый список, в цикле, в то время как исходный список не пуст. Когда исходный список пуст, возьмите новый (отсортированный) список и сделайте его новой.

Это может быть не особенно эффективно, но должно работать нормально.