A Linked Stack in C

This is a discussion on A Linked Stack in C within the C Programming forums, part of the General Programming Boards category; Hello. I have a question with my linked stack implementation in C. I'm pretty new to C and especially pointers. ...

  1. #1
    Registered User
    Join Date
    Nov 2009
    Posts
    20

    Question A Linked Stack in C

    Hello. I have a question with my linked stack implementation in C. I'm pretty new to C and especially pointers. Any help will be greatly appreciated.

    First of all, I tested my linked stack implementation with the following code:

    Code:
    //Just so you know
    typedef struct LinkedStack linkedstack;
    typedef struct StackNode node;
    
    struct StackNode{
    	char info;
    	struct StackNode *link;
    };
    
    struct LinkedStack{
    	struct StackNode *top;
    };
    
    main(){
    	linkedstack s;
    	char c;
    	char vowels[] = "aeiou";
    	int i = 0;
    	
    	CreateStack(&s);
    	
    	while(i < strlen(vowels)){
    		push(&s, vowels[i]);
    		i++;
    	}
    	
    	while(!isEmpty(&s)){
    		char foo = pop(&s);
    		printf("%s%s", &foo, "\n");
    	}
    	
    	char bar = pop(&s);
    }
    From the above code, I expected the following output:

    Code:
    u
    o
    i
    e
    a
    StackUnderflow occurred!
    However, the output I get looks like this: after the vowels, there will be an unwanted ascii character. When I run it from the command line, I get the clubs character. Ran from Notepad++'s NppExec plugin, I get a bar ("|").

    I figure that my mistake is in my implementation of push and pop (but I am heavily inclined to think that my push is perfect, that my pop is the defective one), as it messily deals with pointers. Here's my code:

    Code:
    void push(linkedstack *stack, char me){
    	node *NewNode;
    	NewNode = (node *) malloc(sizeof(node));
    	
    	if(NewNode == NULL){
    		StackOverflow();
    	}
    	else{
    		NewNode->info = me;
    		NewNode->link = stack->top;
    		stack->top = NewNode;
    	}
    }
    
    char pop(linkedstack *stack){
    	char temp;
    	node *node;
    	
    	if(isEmpty(stack)){
    		StackUnderflow();
    	}
    	else{
    		node = stack->top;
    		temp = (*node).info;
    		stack->top = (*node).link;
    		free(node);
    	}
    	
    	return temp;
    }
    Now, I've seen implementations of pop that takes in a stack pointer and a pointer to a "placeholder" i.e., to where the popped value will be stored. However, due to matters of style rooted in my OO (Java) training, I am trying to avoid that. The pop implemenations I've seen return void (as the popped element is stored in the passed pointer). I want to return a char, point blank.

    Is this possible in C or am I making myself suffer by thinking encumbered by OO? Any pointers (no pun intended) to the proper direction will be appreciated. Much thanks.
    Last edited by skytreader; 12-17-2009 at 07:30 PM. Reason: added my structs for StackNode and LinkedStack

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,884
    I think that the problem lies here:
    Code:
    printf("%s%s", &foo, "\n");
    it should be:
    Code:
    printf("%c\n", foo);
    since you want to print a char, not a string.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Nov 2009
    Posts
    20
    Hello laserlight. I tried what you suggested and received the following output:

    Code:
    K
    K
    K
    K
    K
    StackUnderflow occurred!
    No unwanted ascii character this time although the output is more unexpected. I tried to add a printf just before the return statement in pop. I got the following output

    Code:
    From the pop function:uK
    From the pop function:oK
    From the pop function:iK
    From the pop function:eK
    From the pop function:aK
    StackUnderflow occurred!
    Last edited by skytreader; 12-17-2009 at 06:39 PM. Reason: :o becomes a smiley

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,884
    I am afraid that although I would write the program a little differently, I do not see anything in what you have shown that would result in such an output. I suggest that you post the smallest and simplest compilable program that demonstrates the problem.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    Nov 2009
    Posts
    20

    Lightbulb

    Hello. I've found a solution to my problem. Although satisfied that my pop works, it would still be nice if someone here can explain to me the difference I found.

    My original test:

    Code:
    main(){
    	linkedstack s;
    	char c;
    	char vowels[] = "aeiou";
    	int i = 0;
    	
    	CreateStack(&s);
    	
    	while(i < strlen(vowels)){
    		push(&s, vowels[i]);
    		printf("%s%c%c", "pushed ", vowels[i], '\n');
    		printf("%s%c%c", "and peeked ", peek(&s), '\n');
    		i++;
    	}
    	
    	while(!isEmpty(&s)){
                    char foo = pop(&s)
    		printf("%s%c%c", "popped ", foo, '\n'); //I will change this line!
    	}
    	
    	char bar = pop(&s);
    }
    The test that works as expected:

    Code:
    main(){
    	linkedstack s;
    	char c;
    	char vowels[] = "aeiou";
    	int i = 0;
    	
    	CreateStack(&s);
    	
    	while(i < strlen(vowels)){
    		push(&s, vowels[i]);
    		printf("%s%c%c", "pushed ", vowels[i], '\n');
    		printf("%s%c%c", "and peeked ", peek(&s), '\n');
    		i++;
    	}
    	
    	while(!isEmpty(&s)){
    		printf("%s%c%c", "popped ", pop(&s), '\n'); //No more 'foo' variable!
    	}
    	
    	char bar = pop(&s);
    }
    Any thoughts?

  6. #6
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    I don't really like these questions about code, which don't include the whole program.

    Naturally, I can't compile yours, as is, since parts are missing.

    This is a simplified version of it, that works:
    Code:
    
    #include <stdio.h>
    
    
    //Just so you know
    typedef struct LinkedStack linkedstack;
    typedef struct StackNode node;
    
    struct StackNode{
    	char info;
    	struct StackNode *link;
    };
    
    struct LinkedStack{
    	struct StackNode *top;
    };
    void push(linkedstack *stack, char me){
    	node *NewNode;
    	NewNode = (node *) malloc(sizeof(node));
    	
    	NewNode->info = me;
    	NewNode->link = stack->top;
    	stack->top = NewNode;
    }
    
    char pop(linkedstack *stack){
    	char temp;
    	node *node;
    	
    	node = stack->top;
    	temp = (*node).info;
    	stack->top = (*node).link;
    	free(node);
    	
    	return temp;
    }
    
    int main(){
    	linkedstack s;
    	char c, ch;
    	char vowels[] = "aeiou sometimes y and w";
    	int i = 0;
    	
    	while(i < strlen(vowels)){
    		push(&s, vowels[i]);
    		i++;
    	}
    	
    	while(i--){   
    		ch = pop(&s);
    		printf("%c", ch);
    	}
    	
      printf("\n\n\t\t\t     press enter when ready");
      i = getchar();
      return 0;    
    }

  7. #7
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Why do you keep calling pop again after you know isEmpty returns empty?


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

  8. #8
    Registered User
    Join Date
    Nov 2009
    Posts
    20
    Hi quzah. I did that just to make sure that my stack doesn't return any machine-level-y error messages to the user. My StackUnderflow and StackOverflow do nothing but state the obvious (i.e. that a StackUnderflow occurred or a StackOverflow occurred respectively).

    laserlight, Adak, much as I'd like to post my code here, I really can't. This is schoolwork and one of my classmates might go googling, stumble upon here and we'd have the same code. And, lest I be accussed of fraud or anything along those lines, implementing a stack is only a trivial part of the problem. Our real task is to convert infix expressions to postfix. In fact, our reference book gives a compiling code listing for a linked stack. The book's implementation is the one which takes in a pointer to a stack and a pointer to a "placeholder" where the popped value will be stored. I am only trying to do my own implementation because I want to learn C.

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,884
    Quote Originally Posted by skytreader
    laserlight, Adak, much as I'd like to post my code here, I really can't. This is schoolwork and one of my classmates might go googling, stumble upon here and we'd have the same code. And, lest I be accussed of fraud or anything along those lines, implementing a stack is only a trivial part of the problem.
    I asked you to post the smallest and simplest compilable program that demonstrates the problem, not your current code in its entirety. It may well be the case that you will discover the root of the problem while coming up with such a program and thus be able to fix your current program on your own. Even if you don't the fact that you have posted here provides some measure of protection against accusations of plagiarism.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    So you had good working code for this stack, all along, and you're just messing around, yanking our chains.

    I'd love to tell you how damn inconsiderate you are, but I know I couldn't really communicate that to someone as self-centered as yourself, in a public forum.
    Last edited by Adak; 12-20-2009 at 06:49 AM.

  11. #11
    Registered User
    Join Date
    Nov 2009
    Posts
    20
    Quote Originally Posted by laserlight View Post
    Even if you don't the fact that you have posted here provides some measure of protection against accusations of plagiarism.
    In a moment's thought, I didn't realize that.

    My apologies if my being stubborn caused inconveniences. Again, I did not use the working code given in our reference book because I wanted my own shot at going at C. My approach and the book's approach are different (especially in terms of pop).

    I was about to post my problematic code now when I realized what made my approach wrong.

    From my first post:

    Code:
    main(){
    	linkedstack s;
    	char c;
    	char vowels[] = "aeiou";
    	int i = 0;
    	
    	CreateStack(&s);
    	
    	while(i < strlen(vowels)){
    		push(&s, vowels[i]);
    		i++;
    	}
    	
    	while(!isEmpty(&s)){
    		char foo = pop(&s);
    		printf("%s%s", &foo, "\n"); //<--This made it wrong!
    	}
    	
    	char bar = pop(&s);
    }
    I passed the address of foo to printf, hence the messy output. On my third post, it seems that I have already fixed the problem (see the same line) without having to remove 'foo' only I didn't realize it. So I removed foo and directly passed pop(&s) and thought that to be the solution.

    Code:
    //In the first code listing of my third post, I am no longer passing the address of foo.
    printf("%s%c%c", "popped ", foo, '\n');
    Well...that's pretty much it. Thanks to everyone who lent me hand. It was never my intention to waste your time with the trivial part of my problem. I am sorry if I made you feel like that.

    EDIT: laserlight, I'm sorry. You pointed that out to me in your first reply. I didn't see that 'foo' part. What took my attention is the "%c\n" argument and that's the only thing I changed. My apologies.
    Last edited by skytreader; 12-20-2009 at 09:38 AM. Reason: in retrospect of laserlight's first reply

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. stack and pointer problem
    By ramaadhitia in forum C Programming
    Replies: 2
    Last Post: 09-11-2006, 11:41 PM
  2. infix evaluation using stack
    By lewissi in forum C++ Programming
    Replies: 0
    Last Post: 11-03-2005, 01:56 AM
  3. Question about a stack using array of pointers
    By Ricochet in forum C++ Programming
    Replies: 6
    Last Post: 11-17-2003, 09:12 PM
  4. error trying to compile stack program
    By KristTlove in forum C++ Programming
    Replies: 2
    Last Post: 11-03-2003, 05:27 PM
  5. Stack Program Here
    By Troll_King in forum C Programming
    Replies: 7
    Last Post: 10-15-2001, 05:36 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21