The palindrome problem can be solved using a queue and a stack, putting characters simultaneously into a queue and onto a stack as the word or phrase is scanned character by character.

Your program must accept a word or phrase as input and then use a queue and a stack to determine whether the input is a palindrome. It should then output the original phrase and the results declaring whether it is or is not a palidrome. If you choose this problem then you must use a queue and a stack data structure to solve it. Some preprocessing of the word or phrase is allowed to force it all to the same case and eliminate spacing, punctuation, or other non-letter characters.

One way to write this program download and modify the textbook authors Stack and Queue data structure code. You would then write a class that used those structures. Another way to write this program is to use the Java API Stack class and one of the Java API classes that implement the Java API Queue interface directly in your application.

public class SinglyLinkedListIterator //extends SinglyLinkedList (see Fig. 4.15) { private Node h; // list header public Iterator i; public SinglyLinkedListIterator() { h = new Node(); // dummy node i = new Iterator(); h.l = null; h.next = null; } public boolean insert(Listing2 newListing) { Node n = new Node(); if(n == null) // out of memory return false; else { n.next = h.next; h.next = n; n.l = newListing.deepCopy(); return true; } } public Listing2 fetch(String targetKey) { Node p = h.next; while (p != null && !(p.l.compareTo(targetKey) == 0)) { p = p.next; } if(p != null) return p.l.deepCopy(); else return null; } public boolean delete(String targetKey) { Node q = h; Node p = h.next; while (p != null && !(p.l.compareTo(targetKey) == 0)) { q = p; p = p.next; } if(p != null) { q.next = p.next; return true; } else return false; } public boolean update(String targetKey, Listing2 newListing) { if(delete(targetKey) == false) return false; else if(insert(newListing) == false) return false; return true; } public void showAll() { Node p = h.next; while (p != null) //continue to traverse the list { System.out.println(p.l.toString( )); p = p.next; } } public class Node { private Listing2 l; private Node next; public Node() { } }// end of inner class Node public class Iterator { private Node ip; public Iterator() { ip = h; } public void reset() { ip = h; } public boolean hasNext() { if(ip.next != null) return true; else return false; } public Listing2 next() { ip = ip.next; return ip.l.deepCopy(); } public void set(Listing2 newListing) { ip.l = newListing.deepCopy(); } }// end of inner class Iterator }// end class SinglyLinkedListIterator 

public class SllExternalIterator { private NewNode h; public SllExternalIterator() { h = new NewNode(); h.next = null; h.l = null; } public boolean insert(Listing2 newListing) { NewNode n = new NewNode(); if(n == null) // out of memory return true; else { n.l = newListing.deepCopy(); n.next = h.next; h.next = n; return false; } }//end insert method public Listing2 fetch(String targetKey) { NewNode p = h.next; while (p != null && p.l.compareTo(targetKey) != 0) { p = p.next; } if(p == null) return null; else { return p.l.deepCopy(); } }// end of fetch public boolean delete(String targetKey) { NewNode q = h; NewNode p = q.next; while (p != null && p.l.compareTo(targetKey) != 0) { q = q.next; p = p.next; } if(p == null) return true; else { q.next = p.next; return false; } }// end of delete method public boolean update(String targetKey, Listing2 newListing) {if(delete(targetKey) == true) return true; else if(insert(newListing) == true) return true; return false; }//end of update public void showAll() { NewNode p = h.next; while (p != null) { System.out.println(p.l); // Java automatically uses the toString method p = p.next; } }// end of showAll method public SllIterator iterator() { return ( new SllIterator(h) ) ; } }// end of class SllExternalIterator 

public class SllIterator //implements Iterator {private NewNode ip; private NewNode h; public SllIterator(NewNode h) { ip = h; this.h = h; } public void reset() { ip = h; } public boolean hasNext() { if(ip.next == null) return false; else return true; }; public Listing2 next() { ip = ip.next; return ip.l.deepCopy(); } public void set(Listing2 newListing) { ip.l = newListing.deepCopy(); } }// end of the class SllIterator; 

public class Listing { private String name; // key field private String address; private String number; public Listing(String n, String a, String num ) { name = n; address = a; number = num; } public String toString( ) { return("Name is " + name + " Address is " + address + " Number is " + number + " "); } public Listing deepCopy( ) { Listing clone = new Listing(name, address, number); return clone; } public int compareTo(String targetKey) { return(name.compareTo(targetKey)); } public void setAddress(String a) // coded to demonstrate encapsulation { address = a; } }// end of class Listing 

public class Listing2 { private String name; // key field private String address; private String number; public Listing2(String n, String a, String num ) { name = n; address = a; number = num; } public String toString( ) { return("Name is " + name + " Address is " + address + " Number is " + number + " "); } public Listing2 deepCopy( ) { Listing2 clone = new Listing2(name, address, number); return clone; } public int compareTo(String targetKey) { return(name.compareTo(targetKey)); } public String getNumber( ) // fetch the phone number { return number; } // end of getNumber method public void setNumber(String n) // change the phone number { number = n; } // end of setNumber method }// end of Listing2 Class 

import java.util.*; public class MainAPILinkedListAndIteratorClasses { public static void main(String args[ ] ) { LinkedList DataBase = new LinkedList(); Listing2 b; Listing2 a; Listing2 bill = new Listing2("Bill", "1st Avenue", "123 4567"); Listing2 al = new Listing2("Al", "2nd Avenue", "456 3232"); // declare a ListIterator attached to the structure Database ListIterator i = DataBase.listIterator(); // add two phone listings to the data set i.add(bill); i.add(al); // return the iterator to the front of the list while (i.hasPrevious()) i.previous(); // fetch back the two listings and output them a = (Listing2) i.next(); b = (Listing2) i.next(); System.out.println(a); System.out.println(b); // demonstrate the structure is un-encapsulated // change Bill's phone number to 999 9999 bill.setNumber("999 9999"); // return the iterator to the front of the list while (i.hasPrevious()) i.previous(); // fetch and output Williams listing from the structure a = (Listing2) i.next(); System.out.println(a); } } 

public class MainSinlyLinkedListIterator { public static void main(String[] args) { SinglyLinkedListIterator boston = new SinglyLinkedListIterator(); String number; Listing2 l1 = new Listing2("Bill", "1st Avenue", "123 4567" ); Listing2 l2 = new Listing2("Al", "2nd Avenue", "456 3232"); Listing2 l3 = new Listing2("Mike", "3rd Avenue", "333 3333"); boston.insert(l1); // test insert boston.insert(l2); boston.insert(l3); // output all the listings using the iterator, i while(boston.i.hasNext()) { System.out.println(boston.i.next( )); // Java automatically invokes toString } // add an area code to all the listings using the iterator, i boston.i.reset(); while(boston.i.hasNext()) { l1 = boston.i.next(); number = l1.getNumber(); number = "631 " + number; l1.setNumber(number); boston.i.set(l1); } // output the updated listings using the iterator, i boston.i.reset(); while(boston.i.hasNext()) { System.out.println(boston.i.next( )); // Java automatically invokes toString } System.exit(0); }// end of iterator application } 

public class MainSllExternalIterator { public static void main(String[] args) { SllExternalIterator boston = new SllExternalIterator(); String number; Listing2 l1 = new Listing2("Bill", "1st Avenue", "123 4567" ); Listing2 l2 = new Listing2("Al", "2nd Avenue", "456 3232"); Listing2 l3 = new Listing2("Mike", "3rd Avenue", "333 3333"); Listing2 aListing; boston.insert(l1); // test insert boston.insert(l2); boston.insert(l3); SllIterator i1,i2,i3; i1 = boston.iterator(); i2 = boston.iterator(); i3 = boston.iterator(); // output all the listings using iterator 1 while(i1.hasNext()) { aListing = i1.next(); System.out.println(aListing); // Java automatically uses the toString method; } // add an area code to all the listings using iterator 2 while(i2.hasNext()) { l1 = i2.next(); number = l1.getNumber(); number = "631 " + number; l1.setNumber(number); i2.set(l1); } // output all the updated listings using iterator 3 while(i3.hasNext()) { System.out.println(i3.next()); } System.exit(0); } } 

public class NewNode { Listing2 l; // package access data members NewNode next; public NewNode() { } } 

public class SinglyLinkedList { private Node h; // list header public SinglyLinkedList() { h = new Node(); // dummy node h.l = null; h.next = null; } public boolean insert(Listing newListing) { Node n = new Node(); if(n == null) // out of memory return false; else { n.next = h.next; h.next = n; n.l = newListing.deepCopy(); return true; } } public Listing fetch(String targetKey) { Node p = h.next; while (p != null && !(p.l.compareTo(targetKey) == 0)) { p = p.next; } if(p != null) return p.l.deepCopy(); else return null; } public boolean delete(String targetKey) { Node q = h; Node p = h.next; while (p != null && !(p.l.compareTo(targetKey) == 0)) { q = p; p = p.next; } if(p != null) { q.next = p.next; return true; } else return false; } public boolean update(String targetKey, Listing newListing) { if(delete(targetKey) == false) return false; else if(insert(newListing) == false) return false; return true; } public void showAll() { Node p = h.next; while (p != null) //continue to traverse the list { System.out.println(p.l.toString( )); p = p.next; } } public class Node { private Listing l; private Node next; public Node() { } }// end of inner class Node }//end SinglyLinkedList outer class