Data structures: Array implementation of stacks
HTML-код
- Опубликовано: 8 сен 2024
- See complete series on data structures here:
• Data structures
In this lesson, we have discussed array based implementation of stack data structure.
Source Code:
C code: gist.github.co...
C++ code (Object oriented implementation) : gist.github.co...
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).
For practice problems and more, visit: www.mycodeschoo...
Like us on Facebook: / mycodeschool
Follow us on twitter: / mycodeschool
The tutorial is from 2013, and I am from 2021, seems like it will never get old. God bless you
g old
2023 anyone?😅
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.
Jamaika I am very glad that you are getting helped. :)
+Jamaika (y) THIS COMMENT MADE MY DAY :D
why ? doesn't c taught in ur country?
Sonu Sonu sabse yahin puchega?
1. Check your English Before Commenting.
2. One can watch RUclips videos irrespective of the fact that the thing is being taught in their country.
3. Stop spamming RUclips with foolish comments.
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.
Your video makes the internet a better place
Matheus Lacerda so agreed
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!
Thank you for making this video. Explanations from others didn't get me to understand this concept as thoroughly as yours did.
The tutorial is from 2013, and I am from 2023, seems like it will never get old. God bless you
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
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.
Sir You bring my Confidence Back.....Thank you a Lot...for all of your Videos
The clearity of your words just blew my mind.keep you work on
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!
You're explanation is clear and concise. Far superior to the text provided with our course. Thank you.
please check the details
Array Stack of Winterfell.
+Vlad Albescu up u go
Ded
valar mugulish
THE NORTH REMEMBERS....
legend
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.
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.
Anyone else feel like you learned more from this than in college?
One of the talented person who knows data structures as mother tongue
he will be the only reason i pass my examination
I really don't understand why few disliked, this made me understand concepts of stack well.
Thank you so much sir! You're an inspiration for new tutors like me🙏
This helps so so so much!! Thank you for the clear explanation.
Tommorow's my final.Bless you 😂😂
This is the best explanation i could ever get on array implementation of stack. thank you very much
This video is very helpful.I was going hardtime for perceiving the concepts.And I got poor marks.Now I have started to understand by Mercy of Allah.Thanks a lot for this video.
Har cheej me allah ko ghusa do. Thank to this great tutor , not allah.
@@075_ritikkumar7 It is always Allah (The One and Only God) who always helps me for everything. He is the Rahman( The beneficent)has created us from mingled sperm. I also thanked this tutor who has helped me. But if I loose my brain power ,then this tutor can help me no more despite his talent. Because I was depressed for many years. Even I was going to attempt suicide .At that time, it was hard for me to study and understand hard concepts. Fortunately, Allah guided me through HIs Scripture 'The Quran' and helped me to overcome my depression. Finally, I have found a new meaning of my life.
@@075_ritikkumar7 Allah is the most wise.He created everything with exact meaaure through His knowledge He has knowledge about both seen and unseen.
@@075_ritikkumar7 Try to respect every religion. And before commenting also read scripture of respective religion
No word for this kind of knowledge,simply fr m the best in the world ,where are u sir plz comeback we want more videos from you,plzzz sir help u truly the best in the world.
Still the Best Tutorial in the platform
4:10 - "We do not care what garbage lies there" Hahaha
mean bully
I think you are the one with the garbage face and you're trying to feel good by posting sh*t in the internet.
Get a life man.
Grove Street calm your balls
By garbage ,he meant garbage value , that is a typical word in programming vocabulary ,used to describe unwanted value /data .
Garbage value is a thing!!
@@user-mc1eb1sg5x wtf💀💀💀🤣🤣🤣 you okay my guy?
You are absolutely amazing man !!
We wish that too :)
Sir how top=max_size-1
@@VinayKumar-vm1hg If you understood please explain it to me as well.
@@VinayKumar-vm1hg In most programming languages, the arrays are implemented as 0 based index. Let's say there are 2 elements in an array, so its max_size = 2, and there are only two indices - 0, 1. So the variable top should be equal to 1, hence top = max_size-1;
My wish is to free and quality education for all. I don't know how many of you are doing this work. But I wish to God to give a healthy and prosperous life to all of you. Bcoz you r doing a great work. Plz make more videos. You know about India's privet college. they are just useless. You have a great quality to teach everything in simple way. Plz help me help us to become a Good engineer from privets college. We want more videos. Plz make more videos.
please check the details
thanks for this good explanation and clearing the concept
u r d best in dis business :) thankyou soo much for such beautiful and easy to understand explanations :D
#appreciate#your#work :)
give this man a medal
Sir this is very very clearly and amazingly explained video
Thank u very much
so easy! you did a better job than my professor...
i can feel the dedication from your each word.thank you for the information.i killed the subscribe button .#feeling informative with my code school
keep doing it. it is really work as helping hand for many of us..thank you.
thank you man , this was very helpful. God bless you.
My code school,
just simply rocks........
Thankyou so much. Now i can Write Stack code on my own
thanks bro I understood the topic very well you earned yourself a subscriber
Perfect teaching..Finally i learnt tq u so much..
please check the details
i really wish that you guys had started this video-makings a year before !!
Thanks Sir. it helped me a lot.
this explanation helped me a lot sir. thank you very much
Just what I need, thank you for your informative video
amazing woaww i learn first time from your this tutorial and understand stack with array too much easily thansk sir
please check the details
Thank you very much! I have been trying all over again to creat something similar without any success!!! THANK YOU!!!! You helped me a lot!
I've been watching EVERY video about to understand the pop( ) concept, and NOW I'm finally understanding what happens to the number after the pop( ).
All the lessons are great!
Thank you!
please check the details
explanation is done very well... thanks
Your top function has a bug. It will crash if we have an empty stack. At 11:25.
add if condition to check if it is empty
#include
#include
#define max_size 101
int a[max_size];
int top=-1;
void isempty()
{
if(top == -1)
{
printf("error: stack is empty ");
return;
}
}
void push(int x)
{
if(top == max_size -1) // handles stack overflow
{
printf("error: stack overflow
");
return;
}
top++;
a[top] = x;
}
void pop()
{
if(top == -1)
{
printf("error: no element to pop
");
return;
}
top--;
}
int Top()
{
isempty();
return a[top];
}
void print()
{
isempty();
int i;
printf("stack: ");
for(i=0;i
Thank you. God bless you. Keep it up.
Your videos amazing man , thanks for sharing them they help a lot. Keep up good work =)
Nice explanation man
For n pushes, cost of copy should be 1 + 2 + 4+....+ (n/4) + (n/2), because when the stack is overflowed on trying to push the ((n/2) + 1)th element, it creates another dynamic array of size n, which can contain all n pushes. So, why did we include 'n' in the cost?
so for n+1 elements, you''ll have to include n
Nice video dude!! It helped alot, keep up the great work
really u saved my day man a big thank for u
Really loved your lectures bro 😊 .. helpful
u saved me from my exam thx a lot bro
very good， thanks
awesome tutorial ,pls keep more videos on trees and graphs in c++(oop) language
The top function will return the element at the top of the stack. So in push function top==MAX-1 might be true even if stack is not full
please check the details
Very understandable,,,,,,,,,,,
awesome tutorial of DS .. thnku so much.. :)
In the top function, where the line " return A[top]; " is there, the compiler throws out an error that "array subscript is not an integer". And yes, my function starts with int, not void.
thank u so much..i am very grateful to you
fabulous explanation...
IsEmpty()
{
return top==-1;
} // is much cleaner...Awesome videos nonetheless.
Good explanation
thank you very much,wish u wer my lecturer
thank u for mathematical explanation
Thank U Very Much Bro !! :D
simple and clear...just awssm
Thanks ...excellent video ..
Amazing video Buddy :)
really nice job, u helped me a lot
I am becoming a big time fan of your lessons. Do you have any lesson on AVL ? I was not able to find one from your list.
very clear. thank you!
Earned a subscription from me TOO :)
Thank You Sir!!
in case of IsEmpty() method, just return top == -1 without if and else statements
thank you a lot!!! a great series!
love your voice man 💯
Great job!
all are very good videos.i think better than my teacher (b tech 2nd year cse MIT manipal).what do u do for liviving man
lmao
is that seriously a question man?
he obviously is a programmer who also likes to teach
thats what he does for a living
Excellent.
Hi MyCodeSchool Instructor. I am having some trouble in my code. I don't know why but I'm getting a stack overflow error when I try compiling this code. Would you be able to compile it on your end and let me know what might be the issue. My source code is exactly the same as yours.
// Stack -- Array based implementation
#include
#define MAX_SIZE 5
int A[MAX_SIZE];
int top = -1;
void Push(int x) {
if (top = MAX_SIZE - 1) {
printf("Error: stack overflow
");
return;
}
A[++top] = x;
}
void Pop() {
if (top == -1) {
printf("Error: No element to pop
");
return;
}
top--;
}
int Top() {
return A[top];
}
void Print() {
int i;
printf("Stack: ");
for (i = 0; i
I think you might have figured it out by now but in your push function inside the if condition, you have used assignment operator(=) instead of relational operator(==).
Really good thank you.
Isn't stack a LIFO(Last in first out)? So shouldn't the order of the print function be 12 5 2?
I love your clases!
2:10 for empty array, index is -1...bc of imaginary array
thanks it was very helpfull
Good one!
Wonderful ... Thanks,,
damn this video is impressive, thanks a lot man
Thank you sir 😊
I think you forgot to include in the description the other array based implementation of stack in C. you only included the github link to the source code you wrote in the video.
just a question, how exactly do you create a new array when an array is full? we can't create a new node like what we did in linked list since these arrays are located in stack part of the memory, where linked list is in the heap, correct?
I mean, we can't write
if(top == max_size)-1{
int B[max_size*2]; or new B[max_size*2];
}
even if it's possible, when B is maxed out, there will be no int C[max_size*3].
any enlightment?
sir, may i know for such a excellent presentation which software do u use?