# Sort a stack using a temporary stack

Given a stack of integers, sort it in ascending order using another temporary stack.

Examples:

```Input : [34, 3, 31, 98, 92, 23]
Output : [3, 23, 31, 34, 92, 98]

Input : [3, 5, 1, 4, 2, 8]
Output : [1, 2, 3, 4, 5, 8]
```

1. Create a temporary stack say tmpStack.
2. While input stack is NOT empty do this:
• Pop an element from input stack call it temp
• while temporary stack is NOT empty and top of temporary stack is greater than temp,
pop from temporary stack and push it to the input stack
• push temp in temporary stack
3. The sorted numbers are in tmpStack

Here is a dry run of above pseudo code.

```input: [34, 3, 31, 98, 92, 23]

Element taken out: 23
input: [34, 3, 31, 98, 92]
tmpStack: [23]

Element taken out: 92
input: [34, 3, 31, 98]
tmpStack: [23, 92]

Element taken out: 98
input: [34, 3, 31]
tmpStack: [23, 92, 98]

Element taken out: 31
input: [34, 3, 98, 92]
tmpStack: [23, 31]

Element taken out: 92
input: [34, 3, 98]
tmpStack: [23, 31, 92]

Element taken out: 98
input: [34, 3]
tmpStack: [23, 31, 92, 98]

Element taken out: 3
input: [34, 98, 92, 31, 23]
tmpStack: [3]

Element taken out: 23
input: [34, 98, 92, 31]
tmpStack: [3, 23]

Element taken out: 31
input: [34, 98, 92]
tmpStack: [3, 23, 31]

Element taken out: 92
input: [34, 98]
tmpStack: [3, 23, 31, 92]

Element taken out: 98
input: [34]
tmpStack: [3, 23, 31, 92, 98]

Element taken out: 34
input: [98, 92]
tmpStack: [3, 23, 31, 34]

Element taken out: 92
input: [98]
tmpStack: [3, 23, 31, 34, 92]

Element taken out: 98
input: []
tmpStack: [3, 23, 31, 34, 92, 98]

final sorted list: [3, 23, 31, 34, 92, 98]
```

## C++

 `  `  `// C++ program to sort a stack using an ` `// auxiliary stack. ` `#include ` `using` `namespace` `std; ` ` `  `// This function return the sorted stack ` `stack<``int``> sortStack(stack<``int``> &input) ` `{ ` `    ``stack<``int``> tmpStack; ` ` `  `    ``while` `(!input.empty()) ` `    ``{ ` `        ``// pop out the first element ` `        ``int` `tmp = input.top(); ` `        ``input.pop(); ` ` `  `        ``// while temporary stack is not empty and top ` `        ``// of stack is greater than temp ` `        ``while` `(!tmpStack.empty() && tmpStack.top() > tmp) ` `        ``{ ` `            ``// pop from temporary stack and push ` `            ``// it to the input stack ` `            ``input.push(tmpStack.top()); ` `            ``tmpStack.pop(); ` `        ``} ` ` `  `        ``// push temp in tempory of stack ` `        ``tmpStack.push(tmp); ` `    ``} ` ` `  `    ``return` `tmpStack; ` `} ` ` `  `// main function ` `int` `main() ` `{ ` `    ``stack<``int``> input; ` `    ``input.push(34); ` `    ``input.push(3); ` `    ``input.push(31); ` `    ``input.push(98); ` `    ``input.push(92); ` `    ``input.push(23); ` ` `  `    ``// This is the temporary stack ` `    ``stack<``int``> tmpStack = sortStack(input); ` `    ``cout << ````"Sorted numbers are: "````; ` ` `  `    ``while` `(!tmpStack.empty()) ` `    ``{ ` `        ``cout << tmpStack.top()<< ``" "``; ` `        ``tmpStack.pop(); ` `    ``} ` `} `

## Java

 `// Java program to sort a stack using  ` `// a auxiliary stack. ` `import` `java.util.*; ` ` `  `class` `SortStack ` `{ ` `    ``// This function return the sorted stack ` `    ``public` `static` `Stack sortstack(Stack  ` `                                             ``input) ` `    ``{ ` `        ``Stack tmpStack = ``new` `Stack(); ` `        ``while``(!input.isEmpty()) ` `        ``{ ` `            ``// pop out the first element ` `            ``int` `tmp = input.pop(); ` `         `  `            ``// while temporary stack is not empty and ` `            ``// top of stack is greater than temp ` `            ``while``(!tmpStack.isEmpty() && tmpStack.peek()  ` `                                                 ``> tmp) ` `            ``{ ` `                ``// pop from temporary stack and  ` `                ``// push it to the input stack ` `            ``input.push(tmpStack.pop()); ` `            ``} ` `             `  `            ``// push temp in tempory of stack ` `            ``tmpStack.push(tmp); ` `        ``} ` `        ``return` `tmpStack; ` `    ``} ` `     `  `    ``// Driver Code ` `    ``public` `static` `void` `main(String args[]) ` `    ``{ ` `        ``Stack input = ``new` `Stack(); ` `        ``input.add(``34``); ` `        ``input.add(``3``); ` `        ``input.add(``31``); ` `        ``input.add(``98``); ` `        ``input.add(``92``); ` `        ``input.add(``23``); ` `     `  `        ``// This is the temporary stack ` `        ``Stack tmpStack=sortstack(input); ` `        ``System.out.println(``"Sorted numbers are:"``); ` `     `  `        ``while` `(!tmpStack.empty()) ` `        ``{ ` `            ``System.out.print(tmpStack.pop()+``" "``); ` `        ``}  ` `    ``} ` `} ` `// This code is contributed by Danish Kaleem `

## Python3

 `# Python program to sort a  ` `# stack using auxiliary stack. ` ` `  `# This function return the sorted stack ` `def` `sortStack ( stack ): ` `    ``tmpStack ``=` `createStack() ` `    ``while``(isEmpty(stack) ``=``=` `False``): ` `         `  `        ``# pop out the first element ` `        ``tmp ``=` `top(stack) ` `        ``pop(stack) ` ` `  `        ``# while temporary stack is not ` `        ``# empty and top of stack is ` `        ``# greater than temp ` `        ``while``(isEmpty(tmpStack) ``=``=` `False` `and` `             ``int``(top(tmpStack)) > ``int``(tmp)): ` `             `  `            ``# pop from temporary stack and ` `            ``# push it to the input stack ` `            ``push(stack,top(tmpStack)) ` `            ``pop(tmpStack) ` ` `  `        ``# push temp in tempory of stack ` `        ``push(tmpStack,tmp) ` `     `  `    ``return` `tmpStack ` ` `  `# Below is a complete running  ` `# program for testing above ` `# function. ` ` `  `# Function to create a stack.  ` `# It initializes size of stack ` `# as 0 ` `def` `createStack(): ` `    ``stack ``=` `[] ` `    ``return` `stack ` ` `  `# Function to check if  ` `# the stack is empty ` `def` `isEmpty( stack ): ` `    ``return` `len``(stack) ``=``=` `0` ` `  `# Function to push an  ` `# item to stack ` `def` `push( stack, item ): ` `    ``stack.append( item ) ` ` `  `# Function to get top  ` `# item of stack ` `def` `top( stack ): ` `    ``p ``=` `len``(stack) ` `    ``return` `stack[p``-``1``] ` ` `  `# Function to pop an  ` `# item from stack ` `def` `pop( stack ): ` ` `  `    ``# If stack is empty ` `    ``# then error ` `    ``if``(isEmpty( stack )): ` `        ``print``(``"Stack Underflow "``) ` `        ``exit(``1``) ` ` `  `    ``return` `stack.pop() ` ` `  `# Function to print the stack ` `def` `prints(stack): ` `    ``for` `i ``in` `range``(``len``(stack)``-``1``, ``-``1``, ``-``1``): ` `        ``print``(stack[i], end ``=` `' '``) ` `    ``print``() ` ` `  `# Driver Code ` `stack ``=` `createStack() ` `push( stack, ``str``(``34``) ) ` `push( stack, ``str``(``3``) ) ` `push( stack, ``str``(``31``) ) ` `push( stack, ``str``(``98``) ) ` `push( stack, ``str``(``92``) ) ` `push( stack, ``str``(``23``) ) ` ` `  `print``(``"Sorted numbers are: "``) ` `sortedst ``=` `sortStack ( stack ) ` `prints(sortedst) ` ` `  `# This code is contributed by ` `# Prasad Kshirsagar `

/div>

## C#

 `// C# program to sort a stack using  ` `// a auxiliary stack.  ` `using` `System; ` `using` `System.Collections.Generic; ` ` `  `class` `GFG ` `{ ` `// This function return the sorted stack  ` `public` `static` `Stack<``int``> sortstack(Stack<``int``> input) ` `{ ` `    ``Stack<``int``> tmpStack = ``new` `Stack<``int``>(); ` `    ``while` `(input.Count > 0) ` `    ``{ ` `        ``// pop out the first element  ` `        ``int` `tmp = input.Pop(); ` ` `  `        ``// while temporary stack is not empty and  ` `        ``// top of stack is greater than temp  ` `        ``while` `(tmpStack.Count > 0 && tmpStack.Peek() > tmp) ` `        ``{ ` `            ``// pop from temporary stack and  ` `            ``// push it to the input stack  ` `            ``input.Push(tmpStack.Pop()); ` `        ``} ` ` `  `        ``// push temp in tempory of stack  ` `        ``tmpStack.Push(tmp); ` `    ``} ` `    ``return` `tmpStack; ` `} ` ` `  `// Driver Code  ` `public` `static` `void` `Main(``string``[] args) ` `{ ` `    ``Stack<``int``> input = ``new` `Stack<``int``>(); ` `    ``input.Push(34); ` `    ``input.Push(3); ` `    ``input.Push(31); ` `    ``input.Push(98); ` `    ``input.Push(92); ` `    ``input.Push(23); ` ` `  `    ``// This is the temporary stack  ` `    ``Stack<``int``> tmpStack = sortstack(input); ` `    ``Console.WriteLine(``"Sorted numbers are:"``); ` ` `  `    ``while` `(tmpStack.Count > 0) ` `    ``{ ` `        ``Console.Write(tmpStack.Pop() + ``" "``); ` `    ``} ` `} ` `} ` ` `  `// This code is contributed by Shrikant13 `

Output:

```Sorted numbers are:
98 92 34 31 23 3
```

Microsoft

code