优先队列未按正确顺序排序

Question

所以我正在尝试构建一个优先级队列，它接受 2 个数字（0 和 2）。优先级为 0 的值将根据到达时间添加到队列的后面。优先级为 2 的数据包将被插入到优先级为 0 的数据包之前，但不会先于已经排队的优先级数据包。请不要使用 std::priority_queue。这也是使用链接列表的要求有人可以指出我做错了什么吗？示例数据包（粗体优先）：

55555555555555D507E34B17887100A0FF18221981000100000663727970746fC704DD7B

 pQueue100::pQueue100(){
    front = NULL;
}

void pQueue100::insert(string packet, int priority)
{
    node2 *temp, *q;
    temp = new node2;
    temp ->info= packet;
    temp ->priority = priority;
    if (front == NULL ||priority <front->priority)
    {
        temp->link =front;
        front = temp;
    }else 
    {
        q = front;
        while (q->link != NULL && q->link->priority<=priority)
            q=q->link;
        temp->link = q->link;
        q->link=temp;
    }

    //display();
}//insert

void pQueue100::display()
{
    node2 *ptr;
    ptr = front;
    //node2 *temp;
    //temp = front;

    if (front ==NULL)
        cout << "Queue is empty" <<endl;
    else 
    {
        while (ptr != NULL)
        {
            ptr->priority;
            //temp->info;
            cout << ptr->priority << "|" ;
            cout << ptr->info <<endl;
            ptr = ptr->link;

        }
    }
}

如果你们想看看数据包来自哪里：

void thr1::selectPQueue(string packet){ //reads in packets from FIFO Queue and sorts it based on VLAN Tag and priority
    pQueue100 p100;
//  cout <<packet <<endl;//print packets for testing

    if (packet.substr(45,3) == "100"){ //if the packet matches VLAN 100....

        if (packet.substr(44,1) == "0"){
            priorityCode = 0;
        }else if (packet.substr(44,1) == "2"){
            notif = "!!!!!!!!!Priority Packet Packet Found: <..." + packet.substr(16,11) + "...> !!!!!!!!!";
            priorityCode = 2;
            packetCopy = packet;
            //thr2.interupptHandler(packetCopy, notif);
        }else
            priorityCode = priorityCode;

        p100.insert(packet, priorityCode);


    }//end VLAN 100

    else if (packet.substr(45,3) =="101") //if the packet matches VLAN 101
    {


        if (packet.substr(44,1) == "0"){
            priorityCode = 0;
        }else if (packet.substr(44,1) == "2"){
            notif = "!!!!!!!!!Priority Packet Packet Found: <..." + packet.substr(16,11) + "...> !!!!!!!!!";
            priorityCode = 2;
            packetCopy = packet;
            //thr2.interupptHandler(packetCopy, notif);

        }else
            priorityCode = priorityCode;
        //pQ101().recieveInterrupts(packet, priority,);

    }//end VLAN 101

    //p100.display();

Answer 1

反转您使用的比较运算符是一件简单的事情。

void pQueue100::insert(string packet, int priority)
{
    node2 *temp, *q;
    temp = new node2;
    temp ->info= packet;
    temp ->priority = priority;
    if (front == NULL ||priority > front->priority)
    {
        temp->link =front;
        front = temp;
    }else 
    {
        q = front;
        while (q->link != NULL && q->link->priority >= priority)
            q=q->link;
        temp->link = q->link;
        q->link=temp;
    }
}

Driver代码：

int main() 
{
    pQueue100 q;
    q.insert("alpha", 0);
    q.insert("beta", 2);
    q.insert("gamma", 0);
    q.insert("delta", 2);
    q.insert("epsilon", 0);
    q.insert("zeta", 2);
    // correct display sequence should be:
    // beta, delta, zeta, alpha, gamma, epsilon
    q.display();
}

输出：

2|beta
2|delta
2|zeta
0|alpha
0|gamma
0|epsilon

优先队列未按正确顺序排序

Priority Queue not sorting in right order

c++

multithreading

linked-list

priority-queue