CC150 3.6

3_6.cpp

/* CC150 3.6
 * Write a program to sort a stack in ascending order (with biggest items on top).
 * You may use at most one additional stack to hold items, but you may not copy the elements into any other 
 * data structure (such as an array).The stack supports the following operations: push, pop, peek, and isEmpty.
 */

#include <iostream>
#include <stack>

using namespace std;

// COMBINE AND SHRINK RDUNDANT CODE!
void sortStack(stack<int> &stackOld)
{
	stack<int> stackNew; // set a new stack to store sorted elements
	bool done = false;
	while (!stackOld.empty()) { // iterate until all elements are in stackNew (well sorted of course)
		int temp = stackOld.top(); // store and pop the current element
		stackOld.pop();
		if (stackOld.empty()) // if temp is the last unsorted element in the stack
			done = true; // no further processing will be needed
		while (!stackNew.empty() && temp > stackNew.top()) { // move elements back until temp fits in
				stackOld.push(stackNew.top()); 
				stackNew.pop();
		}
		stackNew.push(temp); // NOTICE that temp MUST be pushed into stackNew AT SOME POINT
		if (done) break; // reduce data moving, especially when the last inseted element is relatively large
	}
	while (!stackNew.empty()) {
		stackOld.push(stackNew.top());
		stackNew.pop();
	}
	return;
}

void displayStack(stack<int> mystack)
{
	stack<int> tmpStack;
	while (!mystack.empty()) {
		tmpStack.push(mystack.top());
		mystack.pop();
	}
	while (!tmpStack.empty()) {
		cout << tmpStack.top() << " ";
		tmpStack.pop();
	}
	cout << endl;
	return;
}

int main()
{
	stack<int> mystack;
	int data;
	while (cin >> data)
		mystack.push(data);
	sortStack(mystack);
	displayStack(mystack);
	return 0;
}