Software & Finance





Visual C++ - Applying Queue Technique for Rail Road Car Rearrangement





I have given here the source code in Visual C++ for Queue (First In First Out). I have used templates. For dynamic memory allocation, I have used malloc, realloc and free functions. For rearrange function, I have used 3 tracks to sort the queue. For more infomation, loot at the output section for each iteration what the content of 3 tracks.


The other related links are,

Visual C++ - Sample Queue With Template and Regular Sorting 

Turbo C++ - Sample Queue With Template and Regular Sorting

Turbo C++ - Applying Queue Technique for Rail Road Car Rearrangement

Visual C++ - Applying Queue Technique for Rail Road Car Rearrangement

 

Algorithm:

 

  1. Construct three queues (FIFO) Namely Track 1, Track 2, Track 3
  2. Input the all the cars into Track 1.
  3. Move the first car from Track 1 and Track 3.
  4. Compare the cars from Track 1 and Track 3. If there are no cars in Track 1, then go to step 7.
  5. If track 3 holds the least value, then move the car from Track 1 to Track 2. Here Track 3 holds the least value again. Go to Step 4.  
  6. If track 3 holds the higher value, then move the car from Track 3 to Track 2 and Move the car from Track 1 to Track 3. Now Track3 holds the least value. Go to Step 4.
  7. Now if it first pass, there will be one car which is least among the queue would be in Track 3 and the Track 1 would be empty and the track 2 would have other cars. If it is second pass, there will be two cars which are least among the queue would be in Track 3 and Track 1 would be empty and the track 2 would have other cars. And so on.
  8. Move all the cars one by one from Track 2 Queue to Track 1 Queue - This step can be avoided but the algorithm needs to be changed so that Track 1 behaves like Track 2 and Track 2 behaves like Track 1 on Step 4, 5, 6.
  9. Go to Step 4 until Track 1 is empty.
  10. You will notice all the cars are moved on to Track 3 in the correct order.

 

 



Source Code


#include <iostream>

 

template<class T>

class MyQueue

{

    T *m_data;

    int m_numElements;

 

public:

    MyQueue() : m_data(NULL), m_numElements(0) { }

    ~MyQueue()

    {

        free(m_data);

        m_data = NULL;

        m_numElements = 0;

    }

 

    bool push(T data)

    {

        if(m_data == NULL) // root node

        {

            m_numElements = 1;

            m_data = (T*) malloc(sizeof(T));

        }

        else

        {

            m_numElements++;

            m_data = (T*) realloc(m_data, m_numElements * sizeof(T));

        }

 

        m_data[m_numElements - 1] = data;

        return true;

    }

 

    bool pop()

    {

        if(m_data == NULL) // root node

        {

            return false;

            m_numElements = 0;

        }

        else

        {

            if(m_numElements == 1)

            {

                // last item

                m_numElements = 0;

                free(m_data);

                m_data = NULL;

            }

            else

            {

                m_numElements--;

                memmove(m_data, &m_data[1], m_numElements * sizeof(T));

                m_data = (T*) realloc(m_data, m_numElements * sizeof(T));

            }

        }

        return true;

    }

 

    T front()

    {

        if(m_numElements > 0)

            return m_data[0];

    }

 

    int size()

    {

        return m_numElements;

    }

 

    bool Rearrange()

    {

        // Create 3 tracks

        MyQueue<T> track1;

        MyQueue<T> track2;

        MyQueue<T> track3;

       

        int sz = m_numElements;

        for(int i = 0; i < sz; i++)

        {

            track1.push(front());

            pop();

        }

 

        while(1)

        {

            int len1 = track1.size();

            if(len1 == 0)

                break;

           

            // Track1, Track2, Track3 moves

            for(int i = 0; i < len1; i++)

            {

                if(i == 0)

                {

                    track3.push(track1.front());

                    track1.pop();

                }

                else

                {

                    if(track3.front() < track1.front())

                        {

                                track2.push(track3.front());

                                track3.pop();

                                track3.push(track1.front());

                                track1.pop();

                        }

                    else

                    {

                        track2.push(track1.front());

                        track1.pop();

                    }

                }

            }

            int len2 = track2.size();

            for(int i = 0; i < len2; i++)

            {

                track1.push(track2.front());

                track2.pop();

            }

            push(track3.front());

            track3.pop();

        }

 

        return true;

    }

};

 

int main()

{

    MyQueue<char> q1;

 

    char inpstring[32];

    std::cout << "Enter Rail Road Car Order: ";

    std::cin >> inpstring;

 

    for(int i = 0; i < strlen(inpstring); i++)

        q1.push(inpstring[i]);

   

    q1.Rearrange(); // Using three tracks

 

    int sz1 = q1.size();

 

    std::cout << "\nAfter RailRoad Car Rearrangement:\n\n";

    for(int i = 0; i < sz1; i++)

    {

        std::cout << q1.front();

        q1.pop();

    }

    std::cout << "\n";

 

    return 0;

}

Click here to download Visual C++ Source Code and Executable

 

Output


 

Enter Rail Road Car Order: 456312

 

After RailRoad Car Rearrangement:

 

654321


Press any key to continue . . .


For each iteration, the car with biggest number is moved the correct position in the original track. The diagram is given for the first two iterations

Click here to get the diagram as a word document