Как отсортировать стек, используя только операции со стеком?

Я нашел этот вопрос в Интернете.

Для данного стека S напишите программу C для сортировки стека (по возрастанию приказ). Нам не разрешается делать какие-либо предположения о том, как реализован стек. Единственные используемые функции:

Push
Pop
Top
IsEmpty
IsFull

Я думаю, мы можем собрать кучу и отсортировать ее. Какое оптимальное решение для этого?