Data structures: Array implementation of stacks

See complete series on data structures here:

In this lesson, we have discussed array based implementation of stack data structure.

Source Code:

Time complexity of push for dynamic array implementation:

If we start with an array of size 1 and keep doubling the size with each overflow, for n pushes.. cost of copy will be

(1 + 2 + 4 + 8 + ... + n/2 + n)
= n *( 1+ 1/2 + 1/4 + 1/8 + ... 1/n) - taking out n
= n*2 - the expression in bracket above will evaluate to 2.

So, cost of copy in n pushes = O(n)
Cost of n normal pushes = O(n) - each push takes constant time
Total cost of n pushes = O(n)
Average cost of 1 push = O(1).

[iftekharjitu]

The tutorial is from 2013, and I am from 2021, seems like it will never get old. God bless you

[emmojo]

As a hearing impaired beginning programmer, I want to thank you sincerely for the captions. You have just earned a subscription from me, which is unique given that I don't have any other subscriptions. Keep up the great work.

[Danieljohnson-shiq]

OMG whoever did and organize this tutorial God will bless him. I have went through 13 executive tutorials on stack i still didn't get it, but once i watch this video, it's as if the tutor transfered the knowledge to my brain straight LOL. Once again thank you, am subscribing.

[zlcoolboy]

This makes stacks so easy to understand. No wonder people like them so much. So useful, especially if you make a struct out of it.

[Calm_Energy]

I really appreciate how you give me the words to describe the connection between the pseudo-code and Big O notation. For ex. "two scenarios in a push operation, " then you show the details between constant time for a normal push operation then O(n) for an overflow correction using a larger array. Next you say "the time complexity of push with this strategy" O(1) in best case, O(n) in worst. Plus the pseudo-code really helps!

[MatheusLB]

Your video makes the internet a better place

[RenuSharma-zbbz]

One good thing is that while explaining the data structures not any particular language is used so it is easy for any language study to watch this video

[sarojhkalyan]

Thank you for making this video. Explanations from others didn't get me to understand this concept as thoroughly as yours did.

[virenbhanushali]

The clearity of your words just blew my mind.keep you work on

[aricktanwar]

One of the talented person who knows data structures as mother tongue
he will be the only reason i pass my examination

[fay_chong]

Hi, I consider myself rather green when it comes to programming and I have legit no idea what my professor has been teaching until I found this video. Thank you so much for your clear explanation. :) This video is super helpful!

[amitech]

Great tutorial and nice accent, easily understandable. U reduced my work to Google a lot and then go through too many pages to understand these concepts for my College viva.

[samarth-yt-gn]

I really don't understand why few disliked, this made me understand concepts of stack well.

[smitasharma]

I have gone through all your data-structures videos and I really like the way you explain. I appreciate the content as well as the clarity of the voice and flow.

[MubasharAli-opvq]

The tutorial is from 2013, and I am from 2023, seems like it will never get old. God bless you

[PurnenduMondal_]

Sir You bring my Confidence you a Lot...for all of your Videos

[daveboyle]

You're explanation is clear and concise. Far superior to the text provided with our course. Thank you.

[PokeDubzTCG]

Your videos are great! Thanks for the clear explanations, as my current CSC-250 professor doesn't give us much information on these forms of data structures.

[kevinrocky]

Anyone else feel like you learned more from this than in college?

[tusharjajodia]

Still the Best Tutorial in the platform