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

Summary

Like stacks, queues are fundamental data structures. Queues help us realize the FIFO approach. We looked at how FIFO queues are implemented in the imperative world. We noted that we would end up with too much of copying if we insert new nodes at the end of a list. We could do this in the imperative world but would end up with O(n) copying performance to achieve persistent FIFO queues.

Instead, we looked at an innovative design involving two stacks. We also looked at the Scala implementation and discussed some Scala idioms.

Priority queues are an important variation of queues. We define a priority for each element of the queue and wish to pop the element with the highest priority.

Heap is a famous data structure for implementing the priority ...

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