Geek Answers Handbook

Comparing stack and queue queues in Java (palindromes)

Full disclosure: this is for assignment, so please do not post actual code solutions!

I have an assignment that requires me to take a string from a user and pass it onto the stack and queue, and then use these two to compare characters to determine if the string is a palindrome. I have a program written, but somewhere there is some kind of logical error. Here is the relevant code:

public static void main(String[] args) { UserInterface ui = new UserInterface(); Stack stack = new Stack(); Queue queue = new Queue(); String cleaned = new String(); boolean palindrome = true; ui.setString("Please give me a palindrome."); cleaned = ui.cleanString(ui.getString()); for (int i = 0; i < cleaned.length(); ++i) { stack.push(cleaned.charAt(i)); queue.enqueue(cleaned.charAt(i)); } while (!stack.isEmpty() && !queue.isEmpty()) { if (stack.pop() != queue.dequeue()) { palindrome = false; } } if (palindrome) { System.out.printf("%s is a palindrome!", ui.getString()); } else System.out.printf("%s is not a palindrome :(", ui.getString()); stack.dump(); queue.clear(); } public class Stack { public void push(char c) { c = Character.toUpperCase(c); Node oldNode = header; header = new Node(); header.setData(c); header.setNext(oldNode); } public char pop() { Node temp = new Node(); char data; if (isEmpty()) { System.out.printf("Stack Underflow (pop)\n"); System.exit(0); } temp = header; data = temp.getData(); header = header.getNext(); return data; } } public class Queue { public void enqueue(char c) { c = Character.toUpperCase(c); Node n = last; last = new Node(); last.setData(c); last.setNext(null); if (isEmpty()) { first = last; } else n.setNext(last); } public char dequeue() { char data; data = first.getData(); first = first.getNext(); return data; } } public String cleanString(String s) { return s.replaceAll("[^A-Za-z0-9]", ""); }

Basically, when I run my code through the debugger in Eclipse, my pop and dequeue methods only display for selecting specific alphanumeric characters. I use replaceAll("[^A-Za-z0-9]", "") to "clear" the user string of any non-alphanumeric characters (!,?, &, Etc.). When I say that he selects only certain characters, there seems to be no picture that I can distinguish. Any ideas?

+4
source share
2 answers

Your general algorithm is working correctly, assuming your queue and stack are correct (I tried this using the Deque implementations found in jdk). Since your job includes data structures, I pretty much just took your main logic and replaced the ArrayDequeue data structures, so I don’t feel like I answer for you.

  String word = "ooffoo"; word = word.replaceAll("[^A-Za-z0-9]", ""); Deque<Character> stack = new ArrayDeque<Character>(word.length()); Deque<Character> queue = new ArrayDeque<Character>(word.length()); for (char c : word.toCharArray()) { stack.push(c); queue.add(c); } boolean pal = true; while (! stack.isEmpty() && pal == true) { if (! stack.pop().equals(queue.remove())) { pal = false; } } System.out.println(pal);
0
source

I would recommend using a debugger to see what exactly was being compared, or at least spit out some print lines:

 while (!stack.isEmpty() && !queue.isEmpty()) { Character sc = stack.pop(); Character qc = queue.dequeue(); System.out.println(sc + ":" + qc); if (sc != qc) { palindrome = false; } }
0
source

More articles:


All Articles