Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

Problem with Stack Pop in C function

c stack pop

Best Answer gonerogue, 23 December 2013 - 07:28 AM

In your code:

void push(Element** sp, int newData){
	Element oldHead = **sp;
	Element newElement = {&oldHead,newData};
	*sp = &newElement;
}

You should make sure that the pointers, in the linked list, points to objects that are not locals.

For example, oldHead is local in the function push(). However, you assign its address to newElement's next pointer. Than, you set the head of the list to point to newElement (which is also local to the push() function).

You should not do this. After the function push() finishes, its stack frame has gone and also the local objects stored on that frame.

Usually, the nodes in a container (a linked list in our case), should be dynamically allocated objects (on the heap).

Objects allocated on the heap will live until you free the memory allocated for them (in my example we free the memory allocated for the list elements in the destroy() function).

Go to the full post


This topic has been archived. This means that you cannot reply to this topic.
5 replies to this topic

#1 Pally

Pally

    CC Devotee

  • Senior Member
  • PipPipPipPipPipPip
  • 413 posts

Posted 22 December 2013 - 02:00 PM

Appreciate your help as always,

 

Tried writing a simple push and pop function in C but running into issues poping off the value, I'm using a linked list as the data structure.

 

Basically all I wanted to do is get the address of the second element in the linked list and set that as the stack pointers new address to point to but something is going wrong.

 

Heres the code:

#include <stdio.h>

typedef struct Element{
	struct Element* next;
	int data;
} Element;

void push(Element** sp, int newData){
	Element oldHead = **sp;
	Element newElement = {&oldHead,newData};
	*sp = &newElement;
}
void pop(Element** sp){
	*sp = (**sp).next;
}

int main(int argc, int** argv){
	Element e = {0,55};
	Element* sp = &e;
	printf("SP pointing to %x, data in this element is: %d\n",sp,sp->data);
	push(&sp,66);
	printf("After Push SP pointing to %x, data in this element is: %d\n",sp,sp->data);
	printf("After Push second element in link address is %x, data in this element is: %d\n",sp->next,sp->next->data);

	pop(&sp);
	printf("After Pop SP pointing to %x, data in this element is: %d\n",sp,sp->data);



} 

Heres the output:

SP pointing to f19d0fa0, data in this element is: 55
After Push SP pointing to f19d0f50, data in this element is: 66
After Push second element in link address is f19d0f60, data in this element is: 55
After Pop SP pointing to f19d0f60, data in this element is: -241365096


Your Friendly Neighborhood Pally

#2 gonerogue

gonerogue

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 197 posts

Posted 23 December 2013 - 12:31 AM

Use dynamic allocation to allocate the elements of your stack data structure.

For example: 

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

typedef struct Element{
    struct Element* next;
    int data;
} Element;

void push(Element** sp, int newData){
   Element* oldHead = *sp;
   (*sp) = malloc(sizeof(Element));
   (*sp)->next = oldHead;
   (*sp)->data = newData;
}
Element* pop(Element** sp){
    Element* top = *sp;
    *sp = (**sp).next;
    return top;
}

void destroy(Element** sp) {
    Element* top = pop(sp);
    while (top) {
        free(top);
        top = (*sp) ? pop(sp) : NULL;
    }
}

int main(int argc, int** argv){
    Element* top;
    Element* sp = malloc(sizeof(Element));
    sp->next = NULL;
    sp->data = 55;
    printf("SP pointing to %x, data in this element is: %d\n",sp,sp->data);
    push(&sp,66);
    printf("After Push SP pointing to %x, data in this element is: %d\n",sp,sp->data);
    printf("After Push second element in link address is %x, data in this element is: %d\n",sp->next,sp->next->data);

    top = pop(&sp);
    printf("The top element is %d\n", top->data);
    printf("After Pop SP pointing to %x, data in this element is: %d\n",sp,sp->data);
    
    free(top);
    
    destroy(&sp);
    return 0;
}  

Edited by xyv123, 23 December 2013 - 01:56 AM.


#3 Pally

Pally

    CC Devotee

  • Senior Member
  • PipPipPipPipPipPip
  • 413 posts

Posted 23 December 2013 - 06:43 AM

Thank you for you help, any chance you can elaborate why my solution would not work?

 

I knew mine might have some memory leaks but I still thought it would work in general since when I created a new struct I thought C would definitely not delete the old data but I thought it would be smart enough to give new items their own space in memory?

 

thanks again


Edited by Pally, 23 December 2013 - 06:44 AM.

Your Friendly Neighborhood Pally

#4 gonerogue

gonerogue

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 197 posts

Posted 23 December 2013 - 07:28 AM   Best Answer

In your code:

void push(Element** sp, int newData){
	Element oldHead = **sp;
	Element newElement = {&oldHead,newData};
	*sp = &newElement;
}

You should make sure that the pointers, in the linked list, points to objects that are not locals.

For example, oldHead is local in the function push(). However, you assign its address to newElement's next pointer. Than, you set the head of the list to point to newElement (which is also local to the push() function).

You should not do this. After the function push() finishes, its stack frame has gone and also the local objects stored on that frame.

Usually, the nodes in a container (a linked list in our case), should be dynamically allocated objects (on the heap).

Objects allocated on the heap will live until you free the memory allocated for them (in my example we free the memory allocated for the list elements in the destroy() function).


Edited by xyv123, 23 December 2013 - 07:38 AM.


#5 Pally

Pally

    CC Devotee

  • Senior Member
  • PipPipPipPipPipPip
  • 413 posts

Posted 23 December 2013 - 08:55 AM

In your code:

void push(Element** sp, int newData){
	Element oldHead = **sp;
	Element newElement = {&oldHead,newData};
	*sp = &newElement;
}

You should make sure that the pointers, in the linked list, points to objects that are not locals.

For example, oldHead is local in the function push(). However, you assign its address to newElement's next pointer. Than, you set the head of the list to point to newElement (which is also local to the push() function).

You should not do this. After the function push() finishes, its stack frame has gone and also the local objects stored on that frame.

Usually, the nodes in a container (a linked list in our case), should be dynamically allocated objects (on the heap).

Objects allocated on the heap will live until you free the memory allocated for them (in my example we free the memory allocated for the list elements in the destroy() function).

 

Thank you for explaining, as soon as I read "locals" I knew where I went wrong as the stack will reclaim that space. 

 

Thanks again for your help, I'm trying to refresh my knowledge of C before I learn C++, I remember I loved C for a while but its been a good two years sense I actually used it. This helps wonders thanks again


Your Friendly Neighborhood Pally

#6 gonerogue

gonerogue

    CC Addict

  • Advanced Member
  • PipPipPipPipPip
  • 197 posts

Posted 23 December 2013 - 11:30 AM

You are most welcome.


Edited by xyv123, 23 December 2013 - 11:30 AM.





Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download