Am; YourMove: Visualize Sorting a Stack !

This blog summarization of the video from a YouTube channel AM; YourMove. This is the link to the video.

In this video, the presenter discussed how to sort a stack by just using basic stack operations like push, pop or peek etc. Other constraints on the problem are we can only use data structure stack. But it gives us the flexibility that we can use more than one stack (if we need).

It is one of the simple interview questions out there but the presenter made it more interesting by using a visualizing tool called processing IDE to show the viewers how the elements in the stack are pushed and popped. The video is attached at end of the post.

The presenter informs that the algorithm’s complexity is O(n2) which by no means sounds optimal but under these circumstances this best we can get. The algorithm is discussed below.

We need 2 stacks. The idea is to pull an item from the original stack and push it on the other stack. If pushing this item would violate the sort order of the new stack, we need to remove enough items from it so that it’s possible to push the new item. Since the items we removed are on the original stack, we’re back where we started.

code

Link to the visualization sample video (CLICK HERE) . You can check out the code HERE.

This was one of the interesting topics yet on AM; YourMove. Check out the channel here SUBSCRIBE NOW!

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