Thread: Stack problem - I've hit a wall!

  1. #1
    Registered User
    Join Date
    Sep 2007
    Posts
    10

    Question Stack problem - I've hit a wall!

    I've been working on a stack program for class for the past week or so, and i've completely hit a wall here. I'll post what I have so far. The problem I'm having is the last two functions, the isempty() and the ptintStack() functions.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    /* self-referential structure */
    struct stackNode
     {
      int data; /* define data as an int */
      struct stackNode *nextPtr; /* stackNode pointer */
     }; /* end structure stackNode */
    
    typedef struct stackNode StackNode; /* synonym for struct stackNode */
    typedef StackNode *StackNodePtr; /* synonym for StackNode* */
    
    /* prototypes */
    void push( StackNodePtr *topPtr, int info );
    int pop( StackNodePtr *topPtr );
    void instructions( void );
    void printStack( StackNodePtr currentPtr );
    int isEmpty( StackNodePtr topPtr );
    
    /* function main begins program execution */
    int main()
    {
      StackNodePtr stackPtr = NULL; /* points to stack top */
      int choice; /* user's menu choice */
      int value; /* int input by user */
    
      instructions(); /* display the menu */
      printf( "? " );
      scanf( "%d", &choice );
    
      /* while user does not enter 3 */
      while ( choice != 3 ) {
    
        switch ( choice ) {
    
          /* push value onto stack */
        case 1:
          printf( "Enter an integer: " );
          scanf( "%d", &value );
          push( &stackPtr, value );
     printStack( stackPtr );
          break;
    
          /* pop value off stack */
        case 2:
    
          /* if stack is not empty */
          if ( !isEmpty( stackPtr ) ) {
            printf( "The popped value is %d.\n", pop( &stackPtr ) );
          } /* end if */
    
          printStack( stackPtr );
          break;
    
        default:
          printf( "Invalid choice.\n\n" );
          instructions();
          break;
    
        } /* end switch */
      printf( "? " );
        scanf( "%d", &choice );
      } /* end while */
    
      printf( "End of run.\n" );
    
      return 0; /* indicates successful termination */
    
    } /* end main */
    
    /* display program instructions to user */
    void instructions( void )
    {
      printf( "Enter choice:\n"
    "1 to push a value on the stack\n"
    "2 to pop a value off the stack\n"
              "3 to end program\n" );
    } /* end function instructions */
    
    /* Insert a node at the stack top */
    void push( StackNodePtr *topPtr, int info )
    {
      StackNodePtr newPtr; /* pointer to new node */
    
      newPtr = malloc( sizeof( StackNode ) );
    
      /* insert the node at stack top */
      if ( newPtr != NULL ) {
        newPtr->data = info;
        newPtr->nextPtr = *topPtr;
        *topPtr = newPtr;
      } /* end if */
      else { /* no space available */
        printf( "%d not inserted. No memory available.\n", info );
      } /* end else */
    
    } /* end function push */
    
    /* Remove a node from the stack top */
    int pop( StackNodePtr *topPtr )
    {
      StackNodePtr tempPtr; /* temporary node pointer */
     int popValue; /* node value */
    
      tempPtr = *topPtr;
      popValue = ( *topPtr )->data;
      *topPtr = ( *topPtr )->nextPtr;
      free( tempPtr );
    
      return popValue;
    
    } /* end function pop */
    
    /* Print the stack */
    void printStack( StackNodePtr currentPtr )
    {
      
    I'm stuck here!
     } /* end function printList */
    
    /* Return 1 if the stack is empty, 0 otherwise */
    int isEmpty( StackNodePtr topPtr )
    {
    
    And here.
    
    } /* end function isEmpty */

    Can someone point me to a good tutorial on Stacks, i can't seem to google anything that simplifies it for me. And any help you all could give me would be much appreciated. This is the hardest time I've had so far with programming

  2. #2
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    > Can someone point me to a good tutorial on Stacks, i can't seem to google anything that simplifies it for me.

    Eh, they're sort of a trivial data structure to implement correctly (if "correctly" is different from "well" I guess). The best way to visualize what a stack is, is probably to imagine a stack of objects in real life. If you've ever stacked coins or dishes it should be easy. Stacks are a special list of items that are built up one at a time, and destroyed one at a time, just like a real stack. And just like a real stack, items are usually processed in last in first out order: the top coin comes off the stack before the rest.

    Another type of stack is the queue, where you can imagine maybe a line in a grocery store or something. The chief difference is that items are processed in first in first out order: the first person in line gets a ticket before the rest.

    As long as you meet those requrements, you would implement a stack in my opinion.


    Now as for your two troublesome functions:
    In order to write the isEmpty function you need to understand how to detect an empty stack in your implementation (it looks like if the stack is empty then topPointer is NULL). Once you figure out how to test for an empty stack then just return the result of that test.

    In order to implement printStack, just loop over the stack with a disposable pointer and print each node in the stack as you go along.

  3. #3
    Registered User
    Join Date
    Sep 2007
    Posts
    10
    Your description helps a little to make sense of it all. I'm still lost though :-( Can someone show me how to start the print function? I know how to traverse an array with no problem, but how do you traverse a stack, without affecting the data? I can't even figure out what pointer points to what.

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    What do you find difficult? You just need to walk the list of entries from the top down without changing any of it. As long as the "PrintStack" is a function that is allowed to see inside the stack [that is, it's allowed to use the nextPtr and data to access the stuff stored in the stack].

    If you aren't allowed to do that, then you have to do tricky stuff.
    Do NOT use this method unless the rules say you can't access the internals of the stack when printing it:
    Code:
    void printStack(StackNodePtr cur)
    {
         int x;
         if (cur) {
             x = pop(&cur);   // Pop it off the stack. 
             printf("%d\n", x);  // Print it. 
             printStack(cur);  // Now print the REST of teh stack. 
             push(x);           // Stick it back on again. 
         }
    }
    Since this function is recursive, it is unsuitable for use in embedded systems where the stack is small. It should be fine on a Windows or Linux system.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    Registered User
    Join Date
    Sep 2007
    Posts
    10
    I still don't understand this. Man i'm getting frustrated. Noone has a good link on here for a stack tutorial?

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by matsp View Post
    Code:
    void printStack(StackNodePtr cur)
    {
         int x;
         if (cur) {
             x = pop(&cur);   // Pop it off the stack. 
             printf("%d\n", x);  // Print it. 
             printStack(cur);  // Now print the REST of teh stack. 
             push(x);           // Stick it back on again. 
         }
    }
    How fitting, you take each item off one stack and put it onto another stack, printing it out in the process. Of course the second stack could instead simply be another instance of the same type as the first stack.

    This techinque would break const-ness of the stack course. (printing should be a const operation)
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    http://www.cprogramming.com/tutorial...ory/stack.html
    Have you come up with anything yourself? Cause it's becoming ridiculous. Perhaps made another attempt to print a stack?
    Maybe get a copy of the stack and then:

    void print_stack( stack st )
    while !isempty():
    print top node
    pop top node

    Of course now your problem is implementing isEmpty still.
    Last edited by whiteflags; 11-14-2007 at 12:06 AM.

  8. #8
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by iMalc View Post
    How fitting, you take each item off one stack and put it onto another stack, printing it out in the process. Of course the second stack could instead simply be another instance of the same type as the first stack.

    This techinque would break const-ness of the stack course. (printing should be a const operation)
    I did not intend that as a SERIOUS answer - more as a "curiosity(sp?)".

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Weird stack problem...
    By BC2210 in forum C Programming
    Replies: 2
    Last Post: 11-16-2008, 05:22 PM
  2. Fixing my program
    By Mcwaffle in forum C Programming
    Replies: 5
    Last Post: 11-05-2008, 03:55 AM
  3. Question about a stack using array of pointers
    By Ricochet in forum C++ Programming
    Replies: 6
    Last Post: 11-17-2003, 10:12 PM
  4. Stack problem
    By silicon in forum C++ Programming
    Replies: 3
    Last Post: 11-11-2003, 04:30 PM
  5. Array Stack Problem
    By Drew in forum C++ Programming
    Replies: 3
    Last Post: 09-04-2001, 06:58 PM