How to reverse a stack


Category: Data Structure And Algorithms Tags: C#

I have a stack as below:

1
2
3
4
5

I want to reverse it as:

5
4
3
2
1


Like 0 People
Asked about 29 days ago
Nikhil Joshi

Nikhil Joshi
Ceo & Founder at Dotnetlovers
Atricles: 135
Questions: 12
Given Best Solutions: 12 *

Answers:

Nikhil Joshi

Using recursion:

To reverse a stack we have to pop out all the elements first, then start inserting them back one by one but one thing to remember is while inserting back each element should be inserted at bottom of the stack.

So I have a stack having values 1(top), 2, 3, 4, 5 (bottom), suppose all the elements are popped out now and I start inserting them back (in stack last popped out element will be inserted back first so 5 will be inserted first and then 4 and so on):

inserting 5 -> push 5 -> 5

inserting 4 -> pop 5 -> push 4 -> push 5 -> 5, 4

inserting 3 -> pop 5 -> pop 4 -> push 3 -> push 4 -> push 5 -> 5, 4, 3 

Similarly:

2 -> 5, 4, 3, 2

1 -> 5, 4, 3, 2, 1

Implementation will be following:

class Program
{  
    static void Main(string[] args)
    {
        Stack<int> stack = new Stack<int>();
        stack.Push(5);
        stack.Push(4);
        stack.Push(3);
        stack.Push(2);
        stack.Push(1);

        Console.WriteLine("Stack before reverse:");
        foreach (int element in stack.ToArray())
        {
            Console.WriteLine(element);
        }

        Reverse(stack);

        Console.WriteLine("Stack after rseverse:");
        foreach (int element in stack.ToArray())
        {
            Console.WriteLine(element);
        }

        Console.ReadLine();
    }

    static void Reverse(Stack<int> stack)
    {
        //untill all elements are poped
        if (stack.Count == 0)
            return;

        int element = stack.Pop();
        Reverse(stack);
        InsertAndRearrange(stack, element);
    }
    static void InsertAndRearrange(Stack<int> stack, int element)
    {
        //insert element to only bottom
        if (stack.Count == 0)
            stack.Push(element);
        else
        {
            //if stack is not empty, pop until bottom is reached
            int temp = stack.Pop();
            InsertAndRearrange(stack, element);
            //push back poped elements when input element is pushed to bottom
            stack.Push(temp);
        }
    }
}

Output

Stack before reverse:

1

2

3

4

5

Stack after rseverse:

5

4

3

2

1

Using temporary stack

class Program
{  
    static void Main(string[] args)
    {
        Stack<int> stack = new Stack<int>();
        stack.Push(5);
        stack.Push(4);
        stack.Push(3);
        stack.Push(2);
        stack.Push(1);

        Console.WriteLine("Stack before reverse:");
        foreach (int element in stack.ToArray())
        {
            Console.WriteLine(element);
        }

        stack = Reverse(stack);

        Console.WriteLine("Stack after rseverse:");
        foreach (int element in stack.ToArray())
        {
            Console.WriteLine(element);
        }

        Console.ReadLine();
    }

    static Stack<int> Reverse(Stack<int> stack)
    {
        Stack<int> temp = new Stack<int>();
        while (stack.Count > 0)
        {
            temp.Push(stack.Pop());
        }
        return temp;
    }
}

Output

Stack before reverse:

1

2

3

4

5

Stack after rseverse:

5

4

3

2

1

Like 0 People about 29 days ago

You are not loggedin, please login or signup to add comments:

Existing User

Login via:

New User



x