- Prof. Dancy's Site - Course Site -

Queues & Palindromes

• Due Wednesday, 23-Oct (before class)

Palindromes are words or numbers that are spelled the same both forwards and backwards. There are a number of often seen and famous palindromes:

Ewe
Anna
Racecar
A man a plan a canal Panama
Taco cat

The task

Your job is to develop an algorithm (and accompanying code) to determine whether a string is or is not a palindrome. You also will have to analyze the runtime of your algorithm/code after you've completed the task.

• (You'll have to consider in the analysis how much time an operation from a queue or stack takes dependending on the way those ADTs are implemented)

The tools ("What can I use?")

• You should be using these three things to accomplish your task
  • A Stack
  • A Queue
  • Either the index function ("string".index("s")) OR the indexing operator ("string"[0]).
    • *You must only call/use this method once per letter
  • You should not be using any extra arrays or lists for your algorithm (only 1 queue and 1 stack)

Tips

• You want to think about how queues and stacks structure and order data.

*The original version of this assignment was developed by Lea Wittie @ Bucknell University.