Thread: C Stack question

  1. #1
    Registered User
    Join Date
    May 2011
    Posts
    9

    C Stack question

    I'm having a bit of a problem with pushing an item onto a stack.
    Code:
    void push( StackNodePtr *topPtr, char value ){
    //Push a value on the stack.
        StackNode top;                        //Create node
        top.data = value;                     //Put data in top
        StackNode *Snode = &topPtr;          //make Snode point to topPtr
        top.nextPtr = &Snode;              //Make top point to Snode
        topPtr = ⊤                        //make topPtr(head) point to top.
    }
    Could anyone help me to figure out whats going on here?

    Is it because I'm pointing to topPtr so when the value changes in topPtr, so would Snode and therefore top would change too?

    This is the code for the Stack struct

    Code:
    struct stackNode {
        char data;
        struct stackNode *nextPtr;
    };
        typedef struct stackNode StackNode;
        typedef StackNode *StackNodePtr;
    Thanks for your time
    Last edited by Millsie; 05-28-2011 at 10:34 PM.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Given your function header, there is no way to change the top pointer, which is pretty useless when you're dealing with the stack. Either you pass the topPtr by pointer, or you return the new top.

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > typedef StackNode *StackNodePtr;
    First, you should delete this line, and then go through the rest of your code changing say

    void push( StackNodePtr *topPtr, char value )
    to
    void push( StackNode **topPtr, char value )

    Creating a whole new typedef just for a pointer (unless it's a function pointer) is more trouble than it's worth. Rather than being able to see instantly how many levels of indirection there is, you have to instead work through a maze of typedefs instead.
    Also, when you start adding qualifiers like const, it gets horribly messy.

    > StackNode top; //Create node
    No, this is a local variable that will disappear when the function exits.
    StackNode *newNode = malloc( sizeof *newNode ); // Create node

    Now initialise these members, and link into your existing list.

    Finish with
    *top = newNode;
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by Millsie View Post
    I'm having a bit of a problem with pushing an item onto a stack.
    Code:
    void push( StackNodePtr *topPtr, char value ){
    //Push a value on the stack.
        StackNode top;                        //Create node
        top.data = value;                     //Put data in top
        StackNode *Snode = &topPtr;          //make Snode point to topPtr
        top.nextPtr = &Snode;              //Make top point to Snode
        topPtr = ⊤                        //make topPtr(head) point to top.
    }
    It should also be noted that top is local to this function, and is destroyed when this function ends, so even if you did use a pointer to a pointer as tabstop suggested, your stack would still be messed up when this function returns.


    Quzah.
    Hope is the first step on the road to disappointment.

  5. #5
    Registered User
    Join Date
    May 2011
    Posts
    9
    Thanks for all the replies, I don't think I can modify any of the code of the struct or function headers - since its for an assignment.

    I've worked with stacks before but this one has really got me beat.

    I've been working on this problem all day, so it literally can't be done without modifying his code?

    What a mission this has become...

  6. #6
    Registered User
    Join Date
    May 2010
    Location
    Naypyidaw
    Posts
    1,314
    >>I've been working on this problem all day, so it literally can't be done without modifying his code?
    You want to fix the code without modifying anything?
    Your function is as bad as returning address of local variable.

  7. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    You can get away without changing the function prototype since as mentioned above you do have a pointer to a pointer after all. What you cannot do is reuse the same node over and over and over and over and over and over and over and over and over and over again (which is likely what is going to happen here). You need to use malloc() to give you a node that lasts forever.

  8. #8
    Registered User
    Join Date
    May 2011
    Posts
    9
    Okay, malloc(), Got it. Did some research and now my push function looks like this:
    Code:
    void push( StackNodePtr *topPtr, char value ){
    //Push a value on the stack.
        StackNode *newNode;
        newNode = malloc(sizeof(StackNode));
        newNode -> data = value;
        newNode -> nextPtr = topPtr;
        topPtr = newNode;
    }
    Now, I don't actually know if that works, my guess is that it doesn't but that's probably going to be my best shot...
    Here's my current code for pop()
    Code:
    char pop( StackNodePtr *topPtr ){
    //Pop a value off the stack.
        char data;
        StackNode *temp;
        temp = topPtr;
    
        data = temp->data;
        printf(" %c \n", data);     //For debugging -.-
        topPtr = temp -> nextPtr;
        free(temp);
        return data;
    However either both of them or one of them just doesn't work...

    Any more hints anyone?
    Last edited by Millsie; 05-29-2011 at 07:56 AM.

  9. #9
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    You need to change topPtr when you pop, since the top of the stack is now different than it used to be.

  10. #10
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > topPtr = newNode;
    Are you getting any warnings when you do this?

    If so, what are they?

    Do you understand what
    *topPtr = newNode;
    might be?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  11. #11
    Registered User
    Join Date
    May 2011
    Posts
    9
    Quote Originally Posted by Salem View Post
    topPtr = newNode;
    Are you getting any warnings when you do this?

    If so, what are they?
    Yes, I got one warning an "assignment from incompatible pointer type".
    How serious is this warning? (I just went through and fixed a few pointer errors)

    Quote Originally Posted by Salem View Post
    Do you understand what
    *topPtr = newNode;
    might be?
    Once I changed it to your code above the warning above went away.
    I'm guessing that *topPtr would change what the first node is? (topPtr = topPtr, *topPtr = newNode(the firstnode))
    but I thought it would have to be something like topPtr = &newNode; (looking through some of the book examples of linked lists and whatnot - now that I think of it I wonder if *topPtr = &newNode is possible, meh I'll check after my SQL stuff is done)

    Thanks again
    Last edited by Millsie; 05-29-2011 at 03:39 PM.

  12. #12
    Registered User
    Join Date
    May 2011
    Posts
    9
    Okay, brilliant. Now its popping almost correctly now all I think it needs is a quick modification on how it makes
    the topPtr point to the second node in the stack but I don't know if its in pop() or push() where the error occurs..

    Code so far
    Code:
    char pop( StackNodePtr *topPtr ){
    //Pop a value off the stack.
        char data;
        StackNode *temp;
        temp = *topPtr;
    
        data = temp->data;
        printf(" %c \n", data);
        *topPtr = temp -> nextPtr;
        free(temp);
        return data;
    
    }
    Code:
    void push( StackNodePtr *topPtr, char value ){
    //Push a value on the stack.
    //The seperate top pointer makes this more complicated.
        StackNode *newNode;
        newNode = malloc(sizeof(StackNode));
        newNode -> data = value;
        newNode -> nextPtr = *topPtr;
        *topPtr = newNode;
    
    }

  13. #13
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > Yes, I got one warning an "assignment from incompatible pointer type".
    > How serious is this warning?
    In this case, it's only the difference between working code, and a pile of poo.
    You should regard all warnings as ERRORS (gcc users should have -Werror as an option).

    > I'm guessing that *topPtr would change what the first node is?
    Or stop guessing.
    You're trying to change the stored top pointer in the variable owned by another function.
    Code:
    void foo ( int *p ) {
      p = 123; // this is an error, or "incompatible type assignment"
      *p = 123;
    }
    int main ( ) {
      int bar = 42;
      foo( &bar );
      printf("Value=%d\n", bar );
    }
    Understand how this works first, then you'll understand why you need *topPtr in order to change your actual head pointer.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. a stack question
    By JJH35 in forum C++ Programming
    Replies: 2
    Last Post: 06-03-2007, 11:37 PM
  2. Newbie stack question
    By blackmisery in forum C++ Programming
    Replies: 11
    Last Post: 03-14-2006, 09:31 AM
  3. a question about stack
    By Micko in forum C++ Programming
    Replies: 6
    Last Post: 01-09-2004, 01:09 PM
  4. Question about stack - push - pop
    By The Wiep in forum C++ Programming
    Replies: 6
    Last Post: 12-29-2002, 12:08 PM
  5. Stack Question
    By Drew in forum A Brief History of Cprogramming.com
    Replies: 4
    Last Post: 10-18-2001, 03:01 AM