In CLRS, the authors have a chapter called “Elementary Data Structures”. In there they cover 3 types of data structures in particular:
- Stacks & Queues
- Linked Lists
- Trees (representations)
There is much to learn from these “elementary” data structures.
Here is a problem I came across recently .
Problem: Implement a queue using as many stacks as needed.
The question is deceptively simple. There are two things we need to take care of first before approaching this problem:
- What Stack APIs are exposed / available to us ?
- How to detect empty stack ?
Some insights I had while implementing this solution are as follows:
- One needs to be careful in implementation details.
- Terminating conditions need to be carefully considered for stack / queue class of problems.
Code: