Computer Programming II

Lab Project #3a

PROBLEM:

You are to write a program in C++ that solves the classic palindrome problem. A palindrome is a word or phrase that reads the same forwards as backwards. You must solve the palindrome problem using stacks and queues. Your program will read in a string, pushing each letter on a stack of characters and enqueueing each letter on a queue of characters. When the end of the string is reached, the program will then pop and dequeue the letters one at a time. If each of the letters is identical, then the string is the same backwards as forwards, and is therefore a palindrome.

You must write and get to work the six functions known as the stack ADT and the six functions known as the queue ADT. Use a class for each with an array to hold the elements. Using these functions, write a program that determines whether or not any given string is a palindrome.

The stack and queue approach may seem an overly complex solution, but this is only project 3a. Do a good job on your ADTs, because you will have to use them to do project 3b. This is actually a large and complex project divided down into two steps.

Entered string: Output:

no eye on is a palindrome.

nonsense about palindromes is not a palindrome.

star rats is a palindrome.

DESIGN:

You must hand in a design detailing your data structures used to implement a stack and a queue. Your documentation for this portion of the project can be entered as comments at the top of the module.

IMPLEMENTATION:

You must have three program modules for this project. One should hold the Queue ADT, another the Stack ADT and the third should hold the main function and any other code for handling the palindromes. Make sure you make up "queue.h" and "stack.h" header files which should be #included at the top of your program with the other includes. Files named "queue.cpp" and "stack.cpp" should hold the actual functions for those classes.

Make sure you use classes for your stack and queue ADTs. In the later projects, you will have to use what you build here, so build it well and make it flexible with error-checking and full use of typedefs and const constants.