How to Implement a Stack in C (+ encapsulation)
Вставка
- Опубліковано 30 тра 2024
- Patreon ➤ / jacobsorber
Courses ➤ jacobsorber.thinkific.com
Website ➤ www.jacobsorber.com
---
How to Implement a Stack in C (+ encapsulation) // This video shows you how to implement a stack two ways, in C - using an array and using a linked list.
Also, I'm planning a new course for July 2020, aimed at beginning computer science/engineering/programming students. Interested? Join my mailing list to get more information in the coming days.
jacobsorber.com/mailinglist/
***
Welcome! I post videos that help you learn to program and become a more confident software developer. I cover beginner-to-advanced systems topics ranging from network programming, threads, processes, operating systems, embedded systems and others. My goal is to help you get under-the-hood and better understand how computers work and how you can use them to become stronger students and more capable professional developers.
About me: I'm a computer scientist, electrical engineer, researcher, and teacher. I specialize in embedded systems, mobile computing, sensor networks, and the Internet of Things. I teach systems and networking courses at Clemson University, where I also lead the PERSIST research lab.
More about me and what I do:
www.jacobsorber.com
people.cs.clemson.edu/~jsorber/
persist.cs.clemson.edu/
To Support the Channel:
+ like, subscribe, spread the word
+ contribute via Patreon --- [ / jacobsorber ]
+ rep the channel with nerdy merch --- [teespring.com/stores/jacob-so...]
Source code is also available to Patreon supporters. --- [jsorber-youtube-source.heroku...]
you are honestly the reason why I actually like C and understand it, your videos are so clear and concise, I wish I could have you as an actual professor!
Thanks, Zach. Glad I could help. I'll be teaching OS this fall at Clemson, if you want to enroll. 🙂
@@JacobSorber wish I could :( I'm at UCSC, and I'm in my Systems class rn, your videos have been a godsend, especially the threading series, our professor had us build a server with sockets but barely went over them in class, more just the concepts.
You're the only person on youtube, I'd take an online course from.
corey schafer's python playlist is awesome too!
Jacob - go-to for learning C related stuff. Kevin Powell-CSS, Tech With Tim/ Corey Schaefer-Python. Most others are pretty random.
Hi Jacob ,I found your channel recently and you are amazing teacher. Can you make more in depth tutorials about operating systems ,networks ,compilers for those of us ,who can't affort college. I really think you are amazing teacher ,your students are lucky.
4:00 you could pass a pointer to an int to pop() so you can check for errors, like so
int pop(int *error) {
if (stack_empty) *error = 1; return 0;
*error = 0; return value;
}
and then
int error = 0;
int value = pop(&error);
if (error) { ... } else { // do something with the value... }
It's a bit more verbose but I think that's the best solution
just use errno :D
You really have a passion for code and teaching. Thanks a lot for these high quality, amazing and to the point videos. Good Luck.
Thanks!
Amazing job! Everything clarified in a very simple way and accordance with words of Albert Einstein: Everything should be made as simple as possible, but not simpler.
Thanks Jacob. Another great video.
Thanks, Tim.
thanks for making videos.
Love the content. I would rather be interested in a more advanced embedded systems/operating systems/C programming course.
Great job! Could you make a video about "Difference between system call and function call" ?
Absolutely. I just added it to my topic list.
yes please
Function call is when you call a function using the standard calling conventions (arguments should be pushed to the stack in reverse order, then the return adress, etc etc), a system call is when a program runs kernel code, there are two ways in wich this may happen:
The progran triggers an interrupt, that is a specific CPU instruction that interrupts the execution of the program and passes control to the os or the firmware, the OS generally takes the arguments for the interrupt from the cpu registers.
Interrupts are very slow thoug, so modern operating systems often load the part of the kernel code needed for syscalls into the memory allocated for the process, thus allowing the process to make systemcalls as if they were just another function without messing things up.
Thank you for designing this course. Eagerly Waiting for it😇
Hi Jacob!, I tried to implement the stacks with linked lists as you showed in the video, and everything worked like a charm, till I added a function that creates a dynamic array with malloc, now if I give that array a size bigger than the amount of elements in the stack it won't pop any element for some reason.
Any tips on how to solve this?
Amazing videos btw!
Amazing video. Can you please do one about graphs ?
Definitely. It's on the list of future video topics.
@12:30 - If the array's stack index started at zero (index of first store location), and it was incremented after a successful copy ( ie: stack[ idx++ ] = value; ) there would be no "funny business" initialising to -1...
Pre-decrement, if possible, when popping the top value off the stack: ( value = stack[ --idx ]; )
idx is the (unsigned) count of the number of items currently on the stack.
Bounds checking has been left as an exercise.
Vai ... Shei SHei!!! AWESOME!!
please make a video on block devices and interrupt handling
Hi! Nice tutorials. But I can't understand something: in 10:23 you passed *mystack pointer into a pop function. Than inside this function you used star operator with an arrow operator - after dereferencing a pointer basically. Why is it so? I mean *mystack isn't even a double pointer.
Hey Jason, great video! I am trying to follow your video creating stacks but I wish to create a stack for any data type. How can I do it please?
Very Nice Explaination Sir. Thank You. Can You make video on graph in c. cause it is so hard to learn
I'll add it to the list, and see what I can do.
Eagerly waiting for your course. Plz Use C/C++ for the codes in the course also.
But, of course.
for int pop() you could give it a pointer, if you can pop something you assign the value to that pointer, and return true
otherwise you return false
Hi Thijs. Good to see you again. Yes, you definitely can. I tried to keep things simple, so I don't confuse people who still are settling in with pointers. But, you're absolutely right.
Thankyou sir I watched upto implementation with array since I don't know what is linked list .I will watch it and then come back.basically I don't know nothing about programming can you please suggest me what to do
C actually has a really good encapsulation story, you can put in a header.
struct stack;
struct stack* new_stack();
void push_stack(struct stack *mystack, int value);
int pop_stack(struct stack *mystack);
void delete_stack(struct stack* mystack);
and that's it, with this you can write and compile (but not link) code using only this, not only do you not know the implementation, it doesn't even have to have been written at this point.
At line number 14 , top++, we have incremented the index . Then setting the value at that index.
Because of this we may miss the index 0 to set value at . I believe it should be " mystack[top++] = value;"
No, empty stack has top=-1, so first push will land at index 0.
Hi Jacob, thanks a lot for your great videos. I really like the setup you are using in visual studio code for your examples, can you just give more information about? Thanks in advance.
Thanks, Herr Entwickler. So, just to clarify, you are looking for more information about my setup? It's pretty standard. Are there specific things you are wondering about?
Hello. Im a scrub desperately researching stuff because i have an interview soon.
I believe that by "encapsulation" you actually mean "abstraction". Encapsulation, as I understand it (This is from an OOP video I watched) relates to access levels, but presenting the information in a way that hides the back of the code from the user / programmer working on code, is abstraction.
Again, im kind of new. Could be wrong.
01:25 That's why I often use a metaphor of a one-ended pipe/tube ;> Because this disallows cheating. The only way to get something out of the bottom of a one-ended pipe is to first remove all the objects that are lying upon it, one by one.
01:40 Well, there's also `peek`, which allows you to look at the element on the top of the stack without the need of removing it. Sure, it could be implemented with `pop` followed by a `push` of the same thing, but `peek`ing is faster and doesn't really break the invariants ;) Same thing with a variant of `peek` that can peek an `n`th element counting from the top of the stack, because it can be simulated with `n` calls to `pop` followed by `n` calls to `push` to restore the original layout of the stack. Another useful thing might be `dup` which duplicates whatever is currently on the top of the stack. This one is equivalent to popping it once, then pushing it twice. But yeah, in terms of interfaces, those could be implemented as external helper functions on top of `push` and `pop`, while `push` and `pop` are crucial. But I think there might be a couple of "methods" that are as crucial as `push` and `pop`, and can be considered a part of the stack's interface: checking whether it's full/overflown (unless it automatically grows), and checking whether the stack is empty (this one is quite crucial).
Can you do a video on alignment in c and _Alignas?
I have rewatched this part a thousand times and still struggling to understand... newnode -> next = head; head = newnode; what is that done for?
Drawing it out might help. Basically, you're adding the newnode to the front of the list. You do that by pointing the newnode's next pointer to the current head. And, then you move the head pointer to point to the new node. So, in the end, you have your head pointer pointing at the new node, and the chain remains intact.
@@JacobSorber Thank you very much for the reply. My main problem was that I imagined *next pointer of each node to point to new node that's being pushed, and not vice versa. I guess I've seen a lot of visualisations of stacks without actually saying that
Algorithms in C?
I suppose you could create a constructor method like
stack* newStack(){ stack* this = malloc(sizeof(stack); this->top = STACK_EMPTY; return this;}.
A little too C++-esque but I believe that makes the job.
I love watching your videos. One Question about encapsulation: In order to keep the implementation flexible we don't want to make the details public. So many projects are using void* as types. In your example the functions pop() and push() could also use a void* (or a typedef to void*) instead. What do you think of this approach?
Good question. I think it really depends on what you're trying to protect against. With void* you lose any type-checking help that the compiler could otherwise offer. And, it doesn't prevent people from messing with it, but rather just makes things opaque, which probably does discourage most people from messing with the internals. Whenever possible, I like to keep the compiler's type checking as an ally in my quest for robust code.
@@JacobSorber I agree, so far we talked about it in the team but we did not want to lose the help of the compiler. One option though would be to havean public and an internal header file. And for the public header-file we could replace the struct-def with void, because when linking to a library you don't need the internal struct anymore.
@@JacobSorber Yep, the compiler is your friend. :)
Nice video
Thanks, Ajil.
Have you thought about exploring Rust as a programming language to help students write safe, performant, and concurrent systems level code?
I have. I like Rust. As it becomes more mature and available on different platforms, it's definitely a solid option.
@@JacobSorber it hit v1.0 5 yrs ago (1.45 now), async/await is now in the core, and Microsoft has WinRT, and its available on all platforms LLVM is available. Looking forward to more Rust videos!
Dear Jacob Sorber
,
What determines in which direction the RAM function-stack will grow?
In my MCU (SPC58) stack grows from big RAM address to low RAM address.
Is that HW determined?
Is it possible to reverse function-call stack direction in compiler options?
Warm regards,
AB
Since push and pop are usually operations defined by the architecture, this question is very hardware dependent. Some processors grow the stack upward (8051, I think), and some are selectable (ARM, I believe).
Which editor is this ?
I watched your video about the linked list
I feel like a stack is just a kind of linked list
A stack is an abstraction, that can be implemented using a linked list or an array, or as a block of memory and architecture and register-assisted pointer arithmetic (as is the case for your program's call stack). But, yes, when you implement it with a linked list, it feels like a linked list with some restrictions applied to it.
@@JacobSorber thank you! I'm working on a project (sat solver) and this video is very helpful.
is it possible to implement a stack with different type of data in it? like how routine call stacks works under the hood
We will need void pointers and unions for that I'm sure...
Thanks for your instructive video!
I'm self-taught, and I'm reading the book "The C Programming Language" by R&K.
In this book on page 66, they implement a stack with an array for a Reverse Polish Calculator initialising the value of "top" at 0 instead of -1, actually "top" is named "sp" instead (stack position). So in push() you first push the value and then you increment "top", and in pop() you return the value with the index "top" decremented.
The question is, wich alternative is most commonly used? In addition: Is one better than the other?
I appreciate your time.
Greetings!
The implementation in the book is very good. Personally, I'd only use negative values, implicitly, for error handling but each his own. His pointer based implementation is probably the preferred/more efficient and flexible method.
If you start the stack 'index' at 0, it conceptually hangs together with all that you know about arrays in C. The stack index tells you how many items are on the stack (like strlen() tells you how many chars are in an array) and where the next item pushed will go:
int stack[ stackMax ], idx = 0;
bool push( int val ) { if( idx == stackMax ) return false; stack[ idx++ ] = val; return true; }
bool pop( int *val ) { if( idx == 0 ) return false; *val = stack[ --idx ]; return true; }
Ideally, idx would be an unsigned integer type because it is a 'counting number'.
You can have 2, 1 or 0 chickens, but you can't have -1 chicken...
Impressive how Matthew McConaughey knows about C
Pls make video about implement tree and graph in C.
It's on the list. If all goes well, you'll see it in the coming weeks.
Hey .. can you make a video on 'tries' please?
Yes, it's on my rather long list of future video topics. I'm not sure how long it will take me to get to it.
What kind f editor do you use I though it was atom at first sight
late reply but its vs code
If you have a function that should return a value, but should also return a value if something went wrong, the best way I've found of distinguishing the return value from an error, is to just use pointers.
If all is well, return a pointer to the value, else if something went wrong, return NULL.
That may not always work, and so sometimes I've had to get a little tricky, and instead make the function itself write to an address if something went wrong, like so:
int test(int *error) {
// Sorry, tabs in comment section no work :(
if (/* something went wrong */) {
*error = 1;
return 0;
}
return value; // Some normal value
}
After I watched this video, I was reminded or errno... Would it be wrong to use errno for these sorts of things? Or, what is the best way of dealing with this?
If you were going to return a pointer, I would just malloc space for the result, and return the pointer. That way NULL, could be your error state, and anything else is a valid result.
If you don't mind the extra time for a malloc call and the responsibility of eventually freeing it, then this is a really good way to go.
I personally am not crazy about the errno approach. Global variables come with a lot of baggage-probably not going to work well with threads. I would specifically avoid errno, since it's used by a lot of other functions, and you could run into issues.
You can also pass in a pointer to where you want to popped entry to go and return the success/failure as the return.
Lots of options.
Malloc would be slow. My advice would be to use an output parameter. Maybe something like:
int stack_pop(int* success);
int success;
int result = stack_pop(&success);
if (success == 0)
printf("stack empty
");
else
printf("result: %d
", result);
how do I make it work for any data type and not just int? please help me with this make a tutorial on using void pointers It would be really awesome please help
A void pointer is just an integer, that happens to be interpreted by the compiler as a memory address. So, moving from int to void * should change almost nothing in the code.
Thank You for Answering
I don't quite understand you would create a stack manually?
Isn't the stack something that the compiler creates to fit your code?
I understand to explain the logic of the stack, but why am I doing the job of the compiler?
Well, there is "THE STACK" meaning the call stack, and then there are stack data structures. The call stack is one stack and it is managed by the compiler. But, developers often use other stack data structures to manage various issues in their applications.
doesn't "stack *mystack" is the same with" node **mystack" since stack type defined as "typedef node * stack;" why do we need pointer to pointer?
To pass by reference in push and pop. Oherwise it won't update inside those function.
What’s the point (at 8:46) of the temp node?he creates it, doesn’t use it, then frees it… I don’t get what it’s there for…
tmp points to the 'head' node that is going to be free'd (temporarily hanging onto its address).
The head pointer is changed (and aren't we glad we kept the old value?!)
Now that the head pointer has been 'advanced', the node that WAS at the head is free'd.
i did not get (*stack)->value . Why are you deferencing a pointer but then using the arrow thing???
He's pointing to an item within the struct to which the pointer pointed.
Because stack is a pointer to a pointer. Meaning *stack is also a pointer.
I did not get why pop cant return bool similar to push?
pop is returning the thing that was removed from the stack. So, if pop returns bool, then you would need some other way to get the popped value back, maybe through a pointer passed in as an argument. You could do it that way, I was just trying to keep things simple.
@@JacobSorber ah makes sense i thought it was more a "confirmation" function that says if the element was removed. Thanks!
Also What is search.h in c programming.
Header file for built-in hash table functionality. (XPG4.2 standard)
you could use encapsulation by hiding some of the implementation in a c file
I'm still scratching my head. Tutorial was good but I didn't really understand. I might have to practice.
Practice is good, but feel free to ask about anything that's confusing.
@@JacobSorber Okay so I tried the linked list one and I had trouble getting it. Then I went and wrote myself explanations for each line. And I think I get it somewhat now. Its not easy but atleast it makes sense. Will take me a few more goes before I understand properly.
I suck at Data Structures. I slept through most ds classes throughout my semester. Regret it now.
how to implement a stack in javascript:
const stack = [];
How to create a stack in c: use recursion in a smart way ;-)
Can you explain? kinda a newb at data structures but I never knew you could implement a stack using recursion
I know you just want to show what a stack is. However, could you please not make examples using global variables? It encourages people who don't fully know all about global variables to use them. It's bad if they don't know there can be only one definition for each global variable anywhere in the program *unless* it has internal linkage (and even so there can be only one definition per translation unit). See, global variables are not that simple to people who don't understand linkages.
bbbbbbbbbbbbbb