Task: Telling Letters System
The system you are going to develop will accept a string which
includes the letters, numbers
and any symbols and will read the string from left to right. The
system only selects letters and
outputs them in the reverse order. The system should also report
whether the output string is a
palindrome which is a string of characters that reads the same from
left to right as it does from
right to left.

For example:
If the inputted string is "r8e3h^3c&a97et", the output of your system
should be the string
"teacher", and it should tell that it is not a palindrome.
If the inputted string is "d$%a8d", the output of your system should
be the string "dad", and it
should tell that it is a palindrome.

Questions and Hints:

1. To design the system described above, you can use queues and
stacks. Describe the
stack and queue ADTs and describe the differences between the queue
and the stack.

2. Develop a filtering method using a queue: By adding all the
elements of an original
string one-by-one from left to right to an initially empty queue, the
elements come from
the queue method should be all letters.

3. Develop a reverse method using a stack: Push all the characters
from the filtering queue
method one-by-one from left to right into an original empty stack and
pop the whole
stack.

4. Develop a second queue method and a comparing method which
compares the outputs
from the stack and the queue: add all the characters from the
filtering queue one-by-one
from left to right in an original empty queue and dequeue the whole
queue. The filtered
string is a palindrome if all the characters popped of the stack in
step 3 match the
characters that are dequeued from the front of the queue in step 4.

5. Given a string "r90e^hca9et", filter it first using the filtering
method in step 2, and draw
a table for a queue and a table for a stack to report the output.

6. Implement steps 2-4 using your favored language (pseudo code,
C/C++, JAVA and
etc.).

7. What is the running time of each of your methods?