#include <iostream>
#include <stack>
using namespace std;
stack<int> sortst(stack<int> input)
{
	int poped;
	stack<int> temp;
	while (!input.empty())
	{
		poped = input.top();
		input.pop();
		while (!temp.empty() && temp.top() < poped)
		{
			int pop2 = temp.top();
			input.push(pop2);
			temp.pop();
		}
		temp.push(poped);
	}
	return temp;
}
int main() {
	stack<int> input;
	input.push(3);
	input.push(6);
	input.push(1);
	input.push(2);
	input.push(9);
	input = sortst(input);
	while (!input.empty())
	{
		cout << input.top() << ' ';
		input.pop();
	}
}