Java palindrome checker using queue AND restoring queue to original state

Question

I've written a long and complicated method checking if a list of elements in a Queue is a palindrome. I know it can be improved, but my goal right now is to get it to past all the tests in practice-it. I've passed 9 out of 10, but the only test I can't seem to pass is the odd elements/not a palindrome.

For example: front [5, 10, -1, 4, 3, 2, 2, 4, -1, 10, 5] back. Expected Output should be FALSE. My Output is TRUE.

Also, unlike the other tests, the elements in the Queue aren't being displayed. Unlike the previous questions asked that are similar to this problem, my Queue must be restored to its original state. Here is my code so far:

    public static boolean isPalindrome(Queue<Integer> q) {
        Stack<Integer> s = new Stack<Integer>();
        int size = q.size();
        int extra = 0;

        if(q.isEmpty()) 
            return true;
        else 
            if (size % 2 == 0) {
                for (int i = 0; i < size / 2; i++) {
                    s.push(q.remove());
                }      
            while (!s.isEmpty()) {  // While Stack is not empty:
                if (s.peek() != q.peek()) {
                    int first = s.pop();
                    s.push(q.remove());
                    s.push(first);

                    while (!q.isEmpty())
                        s.push(q.remove());

                    while (!s.isEmpty()) {
                        q.add(s.pop());
                    }
                    return false;
                }
            else {
                while (!q.isEmpty())
                    s.push(q.remove());

                while (!s.isEmpty()) {
                    q.add(s.pop());  // Restore Queue to original order
                }
                return true;
            }
        }

        for (int k = 0; k < size / 2; k++) {
            q.add(q.remove());
            s.push(q.remove());
        }

        for (int l = 0; l < size / 2; l++)
            s.push(q.remove());

        while (!s.isEmpty())
            q.add(s.pop());
    }
    return true;
}

If anyone has a hard time reading this or can suggest a way to make it less convoluted as well, I would appreciate that. Thank you, and sorry again for the bloated code.

Answer 1

Cruncher I went your way to copy the Queue. I was over-complicating the code by worrying about odd size Queues. I'd vote up your answer because that really helped, but not enough frequent flyer miles.

All it really took was throwing out the clunker I first posted, which is sometimes the best thing.

Anyway, here it is. The for-loop loads up the stack, making the copy Cruncher mentioned. The while-loop simply peeks and then reloads the Queue while popping the stack. Much cleaner, and it took me a couple of minutes after asking the right questions.

public static boolean isPalindrome(Queue<Integer> q) {
    Stack<Integer> s = new Stack<Integer>();
    int size = q.size();
    boolean palindrome = true;

    for (int i = 0; i < size; i++) {
        int value = q.peek();
        s.push(value);
        q.remove();
        q.add(value);
    }

    while (!s.isEmpty()) {
         if (s.peek() != q.peek())
            palindrome = false;
         s.pop();
         q.add(q.remove());
    }
    return palindrome;
}

Answer 2

Why not use the simple algorithm which doesn't care if it destroys the Queue in the process, but copy the Queue as the first step?

public static boolean isPalindrome(Queue<Integer> q) {
    return isPalindromeDestructive(copyQueue(q));
}

private static boolean isPalindromeDestructive(Queue<Integer> q) {
    //Destructive algorithm that treats q as disposable.
}

private static Queue<Integer> copyQueue(Queue<Integer> q) {
    return new LinkedList<Integer>(q);
}

You can implement copyQueue however you want, but this works.