Reverse a stack without using extra space in O(n)

Problem Statement

The problem "Reverse a stack without using extra space in O(n)" states that you are given a stack data structure. Reverse the given stack without using extra O(n) space.

 

Example

5 4 3 2 1

1 2 3 4 5

80 60 10 20

20 10 60 80

Algorithm to Reverse a stack without using extra space in O(n)

 

- Create a class node containing an integer variable and a next pointer. Create a class constructor that accepts an integer as parameter. Assign the parameter value to the integer variable and set next pointer as null in the constructor.

- After that, create class stack and initialize a pointer top of type node in it.

- Create a function push() that accepts an integer as the parameter. Check if top is equal to null create a new node with given integer as data and store the new node in top and return.

- Else create a new node s with given integer as data. Update next of s as top and top is equal to s.

- Similarly, create a function pop(). Create a new node s and store the top in it. Update top as next of top and return the new node s.

- After that, create the function reverse(). Create three nodes representing previous, current and succeeding respectively. Update the current and previous node as the top node.

- Update current node as next of current node and the next of previous node as null.

 

www.tutorialcup.com/interview/stack/reverse-a-stack-witho...

Done