In Chapter 8, Queues we looked at functional queues. Deques are a kind of enhanced queues, allowing you to perform insertion and deletion at both the the front and rear ends of the queues.
Why would we need to insert and delete elements from both ends? Well, this is how we would check whether a string is a palindrome. A palindrome is a string that reads the same when read backwards, that is,
s == s.reverse always holds for palindromes. For example, MADAM is a palindrome. (See http://www.fun-with-words.com/palin_example.html
for more fun examples of palindromes.)
The following figure shows a string and how we could use deletion at both ends to check whether it is a palindrome:
The algorithm is pretty ...