Thread: queue help

  1. #1
    Unregistered
    Guest

    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;

    }

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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;
    }
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Unregistered
    Guest
    That would solve the problem. Thanks. I appreciate it.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with FIFO QUEUE
    By jackfraust in forum C++ Programming
    Replies: 23
    Last Post: 04-03-2009, 08:17 AM
  2. Fixing my program
    By Mcwaffle in forum C Programming
    Replies: 5
    Last Post: 11-05-2008, 03:55 AM
  3. linked-list queue
    By the_winky_files in forum C Programming
    Replies: 17
    Last Post: 11-21-2005, 03:57 PM
  4. help with queues
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 05-21-2002, 09:09 PM
  5. help with queues
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 05-21-2002, 11:39 AM