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
		}
	}

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.

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?

Originally Posted by popapez

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.

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.

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;                       ***

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.

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....

So why not do it the way 325,896,400 people have done it before you: return the pointer from your tokenize function.

i do return the pointer from my tokenize function...

No you don't. You return a non-pointer value.

Quzah.

so this is the pointer?

Code:

struct node* tokenize(char line[])
	{		
        .....
	return new;

	}

That is how you return a pointer, yes.

nothing has changed, same errors.

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.