linked-list queue

This is a discussion on linked-list queue within the C Programming forums, part of the General Programming Boards category; Well, what I was looking for was a description of the logic. But if you can explain the purpose and ...

  1. #16
    Registered User
    Join Date
    Mar 2005
    Location
    Mountaintop, Pa
    Posts
    1,059
    Well, what I was looking for was a description of the logic. But if you can explain the purpose and use of the iPriority variable in the structure *AND* make a serious attempt at writing the other DeleteFromQueue function, I will post the code. The DeleteFromQueue function should not be any more than 20 code statements. If you've got more than 20 statements, you're off on a tangent again.

  2. #17
    Registered User
    Join Date
    Mar 2005
    Location
    Mountaintop, Pa
    Posts
    1,059
    The main concern which I have with this program is the priority. What is exactly is this for?
    Priority is used for the queue part of the linked list. A queue is simply a linear list of info that is accessed in a first in first out (FIFO) order. I use iPriority to accomplish this queuing. The first record added will have the highest priority, the next record added will have the next highest priority etc..

    Example
    record 1 iData = 10, iPriority = 9
    record 2 iData = 17, iPriority = 8
    record 3 iData =5, iPriority = 7
    record 4 iDat=24, priority = 6

    Thus, the records will come off the queue in highest priority to lowest priority order.

    Now there can be exceptions to the FIFO queueing. For example, a queue is forming in front of a fancy new restaurant which will open in a hour. Along comes a VIP who would not go to the end of the queue but rather to the front of the queue. We illustrate this with adding record #5 where iData = 0 but iPriority = 10. So that record is now placed at the front of th queue because of its high priority. Normally, you would not have this type of exception in a queue but I just added this flexibility for good measure.

    I haven't thoroughly tested this code. So, testing is your responsibility.

    Good luck
    Bob

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    #define QUEUE_EMPTY                -1
    #define MEMORY_ALLOCATION_FAILED    1
    #define QUEUE_LIMIT_REACHED         2
    #define QUEUE_LIMIT                 6
    struct QueueNode
    {
        int iData;
        int iPriority;
        struct QueueNode *next;
    };
    
    int DeleteFromQueue(struct QueueNode **QueueNodeFirst, struct QueueNode
    **QueueNodeLast,int *iPriority, int *iInput)
    {
        struct QueueNode *QueueNodeTemp1 = NULL;
    
        if((NULL == *QueueNodeLast) && (*QueueNodeLast == *QueueNodeFirst))
            return QUEUE_EMPTY;  
        *iInput = (*QueueNodeFirst)->iData;
        *iPriority = (*QueueNodeFirst)->iPriority;
        QueueNodeTemp1 = *QueueNodeFirst;
        *QueueNodeFirst = (*QueueNodeFirst)->next;
        if(*QueueNodeLast == QueueNodeTemp1)
            *QueueNodeLast = (*QueueNodeLast)->next;
        if(QueueNodeTemp1)
            free(QueueNodeTemp1);
        return 0;
    }
    
    int Add2Queue(struct QueueNode **QueueNodeFirst, struct QueueNode
    **QueueNodeLast, int iPriority, int iInput)
    {
        int iQueueCount = 0;
        struct QueueNode *QueueNodeTemp1  = *QueueNodeFirst; 
        struct QueueNode *QueueNodeTemp2 = NULL;
    
        while(QueueNodeTemp1)
        {
            ++iQueueCount;
            QueueNodeTemp1 = QueueNodeTemp1->next;
        }
        if(iQueueCount >= QUEUE_LIMIT)
            return QUEUE_LIMIT_REACHED;
        QueueNodeTemp1 = NULL; 
        if((QueueNodeTemp1 = ( struct QueueNode *)
            malloc(sizeof(struct QueueNode)))  == NULL)
            return MEMORY_ALLOCATION_FAILED;
        QueueNodeTemp1->iData = iInput;
        QueueNodeTemp1->iPriority = iPriority;
        QueueNodeTemp1->next = NULL;
        if(*QueueNodeLast == NULL)
        {
            *QueueNodeLast = QueueNodeTemp1;
            *QueueNodeFirst = *QueueNodeLast;
        } 
        else
        {
            if((*QueueNodeFirst)->iPriority < iPriority)
            {
                QueueNodeTemp1->next = *QueueNodeFirst;
                *QueueNodeFirst = QueueNodeTemp1;
            } 
            else {
                if((*QueueNodeLast)->iPriority > iPriority)
                {
                    (*QueueNodeLast)->next = QueueNodeTemp1;
                    *QueueNodeLast = QueueNodeTemp1;
                } 
                else {
                    QueueNodeTemp2 = *QueueNodeFirst;
                    while((QueueNodeTemp2->next)->iPriority >= iPriority)
                    {
                        QueueNodeTemp2 = QueueNodeTemp2->next;
                    }
                    QueueNodeTemp1->next = QueueNodeTemp2->next;
                    QueueNodeTemp2->next = QueueNodeTemp1;
                }
            }
        }
        return 0;
    }
    
    void DisplayAllData(struct QueueNode **QueueNodeFirst)
    {
        struct QueueNode *QueueNodeDisplayData = NULL;
        QueueNodeDisplayData = *QueueNodeFirst;
        if(QueueNodeDisplayData == NULL)
            printf("Nothing to print, the queue is empty!!!\n");
        else
            while(QueueNodeDisplayData)
            {
                printf("Data = %d Priority = %d\n",QueueNodeDisplayData->iData,
                    QueueNodeDisplayData->iPriority);
                QueueNodeDisplayData = QueueNodeDisplayData->next;
            }
    }
    
    int main(void)
    {
        int cIntArray[7] = {2, 7, 4, 5, 3, 9, 14};
        int iInput, iPriority, iIndex, iReturn;
        struct QueueNode *QueueNodeFirst = NULL;
        struct QueueNode *QueueNodeLast = NULL;
        // Add six items to queue
        for(iIndex = 0; iIndex < 6; iIndex++)
        {
            iInput = cIntArray[iIndex], iPriority = iIndex;
            printf("Inserting: data: %d with priority: %d\n", iPriority, iInput);
            iReturn = Add2Queue(&QueueNodeFirst, &QueueNodeLast, iInput, iPriority);
            if(iReturn == MEMORY_ALLOCATION_FAILED)
                return MEMORY_ALLOCATION_FAILED;
            else
                if (iReturn == QUEUE_LIMIT_REACHED)
                {
                    printf("Queue has maxed out\n");
                    break;
                }
        }
        DisplayAllData(&QueueNodeFirst);
        //Delete three items
        for(iIndex = 0; iIndex < 3; iIndex++)
        {
            iInput = cIntArray[iIndex], iPriority = iIndex;
            if(DeleteFromQueue(&QueueNodeFirst, &QueueNodeLast, &iInput, &iPriority)
                != QUEUE_EMPTY)
                printf("Deleting: data: %d with priority: %d\n", iPriority, iInput);
            else
                printf("The Queue is empty!!!!!\n");
        }
        DisplayAllData(&QueueNodeFirst);
        // Add one more to queue
        iInput =13;
        iPriority = 7;
        iReturn = Add2Queue(&QueueNodeFirst, &QueueNodeLast, iInput, iPriority);
        if(iReturn == MEMORY_ALLOCATION_FAILED)
            // malloc failed
            return MEMORY_ALLOCATION_FAILED;
        else if (iReturn == QUEUE_LIMIT_REACHED)
            printf("Queue has maxed out\n");
        DisplayAllData(&QueueNodeFirst);
        // We're purposely going to 7 to verify that the queue is empty
        // Note that we originally  added 6 items to the queue, then deleted three
        // and finally added one to the queue for a total of four items
        for(iIndex = 0; iIndex < 7; iIndex++)
        {
            iInput = cIntArray[iIndex], iPriority = iIndex;
            if(DeleteFromQueue(&QueueNodeFirst, &QueueNodeLast, &iInput, &iPriority)
                != QUEUE_EMPTY)
                printf("Deleting: data: %d with priority: %d\n", iPriority, iInput);
            else
                printf("The Queue is empty!!!!!\n");
        }
         DisplayAllData(&QueueNodeFirst);
        return 0;
    }
    Last edited by BobS0327; 11-16-2005 at 08:52 PM.

  3. #18
    Registered User
    Join Date
    Nov 2005
    Posts
    1
    you must be going to UMSL.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 04:09 AM
  2. linked list question
    By mikeman in forum C Programming
    Replies: 1
    Last Post: 11-30-2008, 01:56 PM
  3. Anyone good with linked list.....I am not....
    By chadsxe in forum C++ Programming
    Replies: 11
    Last Post: 11-10-2005, 02:48 PM
  4. Linked List
    By jpipitone in forum C Programming
    Replies: 4
    Last Post: 03-30-2003, 09:27 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 11:21 PM

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