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

Reverse a Stack without using recursion and extra space. Even the functional Stack is not allowed.

Examples:

```Input : 1->2->3->4
Output : 4->3->2->1

Input :  6->5->4
Output : 4->5->6
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

We have discussed a way of reversing a string in below post.

Reverse a Stack using Recursion

The above solution requires O(n) extra space. We can reverse a string in O(1) time if we internally represent the stack as a linked list. Reverse a stack would require a reversing a linked list which can be done with O(n) time and O(1) extra space.

Note that push() and pop() operations still take O(1) time.

## C++

 `// CPP program to implement Stack  ` `// using linked list so that reverse ` `// can be done with O(1) extra space. ` `#include ` `using` `namespace` `std; ` ` `  `class` `StackNode { ` `    ``public``: ` `    ``int` `data; ` `    ``StackNode *next; ` `     `  `    ``StackNode(``int` `data) ` `    ``{ ` `        ``this``->data = data; ` `        ``this``->next = NULL; ` `    ``} ` `}; ` ` `  `class` `Stack { ` `     `  `    ``StackNode *top; ` `     `  `    ``public``: ` `     `  `    ``// Push and pop operations ` `    ``void` `push(``int` `data) ` `    ``{ ` `        ``if` `(top == NULL) { ` `            ``top = ``new` `StackNode(data); ` `            ``return``; ` `        ``} ` `        ``StackNode *s = ``new` `StackNode(data); ` `        ``s->next = top; ` `        ``top = s; ` `    ``} ` `     `  `    ``StackNode* pop() ` `    ``{ ` `        ``StackNode *s = top; ` `        ``top = top->next; ` `        ``return` `s; ` `    ``} ` ` `  `    ``// prints contents of stack ` `    ``void` `display() ` `    ``{ ` `        ``StackNode *s = top; ` `        ``while` `(s != NULL) { ` `            ``cout << s->data << ``" "``; ` `            ``s = s->next; ` `        ``} ` `        ``cout << endl; ` `    ``} ` ` `  `    ``// Reverses the stack using simple ` `    ``// linked list reversal logic. ` `    ``void` `reverse() ` `    ``{ ` `        ``StackNode *prev, *cur, *succ; ` `        ``cur = prev = top; ` `        ``cur = cur->next; ` `        ``prev->next = NULL; ` `        ``while` `(cur != NULL) { ` ` `  `            ``succ = cur->next; ` `            ``cur->next = prev; ` `            ``prev = cur; ` `            ``cur = succ; ` `        ``} ` `        ``top = prev; ` `    ``} ` `}; ` ` `  `// driver code ` `int` `main() ` `{ ` `    ``Stack *s = ``new` `Stack(); ` `    ``s->push(1); ` `    ``s->push(2); ` `    ``s->push(3); ` `    ``s->push(4); ` `    ``cout << ``"Original Stack"` `<< endl;; ` `    ``s->display(); ` `    ``cout << endl; ` `     `  `    ``// reverse ` `    ``s->reverse(); ` ` `  `    ``cout << ``"Reversed Stack"` `<< endl; ` `    ``s->display(); ` `     `  `    ``return` `0; ` `} ` `// This code is contribute by Chhavi. `

## Java

 `// Java program to implement Stack using linked ` `// list so that reverse can be done with O(1)  ` `// extra space. ` `class` `StackNode { ` `    ``int` `data; ` `    ``StackNode next; ` `    ``public` `StackNode(``int` `data) ` `    ``{ ` `        ``this``.data = data; ` `        ``this``.next = ``null``; ` `    ``} ` `} ` ` `  `class` `Stack { ` `    ``StackNode top; ` ` `  `    ``// Push and pop operations ` `    ``public` `void` `push(``int` `data) ` `    ``{ ` `        ``if` `(``this``.top == ``null``) { ` `            ``top = ``new` `StackNode(data); ` `            ``return``; ` `        ``} ` `        ``StackNode s = ``new` `StackNode(data); ` `        ``s.next = ``this``.top; ` `        ``this``.top = s; ` `    ``} ` `    ``public` `StackNode pop() ` `    ``{ ` `        ``StackNode s = ``this``.top; ` `        ``this``.top = ``this``.top.next; ` `        ``return` `s; ` `    ``} ` ` `  `    ``// prints contents of stack ` `    ``public` `void` `display() ` `    ``{ ` `        ``StackNode s = ``this``.top; ` `        ``while` `(s != ``null``) { ` `            ``System.out.print(s.data + ``" "``); ` `            ``s = s.next; ` `        ``} ` `        ``System.out.println(); ` `    ``} ` ` `  `    ``// Reverses the stack using simple ` `    ``// linked list reversal logic. ` `    ``public` `void` `reverse() ` `    ``{ ` `        ``StackNode prev, cur, succ; ` `        ``cur = prev = ``this``.top; ` `        ``cur = cur.next; ` `        ``prev.next = ``null``; ` `        ``while` `(cur != ``null``) { ` ` `  `            ``succ = cur.next; ` `            ``cur.next = prev; ` `            ``prev = cur; ` `            ``cur = succ; ` `        ``} ` `        ``this``.top = prev; ` `    ``} ` `} ` ` `  `public` `class` `reverseStackWithoutSpace { ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``Stack s = ``new` `Stack(); ` `        ``s.push(``1``); ` `        ``s.push(``2``); ` `        ``s.push(``3``); ` `        ``s.push(``4``); ` `        ``System.out.println(``"Original Stack"``); ` `        ``s.display(); ` ` `  `        ``// reverse ` `        ``s.reverse(); ` ` `  `        ``System.out.println(``"Reversed Stack"``); ` `        ``s.display(); ` `    ``} ` `} `

## C#

 `// C# program to implement Stack using linked ` `// list so that reverse can be done with O(1)  ` `// extra space. ` `using` `System;  ` ` `  `public` `class` `StackNode ` `{ ` `    ``public` `int` `data; ` `    ``public` `StackNode next; ` `    ``public` `StackNode(``int` `data) ` `    ``{ ` `        ``this``.data = data; ` `        ``this``.next = ``null``; ` `    ``} ` `} ` ` `  `public` `class` `Stack  ` `{ ` `    ``public` `StackNode top; ` ` `  `    ``// Push and pop operations ` `    ``public` `void` `push(``int` `data) ` `    ``{ ` `        ``if` `(``this``.top == ``null``) ` `        ``{ ` `            ``top = ``new` `StackNode(data); ` `            ``return``; ` `        ``} ` `        ``StackNode s = ``new` `StackNode(data); ` `        ``s.next = ``this``.top; ` `        ``this``.top = s; ` `    ``} ` `     `  `    ``public` `StackNode pop() ` `    ``{ ` `        ``StackNode s = ``this``.top; ` `        ``this``.top = ``this``.top.next; ` `        ``return` `s; ` `    ``} ` ` `  `    ``// prints contents of stack ` `    ``public` `void` `display() ` `    ``{ ` `        ``StackNode s = ``this``.top; ` `        ``while` `(s != ``null``)  ` `        ``{ ` `            ``Console.Write(s.data + ``" "``); ` `            ``s = s.next; ` `        ``} ` `        ``Console.WriteLine(); ` `    ``} ` ` `  `    ``// Reverses the stack using simple ` `    ``// linked list reversal logic. ` `    ``public` `void` `reverse() ` `    ``{ ` `        ``StackNode prev, cur, succ; ` `        ``cur = prev = ``this``.top; ` `        ``cur = cur.next; ` `        ``prev.next = ``null``; ` `        ``while` `(cur != ``null``) ` `        ``{ ` `            ``succ = cur.next; ` `            ``cur.next = prev; ` `            ``prev = cur; ` `            ``cur = succ; ` `        ``} ` `        ``this``.top = prev; ` `    ``} ` `} ` ` `  `public` `class` `reverseStackWithoutSpace  ` `{ ` `    ``// Driver code ` `    ``public` `static` `void` `Main(String []args) ` `    ``{ ` `        ``Stack s = ``new` `Stack(); ` `        ``s.push(1); ` `        ``s.push(2); ` `        ``s.push(3); ` `        ``s.push(4); ` `        ``Console.WriteLine(``"Original Stack"``); ` `        ``s.display(); ` ` `  `        ``// reverse ` `        ``s.reverse(); ` ` `  `        ``Console.WriteLine(``"Reversed Stack"``); ` `        ``s.display(); ` `    ``} ` `} ` ` `  `// This code is contributed by Arnab Kundu `

Output:

```Original Stack
4 3 2 1
Reversed Stack
1 2 3 4
```