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!
@@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.
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
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.
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.
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.
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.
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;"
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
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.
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.
@@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!
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.
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.
@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.
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).
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.
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
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?
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!
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.
@@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.
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.
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.
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).
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);
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.
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.
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...
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.
