Implementing a stack using a linked-list

Question

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);
}

vnp · Accepted Answer · 2018-10-08 23:57:10Z

2

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.

edited Oct 8, 2018 at 23:57

answered Oct 8, 2018 at 21:29

vnp

58.7k4 gold badges55 silver badges144 bronze badges

\$\begingroup\$ Thanks vnp. You gave a right pointers to correct my code. \$\endgroup\$

Ivan Stimac
– Ivan Stimac

2018-10-09 03:04:18 +00:00
Commented Oct 9, 2018 at 3:04

Add a comment |

JS1 · Accepted Answer · 2018-10-08 21:27:59Z

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.

\$\begingroup\$ Stop typing that fast! \$\endgroup\$

vnp
– vnp

2018-10-08 21:30:19 +00:00
Commented Oct 8, 2018 at 21:30 — vnp
– vnp, Commented Oct 8, 2018 at 21:30
\$\begingroup\$ Thanks JS1 I will use strncpy to prevent buffer overflow \$\endgroup\$

Ivan Stimac
– Ivan Stimac

2018-10-09 03:06:00 +00:00
Commented Oct 9, 2018 at 3:06 — Ivan Stimac
– Ivan Stimac, Commented Oct 9, 2018 at 3:06

Dan Oberlam · Accepted Answer · 2018-10-08 23:56:38Z

0

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

edited Oct 8, 2018 at 23:56

Dan Oberlam

8,0492 gold badges33 silver badges74 bronze badges

answered Oct 8, 2018 at 22:00

pm100

8414 silver badges8 bronze badges

Add a comment |

Stack Exchange Network

Implementing a stack using a linked-list

3 Answers 3

Redundant Code

Better to iterate than recurse

Minor issues

You must log in to answer this question.

Hot Network Questions

Implementing a stack using a linked-list

3 Answers 3

Redundant Code

Better to iterate than recurse

Minor issues

You must log in to answer this question.

Related

Hot Network Questions