Delete all even elements from a stack in Java

This tutorial demonstrates two methods for eliminating even numbers from a Java stack. Stacks, adhering to the Last-In-First-Out (LIFO) principle, present a unique challenge for this type of filtering. The techniques shown here are adaptable to other filtering scenarios beyond simply removing even numbers.

The Problem:

Given a stack of integers, write a Java program to remove all even numbers.

Example Inputs and Outputs:

• Input 1: [1, 2, 3, 4, 5] Output 1: [1, 3, 5]
• Input 2: [1, 7, 3, 11, 9] Output 2: [1, 7, 3, 11, 9] (no even numbers to remove)

Solution Approaches:

We'll explore two distinct approaches:

1. Using an Auxiliary Stack: This method employs a temporary stack to store odd numbers while iterating through the original stack.

2. Using Recursion: This recursive approach efficiently processes the stack, removing even numbers during the recursive calls.

Method 1: Auxiliary Stack

This approach involves these steps:

1. Create a temporary Stack (e.g., tempStack).
2. Iterate through the original stack, popping each element.
3. If the element is odd (check using the modulo operator %), push it onto tempStack.
4. Once the original stack is empty, transfer elements from tempStack back to the original stack.

Code Example (Auxiliary Stack):

<code class="language-java">import java.util.Stack;

public class RemoveEvenElements {
    public static void removeEven(Stack<integer> stack) {
        Stack<integer> tempStack = new Stack<>();
        while (!stack.isEmpty()) {
            int element = stack.pop();
            if (element % 2 != 0) {
                tempStack.push(element);
            }
        }
        while (!tempStack.isEmpty()) {
            stack.push(tempStack.pop());
        }
    }

    public static void main(String[] args) {
        Stack<integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        removeEven(stack);
        System.out.println(stack); // Output: [1, 3, 5]
    }
}</integer></integer></integer></code>

Time and Space Complexity (Auxiliary Stack):

• Time Complexity: O(n) - We iterate through the stack twice.
• Space Complexity: O(n) - We use an auxiliary stack of potentially the same size as the input stack.

Method 2: Recursion

This recursive solution elegantly handles the even number removal:

1. Base Case: If the stack is empty, return.
2. Pop the top element.
3. Recursively call the removeEven function to process the remaining stack.
4. After the recursive call, check if the popped element is odd. If it is, push it back onto the stack.

Code Example (Recursion):

<code class="language-java">import java.util.Stack;

public class RemoveEvenElements {
    public static void removeEven(Stack<integer> stack) {
        if (stack.isEmpty()) {
            return;
        }
        int element = stack.pop();
        removeEven(stack);
        if (element % 2 != 0) {
            stack.push(element);
        }
    }

    public static void main(String[] args) {
        Stack<integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        removeEven(stack);
        System.out.println(stack); // Output: [1, 3, 5]
    }
}</integer></integer></code>

Time and Space Complexity (Recursion):

• Time Complexity: O(n) - We recursively traverse the stack.
• Space Complexity: O(n) - The recursive call stack can grow to the size of the input stack in the worst case.

Conclusion:

Both methods effectively remove even numbers from a stack. The auxiliary stack approach is more straightforward, while the recursive approach offers a more concise and potentially slightly more efficient solution (depending on the JVM's optimization). The choice depends on personal preference and coding style. Remember that these techniques can be adapted to filter stacks based on various criteria.

The above is the detailed content of Delete all even elements from a stack in Java. For more information, please follow other related articles on the PHP Chinese website!