-
queue help
Hi,
I'm having problems with a queue I'm writing. I have the code below and a dummy main program that just tests the queue's functions. After taking out the while loop (in main) that removes and prints the elements inside, the prgram exits with the message that it cannot "remove from an empty queue", which obviously implies there is a problem with my QueueEnter() function (keeping it from going into the while loop to begin with). If someone could take a look at it below and see if you can find what's going wrong, I'd appreciate it.
Aside: I know that in order to be portable and multi-user friendly, your supposed to write a queue using header files, ADT/CDT, dynammic memory allocation, and all that. But, since I'm the only one using this queue, there's no need to hide it's implementation.
However, if someone has, or knows where to get a fully functional (I've found ones that don't work right) queue using ADT/CDT, dynammic memory allocation and everything else (in C), could you please pass along the file, or link to the file.
Thanks in advance. Here's my code:
#include<stdio.h>
#include<stdlib.h>
typedef int queueElementT;
typedef struct queueNodeTag {
queueElementT element;
struct queueNodeTag * nextP;
} queueNodeT;
typedef struct queueT {
queueNodeT * frontP, * rearP;
} queueT;
/*
* Function: QueueCreate()
* Usage: queueT q = QueueCreate();
* --------------------------------
* Creates and initializes a queue.
*
*/
queueT QueueCreate(void) {
queueT q;
q.frontP = NULL;
q.rearP = NULL;
return q;
}
/*
* Function: QueueEnter()
* Usage: QueueEnter(queue, element);
* ----------------------------------------------
* Inserts an element into the rear of the queue.
*
*/
void QueueEnter(queueT queue, queueElementT element) {
queueNodeT newNodeP;
newNodeP.element = element;
newNodeP.nextP = NULL;
if (queue.frontP == NULL) { /* Queue is empty */
queue.frontP = &newNodeP;
queue.rearP = &newNodeP;
}
else {
queue.rearP->nextP = &newNodeP;
queue.rearP = &newNodeP;
}
}
/*
* Function: QueueIsEmpty()
* Usage: if (QueueIsEmpty(q)) { ...
* -----------------------------------------------------
* Returns TRUE if Queue is empty, FALSE otherwise
*
*/
int QueueIsEmpty(queueT queue) {
if (queue.frontP == NULL)
return 1;
return 0;
}
/*
* Function: QueueRemove()
* Usage: queueElementT elem = QueueRemove(q)
* ----------------------------------------------------------
* Removes and returns an element from the front of the queue.
*
*/
queueElementT QueueRemove(queueT queue) {
queueElementT element;
queueNodeT * tempP;
if (QueueIsEmpty(queue)){
fprintf(stderr, "Cannot remove from an empty queue.\n");
exit(1);
}
element = queue.frontP->element;
tempP = queue.frontP;
queue.frontP = queue.frontP->nextP;
free(tempP);
return element;
}
/*
* Function: QueuePeek()
* Usage: queueElementT elem = QueuePeek(q);
* --------------------------------------------------
* Returns the value of the first element in the
* queue without removing that element.
*
*/
queueElementT QueuePeek(queueT queue) {
return queue.frontP->element;
}
/*
* Function: QueueDestroy()
* Usage: QueueDestroy(q);
* ----------------------------------------------------------
* Removes all elements from a non-empty queue and then
* deallocates memory used directly or indirectly by the queue.
*
*/
void QueueDestroy(queueT queue) {
while (!QueueIsEmpty(queue)){
QueueRemove(queue);
}
queue.frontP = NULL;
queue.rearP = NULL;
free(&queue);
}
/****************
* MAIN PROGRAM
***************/
int main() {
queueElementT x1=1, x2=2, out=0;
queueT queue;
queue = QueueCreate();
QueueEnter(queue, x1);
QueueEnter(queue, x2);
QueueEnter(queue, 123);
while (queue.frontP != NULL) {
out = QueueRemove(queue);
printf ("%d\n", (int)out);
fflush(stdout);
}
QueueDestroy(queue);
return 0;
}
-
The only problem with your code, was that your QueueEnter and QueueRemove functions operated on local copies of the queue, so that when they modified the front/rear pointers, these changes were not affecting the actual queue stored in main
By passing a pointer to the queue (for those functions which modify the queue), all seems well.
Code:
#include<stdio.h>
#include<stdlib.h>
typedef int queueElementT;
typedef struct queueNodeTag {
queueElementT element;
struct queueNodeTag * nextP;
} queueNodeT;
typedef struct queueT {
queueNodeT * frontP, * rearP;
} queueT;
/*
* Function: QueueCreate()
* Usage: queueT q = QueueCreate();
* --------------------------------
* Creates and initializes a queue.
*
*/
queueT QueueCreate(void) {
queueT q;
q.frontP = NULL;
q.rearP = NULL;
return q;
}
/*
* Function: QueueEnter()
* Usage: QueueEnter(queue, element);
* ----------------------------------------------
* Inserts an element into the rear of the queue.
*
*/
void QueueEnter(queueT *queue, queueElementT element) {
queueNodeT *newNodeP = malloc(sizeof(queueNodeT));
newNodeP->element = element;
newNodeP->nextP = NULL;
if(queue->frontP == NULL) { /* Queue is empty */
queue->frontP = newNodeP;
queue->rearP = newNodeP;
} else {
queue->rearP->nextP = newNodeP;
queue->rearP = newNodeP;
}
}
/*
* Function: QueueIsEmpty()
* Usage: if (QueueIsEmpty(q)) { ...
* -----------------------------------------------------
* Returns TRUE if Queue is empty, FALSE otherwise
*
*/
int QueueIsEmpty(queueT queue) {
if(queue.frontP == NULL)
return 1;
return 0;
}
/*
* Function: QueueRemove()
* Usage: queueElementT elem = QueueRemove(q)
* ----------------------------------------------------------
* Removes and returns an element from the front of the queue.
*
*/
queueElementT QueueRemove(queueT *queue) {
int element;
queueNodeT * tempP;
if(QueueIsEmpty ( *queue )) {
fprintf( stderr, "Cannot remove from an empty queue.\n" );
exit( 1 );
}
element = queue->frontP->element;
tempP = queue->frontP;
queue->frontP = queue->frontP->nextP;
free( tempP );
return element;
}
/*
* Function: QueuePeek()
* Usage: queueElementT elem = QueuePeek(q);
* --------------------------------------------------
* Returns the value of the first element in the
* queue without removing that element.
*
*/
int QueuePeek(queueT queue) {
return queue.frontP->element;
}
/*
* Function: QueueDestroy()
* Usage: QueueDestroy(q);
* ----------------------------------------------------------
* Removes all elements from a non-empty queue and then
* deallocates memory used directly or indirectly by the queue.
*
*/
void QueueDestroy(queueT queue) {
while(!QueueIsEmpty ( queue )) {
QueueRemove( &queue );
}
queue.frontP = NULL;
queue.rearP = NULL;
//! not malloc'ed free( &queue );
//! check the QueueCreate function
}
/****************
* MAIN PROGRAM
***************/
int main() {
queueElementT x1=1, x2=2, out=0;
queueT queue;
queue = QueueCreate( );
QueueEnter( &queue, x1 );
QueueEnter( &queue, x2 );
QueueEnter( &queue, 123 );
while(queue.frontP != NULL) {
out = QueueRemove( &queue );
printf( "%d\n", out );
fflush( stdout );
}
QueueDestroy( queue );
return 0;
}
-
That would solve the problem. Thanks. I appreciate it.