排序队列 - C/C++

Question

我创建了一个队列，每个节点中有三个信息。我想在 class 中创建一个成员函数，在调用时对队列进行排序。我希望队列按时间排序？（它是一个 int 并且是 q_node 的成员）。这个队列需要按照'time'的最小值排在最前面的方式进行排序，并按升序排序。我的队列代码如下：

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字段的节点，将其从列表中移除并使其成为新列表的头部。然后继续这样做，将节点追加到新列表中，在原始列表不为空的情况下循环。当原始列表为空时，取新的（排序的）列表并将其作为新队列。

它可能不是特别有效，但应该可以正常工作。

排序队列 - C/C++

Sorting a queue - C/C++

c++

sorting

queue