using System;

​

public class Node

{

    public int Data

    {

        get;

        private set;

    }

​

    public Node Next

    {

        get;

        set;

    }

​

    public Node(int data)

    {

        Data = data;

    }

}

​

public class Stack

{

    public Node Top

    {

        get;

        set;

    }

​

    public void Push(int data)

    {

        Node node = new Node(data);

        node.Next = Top;

        Top = node;

    }

​

    public int Pop()

    {

        if (Top == null)

            throw new Exception();

        int data = Top.Data;

        Top = Top.Next;

        return data;

    }

​

    public int Peek()

    {

        if (Top != null)

            return Top.Data;

        else

            throw new Exception();

    }

​

    public bool IsEmpty()

    {

        return Top == null;

    }

}

​

public class Program

{

    public static void Main()

    {

        Stack stackOne = new Stack();

        stackOne.Push(4);

        stackOne.Push(3);

        stackOne.Push(0);

        stackOne.Push(1);

        stackOne.Push(2);

        while (!stackOne.IsEmpty())

            Console.Write("{0} ", stackOne.Pop());

​

        Console.WriteLine(Environment.NewLine);

​

        stackOne.Push(4);

        stackOne.Push(3);

        stackOne.Push(0);

        stackOne.Push(1);

        stackOne.Push(2);

​

        stackOne = sortStack(stackOne);

        while (!stackOne.IsEmpty())

            Console.Write("{0} ", stackOne.Pop());

    }

​

    static Stack sortStack(Stack oldStack)

    {

        Stack newStack = new Stack();

        while (!oldStack.IsEmpty())

        {

            if (newStack.IsEmpty())

                newStack.Push(oldStack.Pop());

            else if (oldStack.Peek() < newStack.Peek())

                newStack.Push(oldStack.Pop());

            else

            {

                var item = oldStack.Pop();

                while (!newStack.IsEmpty())

                {

                    oldStack.Push(newStack.Pop());

                }

​

                newStack.Push(item);

            }

        }

​

        return newStack;

    }

}