CODEWITHSUNDEEP
c++
Corey
Corey

Reputation: 21

Sorting a queue based on this criteria

I have a queue that stores pointers to Node objects which are defined as:

class Node {
public:
    Node(int, char, Node*);
    void setC(char);
    char getC();
private:
    int x;
    char c;
    Node* next;
};

Here, c can be either 'S', 'M' or 'L'. (small, medium or large). Now, I want to sort this queue in the ascending order of sizes like all 'S' nodes at the beginning/front, followed by all the 'M' nodes and all the 'L' nodes at the end.

Efficiency is not really a criteria. How do I go about it?

Upvotes: 0

Views: 52

Answers (2)

mbschenkel
mbschenkel

Reputation: 1905

You could use a priority_queue:

#include <queue>
#include <iostream>

using namespace std;

class Node { /* ... */ };

// 'S' < 'M' < 'L'
bool operator< (const Node& lhs, const Node& rhs)
{
    switch(lhs.c) {
        case 'S': return !('S' == rhs.getC());
        case 'M': return ('L' == rhs.getC());
        case 'L': return false;
        default:  throw "must be S, M or L";
    }
}

int main() {
    priority_queue<Node> pq;

    pq.push(Node('S'));
    pq.push(Node('M'));
    pq.push(Node('L'));
    pq.push(Node('S'));
    pq.push(Node('M'));
    pq.push(Node('L'));

    while(pq.size()) {
        cout << pq.top().getC() << endl;
        pq.pop();
    }
}

will give them in descending order:

L
L
M
M
S
S

Upvotes: 1

Henrik St&#229;hlberg
Henrik St&#229;hlberg

Reputation: 318

You could create three stacks and then empty the queue and placing each type in one of the stacks. Then just fill the queue again start with stack 'S' and then stack 'M' and last 'L'.

This is not efficient and maybe storing whole queue in an array and then sort it and replace in queue is a better way.

Upvotes: 0

Related Questions