Linked List implementation of Stack

Question

I am trying to implement stack as a linked list. Here is my current code:

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

typedef struct node {
    int data;
    struct node* link;
} Node;

typedef Node* list;

list head;

void push(list top, int item) {
    if (head == NULL) {
        head = (list) malloc(sizeof(Node));
        head->data = item;
        head->link = NULL;
        top = head;
    } else{
        list temp = (list) malloc(sizeof(Node));
        temp->data = item;
        temp->link = top;
        top = temp;
    }
}

int pop(list top) {
    if (top == NULL) {
        printf("stack is empty");
        /*int tdata=top->data;
        top=top->link;
        return tdata;*/
    } else {
        int tdata = top->data;
        top = top->link;
        return tdata;
    }
}

void display(list top){
    while (top != NULL) {
        printf("%d", top->data);
        top = top->link;
    }
}

int main() {
    int ch, item;
    list top;

    for (;;) {
        printf("1.push\t2.pop\t3.display\t4.exit");
        scanf("%d", &ch);
        switch (ch) {
            case 1:
                printf("enter the element to be pushed");
                scanf("%d",&item);
                push(top,item);
                break;
            case 2:
                item=pop(top);
                printf("element popped is: %d",item);
                break;
            case 3:
                display(top);
                break;
            case 4:
                exit(0);
                break;
            default:
                printf("enter valid choice");
        }
    }
}

When I press '2' the pop method is called, but irrespective of whatever item is on the top it prints the message "element popped is: 11". When I press '3' for the display method, I get "segmentation fault(core dumped)". Why is this happening? What modifications are needed to get this code working?

Welcome to Stack Overflow! It sounds like you may need to learn how to use a debugger to step through your code. With a good debugger, you can execute your program line by line and see where it is deviating from what you expect. This is an essential tool if you are going to do any programming. Further reading: How to debug small programs. — Paul R
– Paul R, Commented Oct 3, 2016 at 18:05
There seems to be some confusion whether the list is top (main) or head (global). — Weather Vane
– Weather Vane, Commented Oct 3, 2016 at 18:13
It is never a good idea to typedef a pointer. As a result, in push your list head is not finding its way back to top in main, it only alters the local copy, while in main the local var top remains uninitialised giving undefined behaviour. — Weather Vane
– Weather Vane, Commented Oct 3, 2016 at 18:21
You also have a memory leak, because in pop you do not free the memory that was allocated. — Weather Vane
– Weather Vane, Commented Oct 3, 2016 at 18:27

Weather Vane · Accepted Answer · 2016-10-03 19:41:25Z

1

I have made several alterations to your program. The most important is to pass a pointer to the list head to functions, which itself is a pointer, so that it can be altered by the function.

I also removed the global head and initialised the local top. I have commented in the code about other matters.

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

typedef struct node {
    int data;
    struct node *link;
} Node;                                 // removed pointer type to Node

void push(Node **top, int item) {       // takes address of the pointer
    Node *temp= malloc(sizeof(Node));   // do not cast malloc
    if(temp == NULL)                    // check that malloc did work
        exit(42);
    temp->data = item;                  // no need for separate clause at first push
    temp->link = *top;                  // link is previous top
    *top = temp;                        // top is new struct, pass it back
}

int pop(Node **top) {                   // takes address of the pointer
    int tdata;
    Node *temp;
    if (*top == NULL) {
        printf("stack is empty\n");     // added newline here and other places
        return 0;
    }
    tdata = (*top)->data;               // collect the data
    temp = (*top)->link;                // remember the next list item
    free(*top);                         // give memory back
    *top = temp;                        // pass new top back to caller
    return tdata;
}

void display(Node *top){
    while (top != NULL) {
        printf("%d ", top->data);       // added spacing
        top = top->link;
    }
    printf("\n");                       // added newline
}

int main(void) {
    int ch, item;
    Node *top = NULL;                   // initialise the list !!

    do {
        printf("1.push  2.pop  3.display  4.exit  ");
        scanf("%d", &ch);
        switch (ch) {
            case 1:
                printf("enter the element to be pushed ");
                scanf("%d",&item);
                push(&top,item);        // pass address so pointer can be updated
                break;
            case 2:
                item=pop(&top);         // pass address so pointer can be updated
                printf("element popped is: %d\n",item);
                break;
            case 3:
                display(top);
                break;
            case 4:
                break;
            default:
                printf("enter valid choice\n");
        }
    } while(ch != 4);                   // changed the loop style
}

edited Oct 3, 2016 at 19:41

answered Oct 3, 2016 at 18:56

Weather Vane

34.8k7 gold badges43 silver badges63 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

sameer soin Over a year ago

thanks for your help.I really appreciate the effort you took in providing the correct code.By the way don't you think when we call the display method once in your code it will alter the value of top and after that if we pop it will show that stack is empty.

Weather Vane Over a year ago

@sameersoin the display method does not pass the pointer-to-pointer, so the list head cannot be altered. You are making the same mistake as you originally did: the function argument is a copy of what was passed. The reason for the double pointer (which display does not take) is so that the passed value can be modified. Another way to do this would be to pass a single pointer, and return a new pointer as the function result which would be assigned to top in main. But in the case of pop, the value popped would then need to be a * arguement. If you like this answer please "accept" it.

Weather Vane Over a year ago

Please notice that it is display(top) and not display(&top) as the push and pop functions use.

sameer soin Over a year ago

ohh yea...sorry my bad...got it

PazO · Accepted Answer · 2016-10-03 18:38:11Z

0

What is happening is that you simply do not initialize or set any value to your list pointer top.
Take a good look at your insertion function push. It receives a pointer. If you want to send your member top as an [out] paramter to this function you should send a pointer to a pointer (**) or a reference to a pointer (*&).
Sending top like this does not modify its value and leaves it with junk as this variable was also never initialized...

answered Oct 3, 2016 at 18:38

PazO

1,4861 gold badge14 silver badges33 bronze badges

Collectives™ on Stack Overflow

Linked List implementation of Stack

2 Answers 2

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related