what is the algorithm?

This is called a priority queue, items in the queue are processed by their priority number first then FIFO order.

While the answers Andreas & Mehdi are good, you may want to investigate MSMQ[^] or something similar too.

MSMQ allows you to set the priority of messages, and it allows you to safely persist the elements in the queue. This is often important when you are handling money. You really, really don't want to loose track of money - so each step of your processing pipeline should be both transacted and persisted.

Best regards
Espen Harlinn

There is an implementation of priority queues algorithm in the STL: "priority_queue"
The header is "queue"

It includes a new method "front" to add priority items.

http://www.cplusplus.com/reference/stl/priority_queue/[^]

http://www.cplusplus.com/reference/stl/priority_queue/priority_queue/[^]

Hi,

This is exactly priority queue. Each items in the queue are assigned a particular priority based on some criteria.The processing is carried out based on this criteria. The item with most priority is processed first and so on.


Cheers

All these answers are good. Better you can use a priority queue or you can use a linked list to act as a queue. The linked list must contain a structure with an item to denote whether the particular item has a priority or not.

So each time when you take the data from linked list, traverse the entire list to check whether any priority item is present or not.

If present, take that item.

Else take the first item in list which will be first item you have entered. So it will work on a FIFO basis with priority scheduling.

All of my colleagues are correct as far as computer science is concerned. Priority queues allow you to enter elements in the proper order for removal. Multi-queue / multi-server queues allow for a totally different priority track for inportant transactions / elements.

Priority Queues work well in computer applications but fail horribly when applied to real people. Have you ever tried to user your "priority customer card" at a bank, or worse yet, in the ticket line at a concert. It's called "line jumping" and you will incur the wrath of everybody else in line. You will be forced to explain your "priority" to everybody else in line and they are the ones who decide if your "priority" is valid or if you are kicked out of line.

Multi-Queue (whether single or multi-server) work best in "people" applications. Consider the Ticket Office at the MGM Grand at Foxwoods where there is the "general ticket pick-up" line snaking through the lobby and the "Platinum and Diamond Elite" line which is very short and has it's own ticket agent. Nobody argues with you when you get into that line, the ticket agent checks your status at the desk and politely asks you to go to the other line if you are in the wrong line. Everything flows smoothly and pleasantly.

So, if you are working with cold, emotionless applications that do not care if another applications / task / transaction / thread jumps in front of them, Priority queues are the way to go. If you are working with people, separate the elite from the great unwashed public whenever you can (multi-queue).

Just my 2 cents worth :)

Great answers above...

If I were writing this queue it might look something like this...

#pragma once

#include <map>
#include <deque>

template<class T>
class CPriorityQueueT
{
protected:
    std::map<int, std::deque<T>>	PriorityMap;

public:
    bool	PushMessage(const T & Message, int Priority = 5);

public:
    bool	PopMessage(T & Message, int * pPriority = NULL);
};

template<class T>
bool CPriorityQueueT<T>::PushMessage(const T & Message, int Priority)
{
    // Find the deqeue that has the same priority
    std::map<int, std::deque<T>>::iterator Iter = PriorityMap.find(Priority);
    if (Iter == PriorityMap.end())
    {
        // The deque doesn't exist. Create it.
        PriorityMap.insert(std::pair<int, std::deque<T>>(Priority, std::deque<T>()));
        Iter = PriorityMap.find(Priority);
    }
    
    // Add the message to the deque
    std::deque<T> & Deque = (*Iter).second;
    Deque.push_back(Message);
    
    return true;
}

template<class T>
bool CPriorityQueueT<T>::PopMessage(T & Message, int * pPriority)
{
    std::map<int, std::deque<T>>::iterator Iter = PriorityMap.begin();
    std::map<int, std::deque<T>>::iterator End  = PriorityMap.end();
    
    // Loop through the map and see if any of the priority deques have data.
    for (; Iter != End; Iter++)
    {
        if ((*Iter).second.size())
            break;
    }
    
    if (Iter == PriorityMap.end())
    {
        // All deques are empty. Exit.
            return false;
    }

    if (pPriority)
        *pPriority = (*Iter).first;
    
    std::deque<T> & Deque = (*Iter).second;
    Message = Deque.front();
    Deque.pop_front();
    
    return true;
}