O'Reilly logo

Learning Functional Data Structures and Algorithms by Raju Kumar Mishra, Atul Khot

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required