Chapter 10. Being Lazy - Queues and Deques
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 simple. We treat the string as a deque of characters. We keep removing successive elements from both the front and rear ends of the string and compare them. If we find a mismatch, the string is not a palindrome.
Another example is how we would model...
