Stack not popping correct values

Question

I cant seem to get my stack to operate as well... a stack. It seems to complie properly, and from what I understand the push and pop functions are written correctly (but they may be wrong).

I attempt to push 2 integers into the stack, and then pop them out again in order to test it, but it pops out what would appear to me to be a memory address in integer form, however this may not be the case. Either way it is not popping the correct value, and I cant find anything obvious with the code.

It may be important to note that the popped values do not seem to change through several iterations, but I think the malloc call would prevent this anyhow.. I am using the GNU GCC compiler included in Code:blocks.

below is the lib.c file:

#include "defs.h"
//Initialising the stack
TopStack* initTOS()
{
    TopStack* pTopStack;
    pTopStack = (TopStack*)malloc(sizeof(TopStack));
    return (pTopStack);
}

//Pushing an element onto the stack
void push(TopStack* ts, int val)
{
    if (ts->num == 0) {
        Stack* pNewNode;
        pNewNode = (Stack*)malloc(sizeof(Stack));
        pNewNode->val = val;
        pNewNode->next = NULL;
        ts->top = pNewNode;
        ts->num++;
    }
    else if (ts->num != 0) {
        Stack* pNewNode;
        pNewNode = (Stack*)malloc(sizeof(Stack));
        pNewNode->val = val;
        pNewNode->next = ts->top;
        ts->top = pNewNode;
        ts->num++;
    }
}

int pop(TopStack* ts)
{
    if (ts->num == 0) {
        printf("Can't pop, stack is empty!\n");
        exit(1);
    }
    else {
        Stack* pTemp;
        int RemovedValue;
        RemovedValue = pTemp->val;
        ts->top = pTemp->next;
        ts->num--;
        free(pTemp);
        return (RemovedValue);
    }
}

void testStack(TopStack* ts)
{
    int RemovedValue;
    push(ts, 1);
    push(ts, 2);
    printf("the popped value was %i\n", pop(ts));
    printf("the popped value was %i\n", pop(ts));
}

the structs are stored here in defs.h:

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <assert.h>
#include <stdbool.h>

#define MAX_EXPR 50

//struct that contains stack's element

typedef struct stack_elem {
    int val;
    struct stack_elem* next;
} Stack;

//struct that contains the pointer to the top of the stack

typedef struct {
    int num; //num of elements in stack
    Stack* top;
    ; //top of stack
} TopStack;

//ts=pointer to the top of stack, val=element to push

void push(TopStack* ts, int val); //push element on the stack

//prints the elements in the stack

void printStack(TopStack* ts);

// initialize the structure that will point to the top of the stack

TopStack* initTOS();

// a simple test for the stack

void testStack(TopStack* ts);

// ts=pointer to the top of stack

int pop(TopStack* ts); //returns element from top of stack
//  simple parser function for RPN expressions that assumes numbers have only one digit

void parseRPN(char expr[], TopStack* st);

// empties the stack using the pop operation

void emptyStack(TopStack* ts);

// performs the operation defined by character op on the elements on top of stack

void performOp(TopStack* st, char op);

and finally the main.c file:

#include "defs.h"

int main()
{
    TopStack* tp;

    tp = initTOS(); // initialize the top of stack structure
    testStack(tp); // this function tests your stack
    return EXIT_SUCCESS;
}

Answer 1

pTemp in the function pop is used while uninitialized. Using a value in uninitialized variable having automatic storage duration will invoke undefined behavior.

The line

Stack *pTemp;

should be

Stack *ptemp = ts->top;

Also you will have to initialize pTopStack->num to zero in initTOS(), or you will invoke undefined behavior again for using value in buffer allocated via malloc() and not initialized.

Another note is that they say you shouldn't cast the result of malloc() in C.

Answer 2

A big and major problem is that when you allocate memory with malloc, it does not initialize the memory in any way. The contents of the memory is indeterminate.

That means when you allocate memory for TopStack in the initTOS function, the structures top pointer will most likely not be NULL as well as num not being zero. Then you start to use these values and you will have undefined behavior.

You should initialize the memory in initTOS. Either by using calloc instead, or explicitly setting each member.

You seem to have problems with other uninitialized variables and data elsewhere as well.