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.

Code:

• Solution