2
\$\begingroup\$

In my intro CS class we're reviewing data structures. I'm currently working on implementing a stack using a linked list (LIFO) in C. I'd appreciate a review of the implementation as well as of my understanding of how a stack should work.

// This program is implementation of stack data structure
// via linked list (LAST IN FIRST OUT STRUCTURE) LIFO

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node
{
   char string[20];
   struct node *next;
} node;

node *push(char *element, node *head);
node *pop(node *head);
void destroy_stack(node *p);

int main(void)
{


    // create new stack
    node *stack = NULL;

    // push 6 "functions" to the stack
    char *function[6] = {"first funct", "second funct", "third funct",
    "fourth funct", "fifth funct", "sixt funct"};       
    for (int i = 0; i < 6; i++)
    {
        printf("function is : %s\n",function[i]);
        stack = push(function[i], stack);
        if (!stack)
        {
            fprintf(stderr,"Not enough memory space for new list");
            return 1;
        }
    }


    // display the stack
    for (node *temp = stack; temp != NULL; temp = temp -> next)
    {

        printf("Elements of the stack are: %s\n", temp -> string);
    }

    // pop the elements from the stack
    while (stack != NULL)
    {

        printf("Popped elemet is: %s\n", stack -> string);
        stack = pop(stack);


    }

    destroy_stack(stack);
    return 0;

} 

node *push(char *element, node *head)
{
    // create space for new element on stack
    node *temp = malloc(sizeof(node));
    if (!temp)
    {
        return NULL;
    }

    // if stack is empty
    if (head == NULL)
    {
        strcpy(temp -> string, element);
        temp -> next = NULL;
        return temp;
    }

    strcpy(temp -> string, element);
    temp -> next = head;
    return temp;
}

node *pop(node * head)
{
    // create a new head
    node *newHead = head->next;

    // pop the element from stack
    free(head);

    return newHead;

}

void destroy_stack(node *p)
{
    if ( p == NULL )
    {
        return;
    }
    else
    {
        destroy_stack(p -> next);
    }
    free(p);
}
\$\endgroup\$
2
\$\begingroup\$
  • push handles both branches in a curiously similar way. The only difference is that temp->next becomes NULL when head is NULL, and head otherwise. You should see the redundancy. It always becomes head no matter what head has been before. Consolidate the branches:

    node *push(char *element, node *head)
    {
        // create space for new element on stack
        node *temp = malloc(sizeof(node));
        if (!temp)
        {
            return NULL;
        }
    
        strcpy(temp -> string, element);
        temp -> next = head;
        return temp;
    }
    
  • Failure to allocate a node results in the entire list being lost. It seems a bit too drastic.

  • I do not endorse a recursive solution when a straightforward iterative one is available. Consider rewriting destroy_stack iteratively.

\$\endgroup\$
  • \$\begingroup\$ Thanks vnp. You gave a right pointers to correct my code. \$\endgroup\$ – Ivan Stimac Oct 9 '18 at 3:04
2
\$\begingroup\$

Redundant Code

In your push() function, you have these two cases which are redundant:

// if stack is empty
if (head == NULL)
{
    strcpy(temp -> string, element);
    temp -> next = NULL;
    return temp;
}

strcpy(temp -> string, element);
temp -> next = head;
return temp;

You can just remove the special case for head == NULL and be left with this, which handles both cases:

strcpy(temp -> string, element);
temp -> next = head;
return temp;

Better to iterate than recurse

Your destroy_stack() function is recursive, and that could be a problem if the stack has millions of elements because it could cause your program stack to overflow. It is easy enough to write an iterative version of that function instead, like this:

void destroy_stack(node *p)
{
    while (p != NULL)
    {
        node *next = p->next;
        free(p);
        p = next;
    }
}

Minor issues

  • In push(), using strcpy() is unsafe because element might exceed 20 characters and you will overflow your buffer.
  • In push(), if malloc() returns NULL, you return NULL and thus destroy/leak the rest of the stack. Perhaps you should just return head instead, to preserve the rest of the stack.
  • In pop(), you might want to check for head == NULL, otherwise you must depend on the caller to never pass NULL to your function.
\$\endgroup\$
  • \$\begingroup\$ Stop typing that fast! \$\endgroup\$ – vnp Oct 8 '18 at 21:30
  • \$\begingroup\$ Thanks JS1 I will use strncpy to prevent buffer overflow \$\endgroup\$ – Ivan Stimac Oct 9 '18 at 3:06
0
\$\begingroup\$

You really need to create a walk function. The code you have in main to display the contents 'knows' the internal structure of your stack. Instead you need a function that returns the next item on the stack given a current item

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.