Lab 3 (100 pts)
Due Tuesday, January 30 at 9:20am on Catalyst

Part 1: Implementing Your Stack and Queue (60 pts)
  • Before you begin Part 2 of this lab, make sure that you have your Stack and Queue data structures working properly.
  • Note: Your will be using the Queue class that you wrote during class time.
  • For the Queue class instructions, see Queue Lesson.
  • For the Stack class instructions, see Stack Lesson.
  • -20 points for altering your Queue.h and Stack.h from what was provided in class.
  • Place all of your files into a single directory or project (Queue.h, Queue.cpp, Stack.h, Stack.cpp + your commented out test files).
  • Make sure to test all of your functions to ensure that they are working properly in separate test files, named QueueTest.cpp and StackTest.cpp (where you should call the functions inside of main).
  • -20 points for not testing each function fully in QueueTest.cpp and StackTest.cpp


Part 2: Palindrome Tester (40 pts)

  • This is a favorite interview question!
  • Using a stack and a queue, determine whether a string is a palindrome.
  • Create a new text file called palindrome.txt and save it in the same directory with your other files, or in the same project.
  • Copy and paste the following contents into palindrome.txt:

A man, a plan, a canal, Panama.
Do geese see God?
Never odd. Even.
Never odd or even.
Eye
Ear
Able was I ere I saw Elba!
Was it Eliot's toilet I saw?
Race cars

  • Next, create a new C++ file called Palindrome.cpp.
  • Write a program to test each phrase in Palindrome.txt to see if it is a palindrome.
  • For credit, you must use both your Queue and Stack classes in the solution to this problem.
  • Note that you must use only 1 stack and 1 queue in your solution to this problem in order to receive credit for this assignment!
  • Hint: Convert each individual char to a string before you insert it into your stack and queue.
  • Print out your results to the console, like what is shown below in the next section.
    • Indicate in parenthesis next to each phrase whether or not it is a palindrome
  • You may need to review file I/O in C++ to do this assignment.
  • Here is a link to a lesson I gave on File I/O at another college.
  • You can also find your own sources online.


Your Program Should Give the Following Output:

A man, a plan, a canal, Panama. (Palindrome)
Do geese see God? (Palindrome)
Never odd. Even. (Not a Palindrome)
Never odd or even. (Palindrome)
Eye (Palindrome)
Ear (Not a Palindrome)
Able was I ere I saw Elba! (Palindrome)
Was it Eliot's toilet I saw? (Palindrome)
Race cars (Not a palindrome)


What to Submit:

  • Submit your Queue.h, Queue.cpp, QueueTest.cpp, Stack.h, Stack.cpp, StackTest.cpp, and Palindrome.cpp