Incorrect data is being pushed into stack implemented using pointers

Question

I have implemented stack using pointers. I have been trying to generalize it for use with arbitrary data type. I have tried but cannot figure out the reason incorrect data is being pushed onto the stack.

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

enum action {START, PUSH, POP, TOP, LENGTH, QUIT, END};
enum status {SUCCESS, FAILURE};

typedef struct node {
    void *data;
    struct node *lower;
} stack_node;

typedef struct stack {
    size_t elem_size;
    size_t stack_size;
    stack_node *top;
} stack_struct;

void clear_screen(void)
{
    system("cls");
}

static enum action get_user_action(void)
{
    int choice = START;
    do {
        clear_screen();
        printf("%d Push data\n"
               "%d Pop Data\n"
               "%d See the top of the stack\n"
               "%d See the length of the stack\n"
               "%d Exit\n\n"
               "Enter your choice -> ", PUSH, POP, TOP, LENGTH, QUIT);
        scanf("%d", &choice);
    } while (!(START < choice && choice < END));
    return (enum action) choice;
}

enum status stack_create(stack_struct **stack, size_t elem_size)
{
    (**stack).elem_size = elem_size;
    (**stack).stack_size = 0;
    (**stack).top = NULL;
    return SUCCESS;
}

enum status push(stack_struct **stack, void *data)
{
    stack_node *node = malloc(sizeof(node));
    if (node == NULL) {
        return FAILURE;
    }

    node->data = malloc(sizeof((**stack).elem_size));
    if (node->data == NULL) {
        return FAILURE;
    }
    memcpy(node->data, data, (**stack).elem_size);

    if ((**stack).top == NULL) {
        node->lower = NULL;
    } else {
        node->lower = (**stack).top;
    }
    (**stack).top = node;
    (**stack).stack_size += 1;
    return SUCCESS;
}

enum status pop(stack_struct *stack, void *data)
{
    if (stack->top == NULL) {
        return FAILURE;
    }
    stack_node *node = stack->top;
    memcpy(data, node->data, stack->elem_size);
    stack->top = node->lower;

    free(node->data);
    free(node);

    stack->stack_size -= 1;
    return SUCCESS;
}

enum status peek(stack_struct *stack, void *data)
{
    if (stack->top == NULL) {
        return FAILURE;
    }
    memcpy(data, stack->top->data, stack->elem_size);
    return SUCCESS;
}

void stack_delete(stack_struct *stack)
{
    while (stack->top != NULL)
    {
        stack_node *node = stack->top;
        stack->top = stack->top->lower;
        free(node->data);
        free(node);
    }
}

int main(void)
{
    enum action choice;
    stack_struct *stack = malloc(sizeof(stack_struct));
    if (stack == NULL)
    {
        printf("Not enough memory\n");
        return 1;
    }
    stack_create(&stack, sizeof(int));

    while ((choice = get_user_action()) != QUIT) {
        clear_screen();
        int data;
        switch (choice) {

            case PUSH:
                printf("Enter data to be pushed -> ");
                scanf("%d", &data);
                if (push(&stack, &data) == SUCCESS){
                    printf("%d pushed onto the stack", (int)stack->top->data);
                } else {
                    printf("Not enough memory\n");
                }
                break;

            case POP:
                if (pop(stack, &data) == SUCCESS){
                    printf("The data is %d\n", data);
                } else {
                    printf("Stack underflow\n");
                }
                break;

            case TOP:
                if (peek(stack, &data) == SUCCESS){
                    printf("The data at top is %d\n", data);
                } else {
                    printf("Nothing in the stack\n");
                }
                break;

            case LENGTH:
                printf("Length is %d\n", stack->stack_size);
                break;

            default:
                assert(!"You should not have reached this.\n");

        }
        stack_delete(stack);
        getchar();
        getchar();
    }
}

I push 234 and get a garbage value.

Update 1

I have a working copy of stack using pointers. It isn't for arbitrary data types but only for int. It can be viewed on codereview where I got the idea to make it for arbitrary data.

Update 2

After p0w pointed out that the printf in the main was incorrect I correct that. I also changed the pop, peek and stack_delete function so that pointer to pointer to struct is passed.

printf shows that correct data is being passed but pop and peek don't think so.

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

enum action {START, PUSH, POP, TOP, LENGTH, QUIT, END};
enum status {SUCCESS, FAILURE};

typedef struct node {
    void *data;
    struct node *lower;
} stack_node;

typedef struct stack {
    size_t elem_size;
    size_t stack_size;
    stack_node *top;
} stack_struct;

void clear_screen(void)
{
    system("cls");
}

static enum action get_user_action(void)
{
    int choice = START;
    do {
        clear_screen();
        printf("%d Push data\n"
               "%d Pop Data\n"
               "%d See the top of the stack\n"
               "%d See the length of the stack\n"
               "%d Exit\n\n"
               "Enter your choice -> ", PUSH, POP, TOP, LENGTH, QUIT);
        scanf("%d", &choice);
    } while (!(START < choice && choice < END));
    return (enum action) choice;
}

enum status stack_create(stack_struct **stack, size_t elem_size)
{
    (**stack).elem_size = elem_size;
    (**stack).stack_size = 0;
    (**stack).top = NULL;
    return SUCCESS;
}

enum status push(stack_struct **stack, void *data)
{
    stack_node *node = malloc(sizeof(node));
    if (node == NULL) {
        return FAILURE;
    }

    node->data = malloc(sizeof((**stack).elem_size));
    if (node->data == NULL) {
        return FAILURE;
    }
    memcpy(node->data, data, (**stack).elem_size);

    if ((**stack).top == NULL) {
        node->lower = NULL;
    } else {
        node->lower = (**stack).top;
    }
    (**stack).top = node;
    (**stack).stack_size += 1;
    return SUCCESS;
}

enum status pop(stack_struct **stack, void *data)
{
    if ((**stack).top == NULL) {
        return FAILURE;
    }
    stack_node *node = (**stack).top;
    memcpy(data, node->data, (**stack).elem_size);
    (**stack).top = node->lower;
    node->lower = NULL;

    free(node->data);
    free(node);

    (**stack).stack_size -= 1;
    return SUCCESS;
}

enum status peek(stack_struct **stack, void *data)
{
    if ((**stack).top == NULL) {
        return FAILURE;
    }
    memcpy(data, (**stack).top->data, (**stack).elem_size);
    return SUCCESS;
}

void stack_delete(stack_struct **stack)
{
    while ((**stack).top != NULL)
    {
        stack_node *node = (**stack).top;
        (**stack).top = (**stack).top->lower;
        free(node->data);
        free(node);
    }
}

int main(void)
{
    enum action choice;
    stack_struct *stack = malloc(sizeof(stack_struct));
    if (stack == NULL)
    {
        printf("Not enough memory\n");
        return 1;
    }
    stack_create(&stack, sizeof(int));

    while ((choice = get_user_action()) != QUIT) {
        clear_screen();
        int data;
        switch (choice) {

            case PUSH:
                printf("Enter data to be pushed -> ");
                scanf("%d", &data);
                if (push(&stack, &data) == SUCCESS){
                    printf("%d pushed onto the stack\n", *(int *)stack->top->data);
                    printf("%u is top of stack", stack->top);
                } else {
                    printf("Not enough memory\n");
                }
                break;

            case POP:
                if (pop(&stack, &data) == SUCCESS){
                    printf("The data is %d\n", data);
                } else {
                    printf("Stack underflow\n");
                }
                break;

            case TOP:
                if (peek(&stack, &data) == SUCCESS){
                    printf("The data at top is %d\n", data);
                } else {
                    printf("Nothing in the stack\n");
                }
                break;

            case LENGTH:
                printf("Length is %d\n", stack->stack_size);
                break;

            default:
                assert(!"You should not have reached this.\n");

        }
        stack_delete(&stack);
        getchar();
        getchar();
    }
}

Put the delete_stack funciton outside the loop.

Uchia Itachi
– Uchia Itachi

2013-08-04 11:08:58 +00:00
Commented Aug 4, 2013 at 11:08 — Uchia Itachi
– Uchia Itachi, Commented Aug 4, 2013 at 11:08
Why is this code crashing on VS2010 but not on GCC?

Uchia Itachi
– Uchia Itachi

2013-08-04 12:55:28 +00:00
Commented Aug 4, 2013 at 12:55 — Uchia Itachi
– Uchia Itachi, Commented Aug 4, 2013 at 12:55

P0W · Accepted Answer · 2013-08-04 10:35:32Z

3

Your struture data is void * so fix printf

printf("%d pushed onto the stack", *(int *)stack->top->data);

However, there seems to be other problems too for other stack operations.

Also if you're planning for making it as a generic Stack, why %d in printf ?

This you might need to re-visit.

edited Aug 4, 2013 at 10:35

answered Aug 4, 2013 at 10:27

P0W

48.1k9 gold badges78 silver badges124 bronze badges

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

9 Comments

Aseem Bansal Over a year ago

This %d was used just for testing purpose. After this correction the correct data is being shown by the printf but the pop and peek are still not considering that it has been placed. I'll add updated code to the question.

P0W Over a year ago

@AseemBansal are you new on SO, doesn't look like, if you fix this, theres' no question at all. Please use another post of some new issues ?

Uchia Itachi Over a year ago

There is crash in stack_delete function while doing free(node)

Aseem Bansal Over a year ago

@UchiaItachi I didn't get that far. pop isn't recognizing that I pushed something

Uchia Itachi Over a year ago

Shouldn't delete_stack be outside the while loop?

|

Uchia Itachi · Accepted Answer · 2013-08-04 13:20:36Z

1

In addtion to the points mentioned by P0W and me, there is bug in your code which is leading to a crash on VS2010 but not in GCC.

While creating the stack_node object in push function dynamically you're passing the sizeof(node) where node is a pointer of stack_node instead you should've passed sizeof(stack_node).

The amount of memory malloc allocates in both the cases is different. In the first one you get 4 bytes(beacuse of size of pointer) and in the second one you get 8 bytes (because of size of stack_node).

In this case you don't get to access the second member of stack_node object which is struct node *lower. Also, this might need to undefined behavior as you're accessing the memory which is not allocated.

Finally at the statement free(node) it crashes.

I don't know the exact reason as to why this is happening and also i don't know how free works behind the scenes.

I would like to know the reason in this case.

answered Aug 4, 2013 at 13:20

Uchia Itachi

5,3352 gold badges26 silver badges26 bronze badges

2 Comments

Aseem Bansal Over a year ago

I had no idea that this bug was present. I have no idea as to why it is giving an error in VS2010 but working in gcc. You can ask a question on stackoverflow with a link to this code and ask why. I did that for a question whose explanation I didn't understand.

Aseem Bansal Over a year ago

If you do ask a question then please post a comment with the link. I'm also interested how that worked in gcc when it is actually wrong.

Collectives™ on Stack Overflow

Incorrect data is being pushed into stack implemented using pointers

2 Answers 2

9 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

9 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related