How to Implement a Stack in C (+ encapsulation)

---

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.



***

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:

To Support the Channel:
+ like, subscribe, spread the word

[zachzulanas]

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!

[axalius]

You're the only person on youtube, I'd take an online course from.

[Mishiman]

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

[johnnewton]

Great job! Could you make a video about "Difference between system call and function call" ?

[samuelrasquinha]

You really have a passion for code and teaching. Thanks a lot for these high quality, amazing and to the point videos. Good Luck.

[dbgn]

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.

[anjalibhatt]

Thank you for designing this course. Eagerly Waiting for it😇

[RngeRpidz]

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

[dedswift]

Amazing video. Can you please do one about graphs ?

[sumitbhosale]

Very Nice Explaination Sir. Thank You. Can You make video on graph in c. cause it is so hard to learn

[jakubstandarski]

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.

[gautamkumarshukla]

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;"

[TinBryn]

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.

[iversonvarun]

Love the content. I would rather be interested in a more advanced embedded systems/operating systems/C programming course.

[DreamVikings]

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.

[jayflaherty]

Have you thought about exploring Rust as a programming language to help students write safe, performant, and concurrent systems level code?

[bonbonpony]

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).

[frezajoe]

is it possible to implement a stack with different type of data in it? like how routine call stacks works under the hood

[eugenek.]

I have rewatched this part a thousand times and still struggling to understand... newnode -> next = head; head = newnode; what is that done for?

[rustycherkas]

@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.