How to sort a stack using a temporary stack in Java

Key takeaways:
A stack is a data structure that follows the last in, first out (LIFO) principle.
Sorting a stack using a temporary stack involves rearranging elements by leveraging an additional stack for comparison and ordering.
The algorithm works by popping elements from the original stack, comparing them with the top of the temporary stack, and inserting them in the correct order.
The time complexity of the sorting algorithm in Java is $O(n²)$ in the worst case, where n is the number of elements. The space complexity is $O(n)$ due to the use of a temporary stack.

A stack is a data structure used in computer science that follows the Last In, First Out (LIFO) principle.

This means the last element added to the stack is the first one removed. Think of it like a stack of plates, where you can only add or remove the top plate. Sorting a stack is useful when organizing elements in a specific order, such as prioritizing tasks or preparing data for efficient retrieval.

A sorted stack makes performing operations like searching, comparing, or merging elements easier.

An algorithm for sorting a stack

The following steps are involved in the algorithm for sorting a stack using a temporary stack:

Create a temporary stack.
While the original stack is not empty:
1. Pop an element from the original stack.
2. While the temporary stack is not empty and the top element of the temporary stack is greater than the popped element:
  1. Pop elements from the temporary stack and return them to the original one.
3. Push the popped element to the temporary stack.
Once all elements are processed, move the items from the temporary stack back to the original stack.

import java.util.Stack;
public class StackSort {
    // Sorting a stack using a temporary stack
    public static void sortStack(Stack<Integer> stack) {
        Stack<Integer> tempStack = new Stack<>();
        while (!stack.isEmpty()) {
            int temp = stack.pop();
            while (!tempStack.isEmpty() && tempStack.peek() > temp) {
                stack.push(tempStack.pop());
            }
            tempStack.push(temp);
        }
        while (!tempStack.isEmpty()) {
            stack.push(tempStack.pop());
        }
    }
    // Main method to demonstrate sorting
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(5);
        stack.push(3);
        stack.push(8);
        stack.push(1);
        stack.push(2);
        System.out.println("Original Stack: " + stack);
        sortStack(stack);
        System.out.println("Sorted Stack: " + stack);
    }
}

Code explanation

Line 3: Defining the StackSort class.
Lines 9–17: Inside the outer loop, there is an inner loop that continues as long as the temporary stack (tempStack) is not empty and the top element of the temporary stack is greater than the current popped element (temp) from the original stack. This loop is responsible for finding the correct position for the current popped element in the temporary stack. The loop continues until the correct position for the temp element is found, i.e., until the top element of the temporary stack is less than or equal to temp.
Lines 19–21: Inside the loop, it pops the top element from the temporary stack (tempStack) using tempStack.pop() and then pushes this element onto the original stack (stack) using stack.push(). This operation effectively moves elements from the temporary stack to the original stack.
Line 26: This line declares and initializes a new stack of integers named stack.
Lines 27–31: Pushing integer elements onto the stack.
Line 35: Calls the sortStack method to sort the elements in the stack.

Time complexity

The time complexity of this sorting algorithm is $O(n^2)$ in the worst case, where $n$ is the number of elements in the stack. The space complexity is $O(n)$ as we use a temporary stack. The algorithm is efficient for small datasets but may not be the best choice for large datasets due to its quadratic time complexity.

Free AI Mock Interviews

Coding Interview

Coding PatternsFree Interview

Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.

System Design

YouTubeFree Interview

Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources

How to sort a stack using a temporary stack in Java

An algorithm for sorting a stack

Sorting a stack of code

Code explanation

Time complexity