Linked List - Stack Building - C - Is this tutorial correct

Question

I am trying to work a through a computer science course on coursebuffet.com, which referred me to saylor.org, which gave me this to learn about how to implement a stack with a linked list in C.

First, I think I understood the concept, but if you'd be so kind and scroll down in the link you will find at the end of it a link to a main file, with which you should test your implementation of it. And what absolutely baffles me for the last two days (yeah, that's how much time I already sank in this one problem) is the following passage:

/*
   * Initialize the stack.  Make it at least
   * big enough to hold the string we read in.
*/
StackInit(&stack, strlen(str));

I can't understand how to initialise a linked list. I mean, that's against its concept, isn't it? I would need to create struct Elements before filling them with push commands, but if I do that, I need to follow the stack in two directions. One directions for pushing it and the opposite direction for popping it. That would need two pointers. I thought the whole concept as described here would be one data element and one pointer per ADT-unit.

Can someone please explain this to me?

The sample code uses `gets()`: see [Why `gets()` is too dangerous to be used?](http://stackoverflow.com/questions/1694036/why-is-the-gets-function-dangerous-why-should-it-not-be-used) for why that's a bad idea (and what to do about it). — Jonathan Leffler, Jun 09 '16 at 18:36
If you're using an array-type stack, the length makes sense. If you're using a linked list stack, the length makes no sense. — Jonathan Leffler, Jun 09 '16 at 18:37
Note: Need `strlen(str)+1` to hold the string unless the LL implies the null character. — chux - Reinstate Monica, Jun 09 '16 at 19:17
Post is asking about the quality of an off-site resource. IMO, that is off-topic here. Post relevant information here. — chux - Reinstate Monica, Jun 09 '16 at 19:23

score 1 · Answer 1 · answered Jun 09 '16 at 18:15

When you initialize list to be length of the string you want to read, you will still have stack pointer pointing to the first element of the list. So basically nothing is lost. However you are correct, there is no point of doing something like that.

There is no need for double linked list. Stack pointer will always point to the first element. Basically whenever you want to push() you will add new node to the beginning of the list, and whenever you want to pop() you will remove first node of the list.

score 1 · Answer 2 · answered Jun 09 '16 at 18:22

Assume stack signifies LIFO operation only. i.e last in will be the first to get out.

Now Lets think how we would like to implement it.

First choice: Just have an fixed size internal array. In that case, you will never have the option to resize on the fly. So the comment above stack init is valid, that you should allocate a size that you think will be safe for the purpose.

Second Choice: Having an array, but using dynamic memory. In that case, even if you hit the limit of existing stack, you always can expand the size by realloc. So comment does not make sense.

Third Choice: Using linklist, So in theory, even if you initialize the stack with 0 size, it should expand on each node insertion, so the comment is misleading. Just to add, top is always the head of the linklist, and with every insertion, new node will become new head.

So to answer your question, the comment above is confusing and make sense only when internal implementation is array based.

But in common sense and general perception associated to Stack DS, Stack is DS which is always associated to Stack Depth. And when implementing this, its always safe to have max limit of elements that can be pushed and I guess, may be comment meant that.

To further illustrate it with an real example, you must have heard of callstack of functions, though in theory its expands but has MAX possible limit and thats the reason we see stack overflow error when we do infinite recursion.

Linked List - Stack Building - C - Is this tutorial correct

2 Answers2