queue and stack implemented with linked list

This is a discussion on queue and stack implemented with linked list within the C Programming forums, part of the General Programming Boards category; Hi, I am taking a beginner's C programming course, although I am very fluent in java so I understand the ...

  1. #1
    Registered User
    Join Date
    Sep 2009
    Posts
    11

    queue and stack implemented with linked list

    Hi, I am taking a beginner's C programming course, although I am very fluent in java so I understand the concepts, etc.

    I am implementing a stack and a queue with nodes of structs using linked lists. Every method that is unrelated to stacks and queues work fine (eg. tokenize, etc). I am having some issues though:
    - stack:
    + it seems to be pushing correctly, but right now trying to pop puts us in an infinite loop. I have looked over and over this code and I don't think it should be doing this....

    - queue:
    + enqueueing the first node works, but the second attempt creates a bus error. I have changed this code many times, and previously it was always enqueueing the last line of my file, instead of going line by line. I am sure it is just one stupid pointer issue or something that is messing it all up, but I'm pulling my hair out trying to find it!!


    Sorry for the long post! Thanks so much!!! Here is my code:



    * NOTE- I only print the f1 field out as a test to see if I have the correct node. The other fields of the struct should work as well.

    Also, I made a lot of variables global for ease of testing, which is obviously not ideal but it's how my code is set up currently.


    EDIT: if someone wants the entire code, with the other subroutines, to test on their own machine, I can easily provide that
    Code:
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <ctype.h>
    #include <time.h>		// for random numbers
    
    struct node				// node for linked list
    	{
    	int f1;
    	float f2;
    	char f3;		
    	struct node *next;		// PTR to next node
    	};
    	
    struct node *start, *end;		// first and last nodes in linked list
    struct node *new, *TEMP, *p;									
    char RandomName(char randomNAME);
    struct node tokenize(char line[]);
    int runs = 1;				// tracks runs, 1st run							
    
    // for stack:
    void push(void), pop(void);
    
    // for queue:
    void dequeue(void), add(void), enqueue();
    
    
    int main(int argc, char*argv[])
    	{	
    	char runagain = 'Y';
    	while (runagain == 'Y')	// entire program in loop
    		{
    	 	new = (struct node*)malloc(sizeof(struct node)); 
    		start = NULL;
    		end = NULL;
    		int whileloop = 1;
    		srand((unsigned)(time(NULL)));					
    		int j = 0;
    		int random = 0;			// random number
    		char *file = argv[1];		// file name is entered from command line
    		FILE *data;										
    		char decision[10];			// will be either stack(S) or queue(Q)
    		char line[100];			// hold the line
    		int lcount = 0;		// initialize line count
    		int i = 1;
    		char input[10];		// holds the action for the queue/stack
    		register int t;									
    
    // make a file
    		data = fopen(file, "w");	// open for writing
    		if (data == NULL)
    			{
    			printf("Cannot open %s\n", data);
    			exit(0);
    			}
    
    		for (j=0; j<10; j++)		// write 10 random structs to file
    			{
    			new->next = NULL;		
    
    			new->f1 = rand()%90+10;					// random integer
    			new->f2 = (rand()%100)/9.9;					// random float
    			new->f3 = RandomName(new->f3);			// random name
    			fprintf(data, "%d %g %c\n", new->f1, new->f2, new->f3);
    			}			// print each data field of new to file
    
    		fclose(data);		// close file
    
    		printf("Create a stack(S) or a queue(Q):  ");	// get decision
    		scanf("%c", decision);
    		if (runs > 1)
    			scanf("%c", decision);						
    
    		*decision = toupper(*decision);					// converts to uppercase always
    		data = fopen(file, "r");						// open file for reading
    
    // queue:
    		if (*decision == 'Q')
    			{
    			while(whileloop == 1) 						// will execute until quit
    				{
    				printf("Choose an action- Enqueue(E), Print(P), Dequeue(D), Quit(Q):  ");
    				if (i==1)
    					gets(input);						// have to gets() twice the first run, 
    				gets(input);							// or will print above line twice.
    				*input = toupper(*input);				// converts to an uppercase char
    
    				switch(*input) 							// will go to one of 3 methods, or exit
    					{
    					case 'E':
    						if (fgets(line, sizeof(line), data) != NULL) 
    							{
    							lcount++;
    							printf("%d. %s", lcount, line);  	// print line # and data
    							}
    						*new = tokenize(line);
    						enqueue();
    						break;
    					case 'P':
    //						print(idkyet, idk);
    						break;
    					case 'D':
    						dequeue();
    						printf("Struct dequeued was %d  \n", start->f1);
    						break;
    					case 'Q':
    						whileloop = 0;
    						break;
    					default:
    						printf("Please enter an A, P, D or Q.\n");	// if none are entered				
    					}
    				i++;									// now only one gets()	
    				}
    			}
    		
    // stack:		
    		else if (*decision == 'S')
    			{
    			int i = 1;
    			while(whileloop == 1) 
    				{
    				printf("Choose an action- PUSH(U), POP(O), Quit(Q):  ");
    				if (i==1)
    					gets(input);			// have to gets() twice the first run, 
    				gets(input);							
    				*input = toupper(*input);				// converts to an uppercase char
    	
    				switch(*input) 				// will go to one of 3 methods, or exit
    					{
    					case 'U':
    						if (fgets(line, sizeof(line), data) != NULL) 
    							{
    							lcount++;
    							printf("%d. %s", lcount, line);  	// print line # and data
    							}
    						*new = tokenize(line);	
    		 				push();
    						break;
    					case 'O':
    						pop();
    						break;
    					case 'Q':
    						whileloop = 0;
    						break;
    					default:
    						printf("Please enter a U, O or Q.\n");	// if none are entered
    					}
    				i++;									// now only one gets()	
    				}
    			}
    		else
    			printf("Error: please enter 'Q' or 'S' only! \n");
    		
    		fclose(data);									// close file
    
    		printf("Would you like to create another data structure: Y or N?  ");
    		scanf("%s", &runagain);							// will run again if 'y'
    			
    		runagain = toupper(runagain);					// always convert to uppercase
    		runs++;							// increase # of runs
    		}
    	printf("BYE!!\n\n");	
    	return 0;
    	}
    
    
    
    char RandomName(char randomNAME)
    	{
    	...
    	return randomNAME;	
    	}
    
    struct node tokenize(char line[])
    {
    struct node *new;
    new = (struct node*)malloc(sizeof(struct node));
    
    .....................
    
    new->f1 = (tempINT[0]*10 + tempINT[1]);
    new->f2 = (tempFLOAT[0] + tempFLOAT[1]/10.0);
    new->f3 = tempSTRING;
    
    return *new;
    }					// new is now updated with values in the line of the file
    
    
    // ********** STACK METHODS: ***********
    
    void push(void)							// pushes number onto stack
    	{
    	new->next = NULL;
    	if (start == NULL)
    		start = new;
    	else
    		{
    		p = start; 
    		while (p->next != NULL)			// traverses to last node
    			p = p->next;
    		p->next = new;					// assigns last node's pointer to new node
    		}	
    	}
    
    void pop(void)								// pops node from stack
    	{
    	if (start == NULL)						// no nodes in list
    		printf("Stack is empty!\n");
    	else if (start->next == NULL)			// only one node in list
    		{
    		printf("Deleted node was start node %d\n", start->f1);
    		free(start);
    		start = NULL;
    		}
    	else
    		{
    		p = start;
    		while (p->next != NULL)
    			{
    			TEMP = p;
    			p = p->next;					// traverse to last node
    			}
    		printf("Deleted node was %d\n", p->f1);
    		TEMP->next = NULL;					// new last node points to NULL
    		free(p);							// free deleted node's memory space
    		}
    	}
    	
    // ********** QUEUE METHODS: ***********
    
    void enqueue(void)						// add number to queue
    	{
    	new->next = NULL;
    	if (start == NULL)
    		start = new;
    	else	
    		{
    		end->next = new;
    		end = new;
    		printf("end is %d\n", end->f1);        
    		}
    	}
    
    void dequeue(void)							// delete number from queue
    	{	
    	struct node *temp1, *temp2;
    	if (start == NULL)
    		{
    		printf("Empty: cannot delete!.\n");
    		exit(1);
    		}
    	else
    		{
    		p = start;
    		printf("Deleted int is %d \n", p->f1);
    		start = start->next;
    		free(p);			// free the memory allocated to del
    		}
    	}
    Last edited by popapez; 09-22-2009 at 10:42 PM.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    So ... where do you create any nodes? Currently you have one node and some pointers to it. You can't make much of a stack, or a queue, from one whole entire node. Every time you want to put a node on the stack you have to actually create a node in order to have a node to put on the stack.

  3. #3
    Registered User
    Join Date
    Sep 2009
    Posts
    11
    well, *new = tokenize(line); will fill a node with the line from the file. Then when pushed or enqueued, it is manipulated to point to a new node, right?

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by popapez View Post
    well, *new = tokenize(line); will fill a node with the line from the file. Then when pushed or enqueued, it is manipulated to point to a new node, right?
    Neither push nor enqueue, at least as you have them written, do anything of the sort. (Hint: the only way to get a new node is to use the word malloc.) Continually using a node that has the name new, while amusing, does not actually give you a new node every time.

  5. #5
    Registered User
    Join Date
    Sep 2009
    Posts
    11
    Either I should not have left out this subroutine or it's just in the wrong place, but here are the important lines of tokenize:

    struct node tokenize(char line[])
    {
    struct node *new;
    new = (struct node*)malloc(sizeof(struct node));

    .....................

    new->f1 = (tempINT[0]*10 + tempINT[1]);
    new->f2 = (tempFLOAT[0] + tempFLOAT[1]/10.0);
    new->f3 = tempSTRING;

    return *new;
    }



    So this is creating a new node every time, right?


    Really appreciate your help- still trying to get used to the whole pointer thing and all.

  6. #6
    Registered User
    Join Date
    Sep 2009
    Posts
    11
    enqueue gets a bus error after this point, and I have no idea why.... end.next should be able to point to "new" and add new nodes this way...

    Code:
    void enqueue(void)						// add number to queue
    	{
    	new->next = NULL;
    	if (start == NULL)
    		start = new;
    	else	
    		{
    		end->next = new;                       ***

  7. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Looking at when things are called: if fgets is NULL, you enqueue anyway despite the lack of data.

    The memory you allocate goes away at the end of the function; or more precisely any way you have of getting to that data goes away at the end of the function. You are returning a struct by value, meaning you are copying the values you read in into your One Remaining Struct that is called new every time, and those malloc'ed structs are left to die a lonely death in the closet of neglect.

    This explains both your issues: since all the pointers are the same, your queue just circles mindlessly trying to find the end, while once you free the new you then have No Remaining Structs, and attempts to deal with such are quite rightly met with a bus error.

  8. #8
    Registered User
    Join Date
    Sep 2009
    Posts
    11
    so, if we do these

    struct node *new;
    new = (struct node*)malloc(sizeof(struct node));


    in main, just before pushing or enqueueing, will the memory stay allocated until the end of main?

    I just tried that and it doesn't work either, but that doesn't mean that it shouldn't work in theory lol...


    I don't know how else to create a linked list then, I guess. It entered my thoughts that maybe I needed an array of all these nodes in order to keep the memory allocated to them all, but that kind of defeats the purpose of a linked list... again, I'm not very familiar with C yet, but it seems intuitive to me that once I set a node's pointer to another node, it shouldn't just disappear. sigh, I'm confused


    Thanks again for your help....

  9. #9
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    So why not do it the way 325,896,400 people have done it before you: return the pointer from your tokenize function.

  10. #10
    Registered User
    Join Date
    Sep 2009
    Posts
    11
    i do return the pointer from my tokenize function...

  11. #11
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    No you don't. You return a non-pointer value.

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

  12. #12
    Registered User
    Join Date
    Sep 2009
    Posts
    11
    so this is the pointer?
    Code:
    struct node* tokenize(char line[])
    	{		
            .....
    	return new;
    
    	}

  13. #13
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    That is how you return a pointer, yes.

  14. #14
    Registered User
    Join Date
    Sep 2009
    Posts
    11
    nothing has changed, same errors.

  15. #15
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Delete the old executable.
    Compile with warnings.
    Post them and your error.
    Better yet, start testing your functions one at a time in a smaller program.


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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Storing strings in a linked list
    By dws90 in forum C Programming
    Replies: 1
    Last Post: 02-21-2009, 07:06 PM
  2. Fixing my program
    By Mcwaffle in forum C Programming
    Replies: 5
    Last Post: 11-05-2008, 03:55 AM
  3. Pushing a Queue onto a Stack?
    By MiroMage in forum C Programming
    Replies: 5
    Last Post: 10-14-2008, 10:23 PM
  4. LIFO with linked list question
    By micpi in forum C Programming
    Replies: 3
    Last Post: 09-15-2005, 01:42 PM
  5. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM

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