Problem

Given a stack of integers, sort the stack in ascending order. You may use additional stacks to hold the elements, but you may not use any other data structures (arrays, lists, etc.).
Example input: [3, 2, 1, 4]
Example output: [1, 2, 3, 4]

Solution

#include <iostream>
#include <stack>

using namespace std;

void sortStack(stack<int> &s) {
	stack<int> temp;
	while (!s.empty()) {
		int x = s.top();
		s.pop();
		while (!temp.empty() && temp.top() > x) {
			s.push(temp.top());
			temp.pop();
		}
		temp.push(x);
	}
	while (!temp.empty()) {
		s.push(temp.top());
		temp.pop();
	}
}

int main() {
	stack<int> s;
	s.push(3);
	s.push(2);
	s.push(1);
	s.push(4);
	sortStack(s);
	while (!s.empty()) {
		cout << s.top() << endl;
		s.pop();
	}
	return 0;
}