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:

 

 

 

 

 

 

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s