Stack & Queues

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:

  1. What Stack APIs are exposed / available to us ?
  2. 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.