Changing the Order of elements in a Stack so that all Odd numbers go before Even numbers

KYR4 0
Viewed 59

I am looking for a way to change the order of the elements in a Stack, so that the even numbers go after odd numbers.

For example, the following stack:

5, 2, 6, 7, 1, 4, 3

Becomes:

5, 7, 1, 3, 2, 6, 4

enter image description here

Here is my current code. I'm stuck on finding out how to change the order :

public static void main(String[] args) {

    Stack<Integer> p = new Stack<>();

    p.push(3);
    p.push(4);
    p.push(1);
    p.push(7);
    p.push(6);
    p.push(2);
    p.push(5);
    
    ListIterator<Integer> ListIterator = p.listIterator(p.size());  
     
    while (ListIterator.hasPrevious())  {  
        Integer i = ListIterator.previous();  
        System.out.println(i);  
    } 
}
stack java algorithm
3 Answers

Stack is subclass of AbstractList, so you can use List.sort() by providing custom Comparator.

public class Temp {

    public static void main(String[] args) {
        Stack<Integer> p = new Stack<>();

        p.push(3);
        p.push(4);
        p.push(1);
        p.push(7);
        p.push(6);
        p.push(2);
        p.push(5);

        p.sort((a, b) -> {
            if (a % 2 == 0 && b % 2 == 0) {
                return 0;
            }
            if (a % 2 == 0) {
                return 1;
            }
            if (b % 2 == 0) {
                return -1;
            }
            return 0;
        });
        System.out.println(p);
    }
}

For the initial stack of - [3, 4, 1, 7, 6, 2, 5] this results in - [3, 1, 7, 5, 4, 6, 2].

Chaosfire0

There are many ways to accomplish the task of separating odd and even elements.

I suspect that the purpose of this challenge is getting familiar with the Stack data structure and its basic operations.

So here's a solution which utilizes two additional Stacks, one to accumulate the odd elements, another for storing even elements.

The initial stack is being empty out and its elements are being distributed between two other stacks. Now have odd and even numbers separated, and the only thing left is to join the data.

The time complexity of this solution is linear O(n). It is more performant than sorting the data, which would have a linear-logarithmic time complexity O(n log n).

That how it can be implemented:

Stack<Integer> numbers = new Stack<>();
        
numbers.push(3);
numbers.push(4);
numbers.push(1);
numbers.push(7);
numbers.push(6);
numbers.push(2);
numbers.push(5);
        
Stack<Integer> odd = new Stack<>();
Stack<Integer> even = new Stack<>();
        
while (!numbers.isEmpty()) {
    Integer next = numbers.pop();
    if (next % 2 == 0) even.push(next);
    else odd.push(next);
}
        
numbers.addAll(odd);
numbers.addAll(even);
    
System.out.println(numbers);

Output:

[5, 7, 1, 3, 2, 6, 4]

Note:

  • Class Stack is legacy, and shouldn't be used (unless it's a requirement of your assignment). When you need an implementation of the stack data structure in Java the recommended alternative is to use implementations of the Deque interface.
  • Try to use more meaningful names than p. It's a good habit because it makes the code easier to read and maintain. Single-letter variable are acceptable only rare cases, like variables defined within a for-loop. Also see Java Language Naming Conventions.
Alexander Ivanchenko0

Compare the negated (so 1 orders before 0) difference between modulo 2:

p.sort((a, b) -> b % 2 - a % 2);

See live demo.

Bohemian0
Related