Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CS 245 Assignment
Practice Assignment 6 – Palindromes
The goal of this assignment is to practice the implementation of two of the data structures we’ve seen:
Stacks and Queues. For this assignment, the correctness of the data structures is primarily measured by
how well the structures can be used to detect palindromes.
Background
Two of the data structures we discussed are Stacks and Queues. A Stack is a LIFO data structure which
has four required functions (push, pop, peek and empty). On the other hand, a Queue is a FIFO data
structure which has three functions (enqueue, dequeue and empty). Because of the order in which data
is placed in these data structures, they can be used to detect palindromes.
A palindrome is a word which can be written the same way backwards or forwards. For example, the
reverse of the word “level” is the same word. (In addition, phrases such as “Al lets Della call Ed Stella” are
palindromes, if spaces omitted and uppercase letters changed to lowercase. But we don’t test for those.)
If an input string is copied, letter-by-letter, into a Stack instance (with a push operation) and to a Queue
instance (with an enqueue operation), the output order should match for palindromes. However, the same
should cause a mismatch for non-palindromes. For example, a non-palindrome word such as “rat” placed
into a Queue instance is retrieved in order (r – a – t) but for a Stack instance, the order is reversed (t
– a – r).