Sort a stack involves the task of arranging the elements within a stack in a specific order, either ascending or descending, using only a limited set of stack operations like push, pop, and peek. The goal is to achieve this sorting without utilizing extra data structures, such as arrays or lists. The challenge lies in creatively leveraging the Last-In-First-Out (LIFO) property of stacks to reorder the elements efficiently. This typically requires employing a second auxiliary stack. Elements are successively removed from the original stack and temporarily placed in the auxiliary stack in their appropriate sorted positions. Once the auxiliary stack is correctly sorted, the elements are returned to the original stack, resulting in it containing the elements in the desired sorted sequence.
Sorting a Stack Using a Stack
Illustration
Here’s a step-by-step explanation of how to sort a stack with a visual representation:
Step 1: Start with an unsorted stack.
Unsorted Stack:
| 6 |
| 3 |
| 8 |
| 1 |
| 5 |
| 2 |
| 4 |
| 7 |
| 9 |
|---|
Step 2: Create an empty auxiliary stack to help with sorting.
Unsorted Stack:
| 6 |
| 3 |
| 8 |
| 1 |
| 5 |
| 2 |
| 4 |
| 7 |
| 9 |
|---|
Auxiliary Stack:
|---|
Step 3: Pop elements from the unsorted stack and push them onto the auxiliary stack while maintaining sorted order. This means we’ll always push elements onto the auxiliary stack in ascending order.
Start by popping 6 from the unsorted stack and push it onto the auxiliary stack.
Unsorted Stack:
| 3 |
| 8 |
| 1 |
| 5 |
| 2 |
| 4 |
| 7 |
| 9 |
|---|
Auxiliary Stack:
| 6 |
|---|
Step 4: Continue popping from the unsorted stack and pushing onto the auxiliary stack while maintaining sorted order. Push 3 onto the auxiliary stack.
Unsorted Stack:
| 8 |
| 1 |
| 5 |
| 2 |
| 4 |
| 7 |
| 9 |
|---|
Auxiliary Stack:
| 6 |
| 3 |
|---|
Step 5: Repeat this process until the unsorted stack is empty.
Unsorted Stack:
| 8 |
| 1 |
| 5 |
| 2 |
| 4 |
| 7 |
| 9 |
|---|
Auxiliary Stack:
| 6 |
| 3 |
|---|
Unsorted Stack is now empty.
Step 6: At this point, the auxiliary stack is sorted in ascending order. To get the sorted stack, simply pop elements from the auxiliary stack and push them onto the unsorted stack.
Unsorted Stack (Sorted):
| 1 |
| 2 |
| 3 |
| 4 |
| 5 |
| 6 |
| 7 |
| 8 |
| 9 |
|---|
Auxiliary Stack:
|---|
Step 7: Now, the unsorted stack contains the elements sorted in ascending order.
Implementation
- Create an auxiliary stack to help with sorting.
- While the input stack is not empty, do the following:
- Pop the top element from the input stack and store it in a variable temp.
- While the auxiliary stack is not empty and the top element of the auxiliary stack is greater than temp, pop the top element from the auxiliary stack and push it onto the input stack.
- Push temp onto the auxiliary stack.
- After the sorting process is complete, the auxiliary stack will hold the elements in sorted order.
Here’s an example of the implementation of how to sort a stack in different programming languages:
C:
#include <stdio.h>
#include <stdlib.h> // For memory allocation and stack functions
// Structure to represent a stack
struct Stack {
int top;
unsigned capacity;
int* array;
};
// Function to create a stack of given capacity
struct Stack* createStack(unsigned capacity) {
struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
stack->capacity = capacity;
stack->top = -1;
stack->array = (int*)malloc(stack->capacity * sizeof(int));
return stack;
}
// Function to check if the stack is empty
int isEmpty(struct Stack* stack) {
return stack->top == -1;
}
// Function to push an element onto the stack
void push(struct Stack* stack, int item) {
stack->array[++stack->top] = item;
}
// Function to pop an element from the stack
int pop(struct Stack* stack) {
if (!isEmpty(stack)) {
return stack->array[stack->top--];
}
return -1; // Indicating an empty stack
}
// Function to sort a stack using another stack as an auxiliary
void sortStack(struct Stack* inputStack) {
struct Stack* auxStack = createStack(inputStack->capacity);
while (!isEmpty(inputStack)) {
int temp = pop(inputStack);
while (!isEmpty(auxStack) && auxStack->array[auxStack->top] > temp) {
push(inputStack, pop(auxStack));
}
push(auxStack, temp);
}
while (!isEmpty(auxStack)) {
push(inputStack, pop(auxStack));
}
free(auxStack->array);
free(auxStack);
}
int main() {
struct Stack* stack = createStack(6);
push(stack, 34);
push(stack, 3);
push(stack, 31);
push(stack, 98);
push(stack, 92);
push(stack, 23);
printf("Original Stack: ");
for (int i = 0; i <= stack->top; i++) {
printf("%d ", stack->array[i]);
}
printf("\n");
sortStack(stack);
printf("Sorted Stack: ");
for (int i = 0; i <= stack->top; i++) {
printf("%d ", stack->array[i]);
}
printf("\n");
free(stack->array);
free(stack);
return 0;
}
Output:
Original Stack: 34 3 31 98 92 23
Sorted Stack: 3 23 31 34 92 98
Explanation:
- In this code we are taking a stack, and we have implemented functions to create, push, and pop elements from the stack.
- The sortStack function takes an input stack and sorts the stack using an auxiliary stack.
- It iterates through the input stack while popping elements, and then it checks the auxiliary stack to find the correct position to push the current element.
- After the sorting is done, the auxiliary stack’s elements are moved back to the input stack to complete the sorting process.
- The main function demonstrates how to create a stack, push elements onto it, sort it, and then print the sorted result.
C++:
#include <iostream>
#include <stack>
void sortStack(std::stack<int>& inputStack) {
std::stack<int> auxStack;
while (!inputStack.empty()) {
int temp = inputStack.top();
inputStack.pop();
while (!auxStack.empty() && auxStack.top() > temp) {
inputStack.push(auxStack.top());
auxStack.pop();
}
auxStack.push(temp);
}
while (!auxStack.empty()) {
inputStack.push(auxStack.top());
auxStack.pop();
}
}
int main() {
std::stack<int> stack;
stack.push(34);
stack.push(3);
stack.push(31);
stack.push(98);
stack.push(92);
stack.push(23);
std::cout << "Original Stack: ";
std::stack<int> originalStack = stack;
while (!originalStack.empty()) {
std::cout << originalStack.top() << " ";
originalStack.pop();
}
std::cout << std::endl;
sortStack(stack);
std::cout << "Sorted Stack: ";
while (!stack.empty()) {
std::cout << stack.top() << " ";
stack.pop();
}
std::cout << std::endl;
return 0;
}
Output:
Original Stack: 34 3 31 98 92 23
Sorted Stack: 3 23 31 34 92 98
Explanation:
- The code uses the std::stack container class provided by the C++ Standard Library to represent the stacks.
- The sortStack function takes an input stack sort the stack using an auxiliary stack.
- It iterates through the input stack while popping elements, and then it checks the auxiliary stack to find the correct position to push the current element.
- After the sorting is done, the auxiliary stack’s elements are moved back to the input stack to complete the sorting process.
- The main function demonstrates how to create a stack, push elements onto it, sort it, and then print the original and sorted stacks.
Java:
import java.util.Stack;
public class SortStack {
public static void sortStack(Stack<Integer> inputStack) {
Stack<Integer> auxStack = new Stack<>();
while (!inputStack.isEmpty()) {
int temp = inputStack.pop();
while (!auxStack.isEmpty() && auxStack.peek() > temp) {
inputStack.push(auxStack.pop());
}
auxStack.push(temp);
}
while (!auxStack.isEmpty()) {
inputStack.push(auxStack.pop());
}
}
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(34);
stack.push(3);
stack.push(31);
stack.push(98);
stack.push(92);
stack.push(23);
System.out.print("Original Stack: ");
for (Integer element : stack) {
System.out.print(element + " ");
}
System.out.println();
sortStack(stack);
System.out.print("Sorted Stack: ");
for (Integer element : stack) {
System.out.print(element + " ");
}
System.out.println();
}
}
Output:
Original Stack: 34 3 31 98 92 23
Sorted Stack: 3 23 31 34 92 98
Explanation:
- The code uses the Stack class from the Java Collections framework to represent the stacks.
- The sortStack method takes an input stack and sorts it using an auxiliary stack.
- It iterates through the input stack while popping elements, and then it checks the auxiliary stack to find the correct position to push the current element.
- After the sorting is done, the auxiliary stack’s elements are moved back to the input stack to complete the sorting process.
- The main method demonstrates how to create a stack, push elements onto it, sort it, and then print the original and sorted stacks.
Python:
def sort_stack(stack):
aux_stack = []
while stack:
temp = stack.pop()
while aux_stack and aux_stack[-1] > temp:
stack.append(aux_stack.pop())
aux_stack.append(temp)
return aux_stack
# Example usage
input_stack = [34, 3, 31, 98, 92, 23]
sorted_stack = sort_stack(input_stack)
print("Sorted Stack:", sorted_stack)
Output:
Sorted Stack: [3, 23, 31, 34, 92, 98]
Explanation:
- The sort_stack function takes an input stack and sorts it using an auxiliary stack.
- It iterates through the input stack while popping elements, and then it checks the auxiliary stack to find the correct position to push the current element.
- After the sorting is done, the auxiliary stack’s elements are moved back to the input stack to complete the sorting process.
- The example usage demonstrates how to create an original stack, sort it using the sort_stack function, and then print both the original and sorted stacks.
Complexity Analysis
Time Complexity: O(N2)
- In the worst case, each element needs to be moved to the auxiliary stack for sorting.
- For each element, we may have to perform a maximum of N comparisons before finding the correct position in the auxiliary stack.
Space Complexity: O(N)
- The auxiliary stack is used to store the sorted elements, resulting in linear space usage proportional to the input size.
Sorting a Stack Using Recursion
Illustration
Using a recursive approach to sort a stack involves repeatedly removing elements from the stack while maintaining the order of the remaining elements. The sorted order is achieved by inserting the removed elements back into the stack at their correct positions.
Implementation
- If the stack is not empty, remove the top element using the pop() operation.
- Recursively sort the remaining elements of the stack.
- Insert the removed element back into the stack at its correct position.
- The base case of the recursion is an empty stack or a single-element stack.
Here’s an example of implementing stack sorting in different programming languages:
C:
#include <stdio.h>
#include <stdlib.h> // For memory allocation and stack functions
// Structure to represent a stack
struct Stack {
int top;
unsigned capacity;
int* array;
};
// Function to create a stack of given capacity
struct Stack* createStack(unsigned capacity) {
struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
stack->capacity = capacity;
stack->top = -1;
stack->array = (int*)malloc(stack->capacity * sizeof(int));
return stack;
}
// Function to check if the stack is empty
int isEmpty(struct Stack* stack) {
return stack->top == -1;
}
// Function to push an element onto the stack
void push(struct Stack* stack, int item) {
stack->array[++stack->top] = item;
}
// Function to pop an element from the stack
int pop(struct Stack* stack) {
if (!isEmpty(stack)) {
return stack->array[stack->top--];
}
return -1; // Indicating an empty stack
}
// Function to insert an element at its correct position in a sorted stack
void insertSorted(struct Stack* stack, int element) {
if (isEmpty(stack) || element > stack->array[stack->top]) {
push(stack, element);
} else {
int temp = pop(stack);
insertSorted(stack, element);
push(stack, temp);
}
}
// Function to recursively sort a stack using an auxiliary stack
void sortStack(struct Stack* inputStack) {
if (!isEmpty(inputStack)) {
int temp = pop(inputStack);
sortStack(inputStack);
insertSorted(inputStack, temp);
}
}
int main() {
struct Stack* stack = createStack(6);
push(stack, 34);
push(stack, 3);
push(stack, 31);
push(stack, 98);
push(stack, 92);
push(stack, 23);
printf("Original Stack: ");
for (int i = 0; i <= stack->top; i++) {
printf("%d ", stack->array[i]);
}
printf("\n");
sortStack(stack);
printf("Sorted Stack: ");
for (int i = 0; i <= stack->top; i++) {
printf("%d ", stack->array[i]);
}
printf("\n");
free(stack->array);
free(stack);
return 0;
}
Explanation:
- The code uses a structure to represent a stack, and functions are defined to create, push, and pop elements from the stack.
- The insertSorted function inserts an element at its correct position in a sorted stack.
- The sortStack function recursively sorts the input stack using an auxiliary stack and the insertSorted function.
- The main function demonstrates how to create a stack, push elements onto it, sort it, and then print the original and sorted stacks.
C++:
#include <iostream>
#include <stack>
void insertSorted(std::stack<int>& stack, int element) {
if (stack.empty() || element > stack.top()) {
stack.push(element);
} else {
int temp = stack.top();
stack.pop();
insertSorted(stack, element);
stack.push(temp);
}
}
void sortStack(std::stack<int>& inputStack) {
if (!inputStack.empty()) {
int temp = inputStack.top();
inputStack.pop();
sortStack(inputStack);
insertSorted(inputStack, temp);
}
}
int main() {
std::stack<int> stack;
stack.push(34);
stack.push(3);
stack.push(31);
stack.push(98);
stack.push(92);
stack.push(23);
std::cout << "Original Stack: ";
std::stack<int> originalStack = stack;
while (!originalStack.empty()) {
std::cout << originalStack.top() << " ";
originalStack.pop();
}
std::cout << std::endl;
sortStack(stack);
std::cout << "Sorted Stack: ";
while (!stack.empty()) {
std::cout << stack.top() << " ";
stack.pop();
}
std::cout << std::endl;
return 0;
}
Explanation:
- The code uses the std::stack container class from the C++ Standard Library to represent the stacks.
- The insertSorted function inserts an element at its correct position in a sorted stack.
- The sortStack function recursively sorts the input stack using an auxiliary stack and the insertSorted function.
- The main function demonstrates how to create a stack, push elements onto it, sort it, and then print the original and sorted stacks.
Java:
import java.util.Stack;
public class SortStackUsingRecursion {
public static void insertSorted(Stack<Integer> stack, int element) {
if (stack.isEmpty() || element > stack.peek()) {
stack.push(element);
} else {
int temp = stack.pop();
insertSorted(stack, element);
stack.push(temp);
}
}
public static void sortStack(Stack<Integer> inputStack) {
if (!inputStack.isEmpty()) {
int temp = inputStack.pop();
sortStack(inputStack);
insertSorted(inputStack, temp);
}
}
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(34);
stack.push(3);
stack.push(31);
stack.push(98);
stack.push(92);
stack.push(23);
System.out.print("Original Stack: ");
for (Integer element : stack) {
System.out.print(element + " ");
}
System.out.println();
sortStack(stack);
System.out.print("Sorted Stack: ");
for (Integer element : stack) {
System.out.print(element + " ");
}
System.out.println();
}
}
Explanation:
- The code uses the Stack class from the Java Collections framework to represent the stacks.
- The insertSorted method inserts an element at its correct position in a sorted stack.
- The sortStack method recursively sorts the input stack using an auxiliary stack and the insertSorted method.
- The main method demonstrates how to create a stack, push elements onto it, sort it, and then print the original and sorted stacks.
Output:
Original Stack: [34, 3, 31, 98, 92, 23]
Sorted Stack: [3, 23, 31, 34, 92, 98]
Complexity Analysis
Time Complexity: O(N2)
- The insert_sorted function, in the worst case, can involve inserting each element in the stack at its correct position, taking O(N) time.
- This operation is performed for each element, resulting in a total time complexity of O(N2).
Space Complexity: O(N)
- The recursive calls consume memory on the call stack, leading to a space complexity of O(N) due to the depth of the recursion.
FAQs
Q. What is the key idea behind sort a stack using recursion?
A. The key idea is to use recursion to remove elements from the stack while maintaining their order, then insert them back in sorted order.
Q. What’s the role of the insert_sorted function to sort a stack?
A. The insert_sorted function inserts an element at its correct sorted position in the stack using recursion.
Q. How is the sorting process achieved using recursion?
A. Elements are removed from the input stack and sorted recursively, then inserted back in their correct positions using the insert_sorted function.
Q. What’s the time complexity to sort a stack using recursion?
A. The time complexity is O(N2), where N is the number of elements in the stack, due to the repeated insertion and sorting operations.
Conclusion
- Sort a Stack Using Recursion involves leveraging recursive processes to arrange stack elements in a sorted order.
- Elements are removed from the stack and sorted recursively.
- The insert_sorted function inserts an element at its correct position using recursion.
- Sorted elements are then inserted back into the stack to achieve the sorted order.
- Recursion simplifies the sorting process by breaking it down into smaller steps.
- The technique utilizes the stack’s LIFO (Last-In-First-Out) structure to maintain order.
- Due to the repeated insertion and sorting operations using recursion.
- Recursive function calls consume memory on the call stack.
- While educational and insightful, this approach may not be the most efficient for large stacks due to its quadratic time complexity.
