Search⌘ K
AI Features
Home
Courses
Data Structures for Coding Interviews in C#

Solution Review: Sort Values in Stack

Learn to sort a stack's values through two main methods: an iterative approach with a temporary stack and a recursive approach using stack manipulation. This lesson explains both algorithms in C#, their implementation details, and their O(n²) time complexity, helping you grasp efficient stack sorting techniques.

We'll cover the following...

Solution #1: Using a temporary stack

C#
namespace chapter_4
{
    class Challenge5_1
    {
        static Stack<int> sortStack(Stack<int> stack, int size)
        {
            //1. Use a second tempStack.
            //2. Pop value from mainStack.
            //3. If the value is greater or equal to the top of tempStack, then push the value in tempStack
            //else pop all values from tempStack and push them in mainStack and in the end push value in tempStack and repeat from step 2.
            //till mainStack is not empty.
            //4. When mainStack will be empty, tempStack will have sorted values in descending order.
            //5. Now transfer values from tempStack to mainStack to make values sorted in ascending order.
            Stack<int> tempStack = new Stack<int>();
            while (stack.Count != 0)
            {
                int value = stack.Pop();
                if ((tempStack.Count > 0) && (value >= tempStack.Peek()))
                {
                    tempStack.Push(value);
                }
                else
                {
                    while (tempStack.Count != 0)
                    {
                        stack.Push(tempStack.Pop());
                    }
                    tempStack.Push(value);
                }
            }
            //Transfer from tempStack => stack
            while (tempStack.Count != 0)
            {
                stack.Push(tempStack.Pop());
            }
            return stack;
        }
        static void ShowStack(Stack<int> stack)
        {
            while (stack.Count != 0)
            {
                Console.Write("\t" + stack.Pop());
            }
        }
        static void Main(string[] args)
        {
            Stack<int> stack = new Stack<int>();
            stack.Push(2);
            stack.Push(97);
            stack.Push(4);
            stack.Push(42);
            stack.Push(12);
            stack.Push(60);
            stack.Push(23);
            ShowStack(sortStack(stack, 7));
        }
    }
}

This solution takes an iterative approach towards the problem. Create a helper stack called tempStack. Its job is to hold the elements of stack in descending order.

The main functionality of the algorithm lies in the nested while loops. In the outer loop, pop elements out of stack until it is empty. As long as the popped value is larger than the top value in tempStack, you can push it in. ...