In this assignment you are required to utilize the stack and queue data structur
ID: 3682804 • Letter: I
Question
In this assignment you are required to utilize the stack and queue data structures provided in the book. A slightly modified versions of these implementations is provided in this assigment, this implementation is the one to be used. Keep in mind that, there is a stack and a queue built-in in Java, however you are NOT allowed to use these for this assignment. The Stack implementation is contained in the class ListStack.java, and the Queue implementation is contained in the class ListQueue.java. Because both are based on Linked Lists the ListNode.java (extremely similar to the Node.java file in the previous assignment) is provided. An additional file called UnderflowException.java is provided also to handle exceptions. What you are required to do is to implement a driver program that utilizes both the stack and the queue implementations provided to do the following: 1. Read two strings from input. 2. Utilize the stack and the queue both to determine if each string is a palindrome (a string spelled forward as it is backwards, ex. radar) 3. Print a message indicating if each of the strings is a palidrome or not. 4. If the strings are of different lengths, then indicate that and exit. Otherwise if both are not palindromes (only if both are not), check to see if they are the reverse of each other. (ex. abcde and edcba both are not palindromes but they are the reverse of each other. Also here, you must utilize the stack and the queue in this determination. Once you have made the determination, print a message indicating if they are or not the reverse of each other. Files that you will need: all provided with the assignment ^^^^^^^^^^^^^^^^^^^^^^^^^ ListStack.java : This file contains the stack implementation. ListQueue.java : This file contains the queue implementaiton. ListNode.java : This file contains the node implementation. UnderflowException.java: It's an Exception handling file that you will need. Files to implement and submit: ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Main.java : This is the driver program you are to implement for this assignment.
// Basic node stored in a linked list // Note that this class is not accessible outside // of package weiss.nonstandard class ListNode<AnyType> { // Constructors public ListNode( AnyType theElement ) { this( theElement, null ); } public ListNode( AnyType theElement, ListNode<AnyType> n ) { element = theElement; next = n; } public AnyType element; public ListNode<AnyType> next; } // ListQueue class // // CONSTRUCTION: with no initializer // // ******************PUBLIC OPERATIONS********************* // void enqueue( x ) --> Insert x // AnyType getFront( ) --> Return least recently inserted item // AnyType dequeue( ) --> Return and remove least recent item // boolean isEmpty( ) --> Return true if empty; else false // void makeEmpty( ) --> Remove all items // ******************ERRORS******************************** // getFront or dequeue on empty queue /** * List-based implementation of the queue. * @author Mark Allen Weiss */ public class ListQueue<AnyType> { /** * Construct the queue. */ public ListQueue( ) { front = back = null; } /** * Test if the queue is logically empty. * @return true if empty, false otherwise. */ public boolean isEmpty( ) { return front == null; } /** * Insert a new item into the queue. * @param x the item to insert. */ public void enqueue( AnyType x ) { if( isEmpty( ) ) // Make queue of one element back = front = new ListNode<AnyType>( x ); else // Regular case back = back.next = new ListNode<AnyType>( x ); } /** * Return and remove the least recently inserted item * from the queue. * @return the least recently inserted item in the queue. * @throws UnderflowException if the queue is empty. */ public AnyType dequeue( ) { if( isEmpty( ) ) throw new UnderflowException( "ListQueue dequeue" ); AnyType returnValue = front.element; front = front.next; return returnValue; } /** * Get the least recently inserted item in the queue. * Does not alter the queue. * @return the least recently inserted item in the queue. * @throws UnderflowException if the queue is empty. */ public AnyType getFront( ) { if( isEmpty( ) ) throw new UnderflowException( "ListQueue getFront" ); return front.element; } /** * Make the queue logically empty. */ public void makeEmpty( ) { front = null; back = null; } private ListNode<AnyType> front; private ListNode<AnyType> back; } // ListStack class // // CONSTRUCTION: with no initializer // // ******************PUBLIC OPERATIONS********************* // void push( x ) --> Insert x // void pop( ) --> Remove most recently inserted item // AnyType top( ) --> Return most recently inserted item // AnyType topAndPop( ) --> Return and remove most recent item // boolean isEmpty( ) --> Return true if empty; else false // void makeEmpty( ) --> Remove all items // ******************ERRORS******************************** // top, pop, or topAndPop on empty stack /** * List-based implementation of the stack. * @author Mark Allen Weiss */ public class ListStack<AnyType> { /** * Construct the stack. */ public ListStack( ) { topOfStack = null; } /** * Test if the stack is logically empty. * @return true if empty, false otherwise. */ public boolean isEmpty( ) { return topOfStack == null; } /** * Make the stack logically empty. */ public void makeEmpty( ) { topOfStack = null; } /** * Insert a new item into the stack. * @param x the item to insert. */ public void push( AnyType x ) { topOfStack = new ListNode<AnyType>( x, topOfStack ); } /** * Remove the most recently inserted item from the stack. * @throws UnderflowException if the stack is empty. */ public void pop( ) { if( isEmpty( ) ) throw new UnderflowException( "ListStack pop" ); topOfStack = topOfStack.next; } /** * Get the most recently inserted item in the stack. * Does not alter the stack. * @return the most recently inserted item in the stack. * @throws UnderflowException if the stack is empty. */ public AnyType top( ) { if( isEmpty( ) ) throw new UnderflowException( "ListStack top" ); return topOfStack.element; } /** * Return and remove the most recently inserted item * from the stack. * @return the most recently inserted item in the stack. * @throws UnderflowException if the stack is empty. */ public AnyType topAndPop( ) { if( isEmpty( ) ) throw new UnderflowException( "ListStack topAndPop" ); AnyType topItem = topOfStack.element; topOfStack = topOfStack.next; return topItem; } private ListNode<AnyType> topOfStack; } /** * Exception class for access in empty containers * such as stacks, queues, and priority queues. * @author Mark Allen Weiss */ public class UnderflowException extends RuntimeException { /** * Construct this exception object. * @param message the error message. */ public UnderflowException( String message ) { super( message ); } }
Explanation / Answer
package assignment;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
public class PalindromeTest {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter two strings seperated by space");
String str1 = sc.next();
String str2 = sc.next();
boolean pal1 = isPalindrome(str1);
boolean pal2 = isPalindrome(str2);
System.out.println(str1+" : "+(pal1 ? "Palindrome" : "Not palindrome"));
System.out.println(str2+" : "+(pal2 ? "Palindrome" : "Not palindrome"));
if(str1.length() != str2.length())
System.out.println("Strings are of different lengths");
else if(!pal1 & !pal2) {
Stack<Character> stack = new Stack<Character>();
Queue<Character> queue = new LinkedList<Character>();
for(char c: str1.toCharArray())
stack.push(c);
for(char c: str2.toCharArray())
queue.add(c);
//determine
boolean reverse = false;
while(!queue.isEmpty()) {
if(queue.poll() != stack.pop()) {
reverse = false;
break;
}
else
reverse = true;
}
if(reverse) {
System.out.println("string are reverse of each other");
}
}
}
public static boolean isPalindrome(String str) {
if(str != null && !"".equals(str.trim())) {
Stack<Character> stack = new Stack<Character>();
Queue<Character> queue = new LinkedList<Character>();
for(char c: str.toCharArray()) {
stack.push(c);
queue.add(c);
}
while(!queue.isEmpty()) {
if(queue.poll() != stack.pop())
return false;
}
return true;
}
return false;
}
}
//Basic node stored in a linked list
//Note that this class is not accessible outside
//of package weiss.nonstandard
class ListNode<AnyType>
{
// Constructors
public ListNode( AnyType theElement )
{
this( theElement, null );
}
public ListNode( AnyType theElement, ListNode<AnyType> n )
{
element = theElement;
next = n;
}
public AnyType element;
public ListNode<AnyType> next;
}
//ListQueue class
//
//CONSTRUCTION: with no initializer
//
//******************PUBLIC OPERATIONS*********************
//void enqueue( x ) --> Insert x
//AnyType getFront( ) --> Return least recently inserted item
//AnyType dequeue( ) --> Return and remove least recent item
//boolean isEmpty( ) --> Return true if empty; else false
//void makeEmpty( ) --> Remove all items
//******************ERRORS********************************
//getFront or dequeue on empty queue
/**
* List-based implementation of the queue.
* @author Mark Allen Weiss
*/
class ListQueue<AnyType>
{
/**
* Construct the queue.
*/
public ListQueue( )
{
front = back = null;
}
/**
* Test if the queue is logically empty.
* @return true if empty, false otherwise.
*/
public boolean isEmpty( )
{
return front == null;
}
/**
* Insert a new item into the queue.
* @param x the item to insert.
*/
public void enqueue( AnyType x )
{
if( isEmpty( ) ) // Make queue of one element
back = front = new ListNode<AnyType>( x );
else // Regular case
back = back.next = new ListNode<AnyType>( x );
}
/**
* Return and remove the least recently inserted item
* from the queue.
* @return the least recently inserted item in the queue.
* @throws UnderflowException if the queue is empty.
*/
public AnyType dequeue( )
{
if( isEmpty( ) )
throw new UnderflowException( "ListQueue dequeue" );
AnyType returnValue = front.element;
front = front.next;
return returnValue;
}
/**
* Get the least recently inserted item in the queue.
* Does not alter the queue.
* @return the least recently inserted item in the queue.
* @throws UnderflowException if the queue is empty.
*/
public AnyType getFront( )
{
if( isEmpty( ) )
throw new UnderflowException( "ListQueue getFront" );
return front.element;
}
/**
* Make the queue logically empty.
*/
public void makeEmpty( )
{
front = null;
back = null;
}
private ListNode<AnyType> front;
private ListNode<AnyType> back;
}
//ListStack class
//
//CONSTRUCTION: with no initializer
//
//******************PUBLIC OPERATIONS*********************
//void push( x ) --> Insert x
//void pop( ) --> Remove most recently inserted item
//AnyType top( ) --> Return most recently inserted item
//AnyType topAndPop( ) --> Return and remove most recent item
//boolean isEmpty( ) --> Return true if empty; else false
//void makeEmpty( ) --> Remove all items
//******************ERRORS********************************
//top, pop, or topAndPop on empty stack
/**
* List-based implementation of the stack.
* @author Mark Allen Weiss
*/
class ListStack<AnyType>
{
/**
* Construct the stack.
*/
public ListStack( )
{
topOfStack = null;
}
/**
* Test if the stack is logically empty.
* @return true if empty, false otherwise.
*/
public boolean isEmpty( )
{
return topOfStack == null;
}
/**
* Make the stack logically empty.
*/
public void makeEmpty( )
{
topOfStack = null;
}
/**
* Insert a new item into the stack.
* @param x the item to insert.
*/
public void push( AnyType x )
{
topOfStack = new ListNode<AnyType>( x, topOfStack );
}
/**
* Remove the most recently inserted item from the stack.
* @throws UnderflowException if the stack is empty.
*/
public void pop( )
{
if( isEmpty( ) )
throw new UnderflowException( "ListStack pop" );
topOfStack = topOfStack.next;
}
/**
* Get the most recently inserted item in the stack.
* Does not alter the stack.
* @return the most recently inserted item in the stack.
* @throws UnderflowException if the stack is empty.
*/
public AnyType top( )
{
if( isEmpty( ) )
throw new UnderflowException( "ListStack top" );
return topOfStack.element;
}
/**
* Return and remove the most recently inserted item
* from the stack.
* @return the most recently inserted item in the stack.
* @throws UnderflowException if the stack is empty.
*/
public AnyType topAndPop( )
{
if( isEmpty( ) )
throw new UnderflowException( "ListStack topAndPop" );
AnyType topItem = topOfStack.element;
topOfStack = topOfStack.next;
return topItem;
}
private ListNode<AnyType> topOfStack;
}
/**
* Exception class for access in empty containers
* such as stacks, queues, and priority queues.
* @author Mark Allen Weiss
*/
class UnderflowException extends RuntimeException
{
/**
* Construct this exception object.
* @param message the error message.
*/
public UnderflowException( String message )
{
super( message );
}
}
---output----------------
Enter two strings seperated by space
abcde
edcba
abcde : Not palindrome
edcba : Not palindrome
string are reverse of each other