CODEWITHSUNDEEP
javagenerics
mpenkov
mpenkov

Reputation: 21906

How can I make this code work with generics?

I have some code that sorts a stack using only another stack (it's an interview question). The code itself seems to work. I'd like to implement it using generics, so that any kind of stack is sortable, under the following conditions:

  1. The sort method remains static (I'd like to avoid parameterizing the entire class)
  2. I can use native comparator operators (like <) - I guess the parameterized type needs to implement Comparable.

Is this possible?

Here's the code. 

import java.util.Stack;
public class StackSort {
    static void sort(Stack<Integer> stack) {
        Stack<Integer> tmp = new Stack<Integer>();
        for (;;) {
            int nswaps = 0;
            while (!stack.isEmpty()) {
                Integer curr = stack.pop();
                if (!stack.isEmpty() && curr < stack.peek()) {
                    Integer next = stack.pop();
                    tmp.push(next);
                    tmp.push(curr);
                    ++nswaps;
                } else {
                    tmp.push(curr);
                }
            }
            while (!tmp.isEmpty()) {
                stack.push(tmp.pop());
            }
            if (nswaps == 0) {
                break;
            }
        }
    }
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(6);
        stack.push(4);
        stack.push(11);
        stack.push(8);
        stack.push(7);
        stack.push(3);
        stack.push(5);
        System.out.println(stack);
        StackSort.sort(stack);
        System.out.println(stack);
    }
}

Upvotes: 0

Views: 133

Answers (2)

Martijn Courteaux
Martijn Courteaux

Reputation: 68847

Using comparator operators on Objects (wrapped primitives or not) is not possible in Java. C++ support such a possibility. However, you can create a workaround by forceing the parameter type to implement Comparable. Your signature should look like this:

public <T extends Comparable<? super T>> static void sort(Stack<T> stack)

And to compare, use compareTo instead of native operators (which is not possible in Java):

obj1.compareTo(obj2)

Upvotes: 2

fgwe84
fgwe84

Reputation: 168

You are on the right way by mentioning Comparable.

Your method can be

static <T extends Comparable<T>>void sort(Stack<T> stack) {

And the comparison curr < stack.peek() replace by

curr.compareTo(stack.peek()) < 0

Upvotes: 3

Related Questions