Posted on by Kalkicode
Code Stack

# Sort stack using another stack

The problem of Sort Stack using Another Stack involves sorting the elements of a given stack in ascending order using only one additional auxiliary stack. The task is to implement a function that takes an unsorted stack as input and returns a new stack containing the sorted elements.

## Problem Statement

Given an unsorted stack, implement a function `sortStack(Stack<Integer> s)` that takes this stack as input and returns a new stack containing the sorted elements in ascending order. The original stack should remain unchanged.

## Example

Consider the following stack:

``````10 <- Top
6
5
8
3
12
1
9
7
4
``````

After sorting the stack using another stack, the result should be:

``````1 <- Top
3
4
5
6
7
8
9
10
12
``````

## Idea to Solve the Problem

To sort the stack using another stack, we can use the following approach:

1. Create an auxiliary stack to store the sorted elements.
2. While the original stack is not empty, perform the following steps:
• Pop an element `temp` from the original stack.
• While the auxiliary stack is not empty and the top element of the auxiliary stack is less than `temp`, pop the top element from the auxiliary stack and push it back to the original stack.
• Push `temp` onto the auxiliary stack.
3. After all elements are processed, the auxiliary stack will contain the sorted elements in descending order.
4. To get the sorted elements in ascending order, we can simply pop elements from the auxiliary stack and push them back to the original stack.

## Algorithm

1. Create a new `Stack<Integer>` called `auxiliary` to store the sorted elements.
2. While the original stack `s` is not empty, do the following:
• Pop the top element `temp` from `s`.
• While `auxiliary` is not empty and the top element of `auxiliary` is less than `temp`, pop the top element from `auxiliary` and push it back to `s`.
• Push `temp` onto `auxiliary`.
3. The `auxiliary` stack now contains the sorted elements in descending order.
4. To get the sorted elements in ascending order, pop elements from `auxiliary` and push them back to `s`.
5. Return the `auxiliary` stack, which now contains the sorted elements in ascending order.

## Pseudocode

``````Function sortStack(Stack s):
Create a new Stack called auxiliary
While s is not empty:
Pop the top element temp from s
While auxiliary is not empty and auxiliary.peek() < temp:
Pop the top element from auxiliary and push it back to s
Push temp onto auxiliary
Return auxiliary
``````

## Time Complexity

The time complexity of the `sortStack` function is O(N^2), where N is the number of elements in the original stack. This is because for each element in the original stack, we may have to perform N operations in the worst case to maintain the sorted order in the auxiliary stack. Therefore, the overall time complexity of the sorting process is O(N^2).

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post