Jan 2012 - Technology - 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:

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.

#include "iostream" 

template 
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 
		{ 
			m_numElements = 0; 
			return false; 
		} 
		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 track1; 
			MyQueue track2; 
			MyQueue 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 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; 
}

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