CS 112 Project 8: Queues (and Stacks)
- Practice building Queue operations.
- Use a Stack and a Queue to solve a problem
- Practice using exceptions.
This week's project is a single person project.
The project is to:
As usual, you should use test-driven development to accomplish these tasks.
- Convert your Queue into a template.
- Add a new method to your ArrayQueue class:
that changes the capacity of aQueue to newCapacity.
(This is much trickier than Stack::setCapacity():
if newCapacity is zero OR
newCapacity or < getSize(),
setCapacity() should throw an exception;
otherwise, it should allocate a new array with the new capacity,
copy the values from the old array into the new array,
and deallocate the old array.)
To help you see all the things that can go wrong,
you should make certain your method passes all the tests in
this test method
before working on the rest of the project.
- Use your Stack<Item> and ArrayQueue<Item> to solve a problem.
You are to design and build a palindrome detector class.
For our purposes, a palindrome is a line of text in which the alphabet characters
are the same when read forwards and backwards.
For example, the lines:
Madam, I'm Adam.
A man, a plan, a canal, Panama!
are both palindromes.
Your palindrome detector is to read an input file and create an output file
that is an exact copy of the input file, except that 3 asterisks (***)
are printed at the end of each line that is a palindrome.
Thus, if the input file contained the two lines above,
the output file should contain:
Madam, I'm Adam. ***
A man, a plan, a canal, Panama! ***
Your class constructor should accept and save the names of the
input and output files.
To accomplish this, your class should provide
a detectPalindromes() method that
opens streams to the input and output files,
processes the input file line-by-line,
and produces the corresponding output file.
(Hint: use getline() to read a line into a string,
immediately write that string to the output file,
then process the string character-by-character.)
Don't forget to close the streams at the end of this method.
To "process" a given string str,
your checker should call an isPalindrome(str) method that
returns true or false based on whether or not
str is a palindrome.
This method should process the string character-by character, as
This algorithm works because a stack is a LIFO structure while a queue is a FIFO structure.
When we have added the characters from a line to each structure, popping the stack
gives us the line's last character on the line, while removing from a queue gives us the
line's first character.
As soon as we find a mismatch in these characters, we know the line is not a palindrome;
However, if we reach the bottom of the stack and the end of the queue without finding any
mismatch, then we have a palindrome.
For each character in the string:
If that character is a letter, your program should:
- convert it to lower case;
- push it onto a stack; and
- append it to a queue.
When the string's characters have been loaded into the stack and queue,
repeat these steps until the stack and queue are empty:
- Pop a char from the stack into ch1;
- Remove a char from the queue into ch2;
- If ch1 and ch2 are different,
then return false (the line is not a palindrome);
- Return true.
The twist is that for each line to be processed,
your method should define your stack and queue
with initial capacities of 1.
You are to "wrap" the push() and append()
calls in try-catch blocks.
If either throws an exception (because the structure is full),
your exception-handler code should:
- Use setCapacity() and getCapacity() to
double the structure's capacity; and
- Invoke push() and append() again to push/append
the character onto the (now larger) structure.
There is one special case to cover:
a blank line can (trivially) be considered to be a palindrome,
but we will not do so -- your class should not mark blank lines
You may find some of the
functions in the <cctype> library
to be useful for this project.
As always, if you get to the point where you cannot figure out what is wrong,
use the debugger, as it will let you trace the execution of your code
one step at a time!
You should use test-driven development to build your class.
Write a test class and strong test-methods for the methods
in your palindrome detector class.
When your palindrome detector passes all of your tests, try it on this
as a final test.
Our grader will be using it to test your program.
A hard copy of this grade sheet,
attached to a hard copy of a
script file that lists the files in
your project, shows that it compiles/links correctly, and shows it correctly
running and providing the required functionality.
An electronic copy of your project, in your
This page maintained by