Turbo C++ - Applying Queue Technique for Rail Road Car Rearrangement
I have given here the source code in Turbo 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:
- Construct three queues (FIFO) Namely Track 1, Track 2, Track 3
- Input the all the cars into Track 1.
- Move the first car from Track 1 and Track 3.
- Compare the cars from Track 1 and Track 3. If there are no cars in Track 1, then go to step 7.
- 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.
- 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.
- 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.
- 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.
- Go to Step 4 until Track 1 is empty.
- You will notice all the cars are moved on to Track 3 in the correct order.
Source Code
#include <iostream.h>
#include <alloc.h>
#include <stdlib.h>
#include <string.h>
typedef enum _boolean
{
true = 1, false = 0
} bool;
template<class T>
class MyQueue
{
class T *m_data;
int m_numElements;
public:
MyQueue() : m_data(NULL), m_numElements(0) { }
~MyQueue()
{
free(m_data);
m_data = NULL;
m_numElements = 0;
}
T front();
int size()
{
return m_numElements;
}
bool Rearrange();
bool push(T data);
bool pop();
bool Sort();
};
template<class T>
bool MyQueue<class T>::Sort()
{
for(int i = 1; i < m_numElements; i++)
{
for(int j = 0; j < m_numElements - i; j++)
{
if(m_data[j] > m_data[j + 1])
{
T temp = m_data[j];
m_data[j] = m_data[j + 1];
m_data[j + 1] = temp;
}
}
}
return true;
}
template<class T>
bool MyQueue<class T>::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;
}
template<class T>
bool MyQueue<class T>::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;
}
template<class T>
T MyQueue<class T>::front()
{
if(m_numElements > 0)
return m_data[0];
}
template<class T>
bool MyQueue<class T>::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;
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(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];
cout << "Enter Rail Road Car Order: ";
cin >> inpstring;
for(int i = 0; i < strlen(inpstring); i++)
q1.push(inpstring[i]);
q1.Rearrange(); // Using three tracks
int sz1 = q1.size();
cout << "After RailRoad Car Rearrangement:\n";
for(i = 0; i < sz1; i++)
{
cout << q1.front();
q1.pop();
}
cout << "\n";
return 0;
}
Click here to download Turbo 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
|
|