$($CSCI $251)$ Project $2$: Implement and Apply Stack and Queue

Total Grading Points: $100$

Purpose and Project Description:

The purpose for this project is to reinforce the knowledge from Chapter $5$ of the online course

textbook $($zyBooks$).$ Students will practice how to implement stack and queue data structures

using list ADT; for instance, ArrayList. Students will also apply a stack and a queue in practical

implementation; for instance, to check if a string is a palindrome or not. The implementation

can be done in either Java or C$++$ programming language.

Tasks:

$1.$ Use ArrayList to implement MyStack class which define the data structure that

has Last$-$In$-$First$-$Out property $[35$ points$].$

$2.$ Use ArrayList to implement MyQueue class which define the data structure that

has First$-$In$-$First$-$Out property $[35$ points$].$

$3.$ Write a function public static Boolean isPalindrome $($String sentence$)[30$ points$].$

This function returns true if sentence is a palindrome; false otherwise.

Provided Template files:

Three template files are given in either Java or C$++($that is$,$ CSCI$251$ProjectTwo, MyStack and

MyQueue$).$ Students should add necessary comments to all files and implement all

functionalities in the given files. No extra functions can be added. No function name can

be changed. Do not modify the contents of the main method in CSCI$251$ProjectTwo file.

$/**$

$*$ CSCI$251$ProjectTwo: Use MyStack and MyQueue to write a project that checks if a sentence is palindrome

$*$

$*$ @author Your name

$*$ @version Date

$*/$

import java.util.Scanner;

public class CSCI$251$ProjectTwo

$\{$

public static void main$($String $[]$ args$)$

$\{$

Scanner input $=$ new Scanner$($System$.$in$)$;

String sentence;

String again;

do$\{$

System.out.println$("$Enter a sentence, I will tell you if it is a palindrome: $")$;

sentence $=$ input.nextLine$()$;

if$($isPalindrome$($sentence$))$

System.out.println$("\backslash ""+$ sentence $+"\backslash "$ is a palindrome!"$)$;

else

System.out.println$("\backslash ""+$ sentence $+"\backslash "$ is not a palindrome!"$)$;

System.out.println$("$Do you want another test $(\backslash "$YES$\backslash "$ or $\backslash "$NO$\backslash ")$: $")$;

again $=$ input.nextLine$()$;

$\}$while$($again$.$equalsIgnoreCase$("$YES$"))$;

$\}$

$/**$

$*$ isPalindrome returns true if the given String is a palindrome

$*$ @

$*/$

public static boolean isPalindrome$($String sentence$)$

$\{$

$//$ You implement this

$//$ declare a MyStack s

MyStack s $=$ new MyStack$()$;

$//$ declare a MyQueue q

MyQueue q $=$ new MyQueue$()$;

for$($int i $=0$; i $<$ sentence.length$()$; i$++)$

$\{$

$//$ if ith character in sentence is a letter

$//$ convert to upper case and push it into s and q

$\}$

while$(!$s$.$isEmpty$())$

$\{//$If stack is not empty

$//$ if the front of the queue does not match the top of stack

$//$ return false

if $($Character$.$isLetter$($sentence$.$charAt$($i$)))\{$

char c $=$ Character.toUpperCase$($sentence$.$charAt$($i$))$;

s$.$push$($c$)$;

q$.$push$($c$)$;

$//$ pop out top of the stack and front of the queue

$\}$

return true;

$\}$

$\}$

$\}$

$/**$

$*$ class MyQueue implemented using ArrayList. The index $0$ element is the front of the queue

$*$ The last element of the queue has index tail

$*$

$*$ @author Your Name

$*$ @version Date

$*/$

import java.util.ArrayList;

public class MyQueue

$\{$

private ArrayList list; $//$ hold the elements in queue

private int tail; $//$ index of the last element in queue

$/**$

$*$ constructor construct an empty queue

$*/$

public MyQueue$()$

$\{$

$\}$

$/**$

$*$ isEmpty return true if the queue is empty; false otherwise

$*$ @return true if the queue is empty; false otherwise

$*/$

public boolean isEmpty$()$

$\{$

$\}$

$/**$

$*$ size return the size of the queue

$*$ @return the number of elements in queue

$*/$

public int size$()$

$\{$

$\}$

$/**$

$*$ peek return the front element of the queue

$*$ @return the front element of the queue. If the queue is empty, return null

$*/$

public E peek$()$

$\{$

$\}$

$/**$

$*$ pop remove the front element of the queue

$*/$

public void pop$()$

$\{$

$\}$

$/**$

$*$ push push a new element to the queue

$*/$

public void push$($E item$)$

$\{$

$\}$

$\}$

$/**$

$*$ class MyStack: A stack class implemented by using ArrayList

$*$ All stack elements are stored in an ArrayList. The top element has index top

$*$

$*$ @author Your Name

$*$ @version Date

$*/$

import java.util.ArrayList;

public class MyStack

$\{$

private ArrayList list; $//$ used to store elements in stack

private int top; $//$ the index of top element

$/**$

$*$ constructor construct an empty stack

$*/$

public MyStack$()$

$/**$

$*$ class MyStack: A stack class implemented by using