Thread: linked-list queue

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