CIS 313 Lab 1 Solution

CIS 313 Lab 1 Solution

This lab involves using stack and queue data structures to solve a simple problem: is a phrase a palindrome or not.

Overview

The program should do the following:

Accept a string from the user. Accept this string using stdin. Test the phrase to check whether it is a palindrome or not, using Stacks and Queues. Display the result.

You will need to implement the following:

Stack.java - a standard stack data structure, supporting: push(), pop(), and isEmpty() Queue.java - a standard queue data structure, supporting: enqueue(), dequeue(), and isEmpty() Node.java - a simple Node class containing two public data fields: char data, Node next Palindrome.java - a driver class which will contain the main and other functions (example : is_Palindrome() ).
You cannot use Java's provided standard Stack and Queue classes or create a wrapper around them, instead you must implement them yourself.

Using Java's provided classes in your submission will result in you losing implementation points.

The Stack and Queue are linear data structure and must be implemented as singly linked lists (where each node in the list has a reference to the next node in the list). This will be conveyed in the labs and if you need further help, please don't hesitate to come ask for help!

These data structures must be implemented efficiently; in other words, each atomic operation (i.e. push()) should operate in O(1), or constant, time.

A palindrome can be defined as a phrase that reads the same forwards or backwards, ignoring all whitespaces and capitalization. So, you may have to do some pre-processing on the input phrases.

Extra Credit [5%]

If you can keep every function under 9 lines of code (and you have working code)! This includes the main() in Palindrome.java. If you managed to do this, add a comment on the top in Palindrome.java.

 
Powered by