Question

IN C ONLY (follow instruction please)

Implement the following functions:

Queue * initQueue( ) // Return empty queue

// enqueue and dequeue each return an int error code

int enqueue(int, Queue *)

int dequeue(Queue *, int *)

int getQsize(Queue *) // returns # of items in queue

void freeQueue(Queue *) // Free *all* space

Implement the above using a circular-linked list. Again, all operations except freeQueue should take O(1) time.

You will need to document each of your functions to inform the user how to use it and how to interpret its return value. Note that dequeue places the integer removed from the front of the queue into the location specified by the reference provided by the user (the second parameter). Note also that error conditions can arise for both enqueue and dequeue.

Also, try implementing the above with a doubly-circular-linked list. Does it make things easier or harder?

Answer 1

Tried my best to implement the code as per your requirements. Implementing using a Doubly Circular Linked list doesn't make it any easier nor harder. In this case no need to to maintain Tail (Rear) Node in the Queue Struct as Tail Node can be obtained from the previous pointer of the Head Node. I implemented the PrintQ method which is a helper function. Remove it from the code if you wish. I tried my best as far as the Error checking is concerned. Please check it and add any error checking code if necessary. Thanks

#include <stdio.h>
#include <stdlib.h>

typedef struct CLLNode
{
    int data;
    struct CLLNode *next;
} CLLNode;

typedef struct Queue
{
    CLLNode* head; // front
    CLLNode* tail; // rear
    int capacity;
} Queue;

Queue* initQueue()
{
    // initializes the Empty Queue
    Queue* newQueue = (Queue *) malloc(1 * sizeof(Queue));
    newQueue->head = NULL;
    newQueue->tail = NULL;
    newQueue->capacity = 0;

    return newQueue;
}

int enqueue(int value, Queue* queue)
{
    // Add the new integer to the end of the Queue
    // Returns the value appended to the Queue on sucess
    CLLNode* newNode = (CLLNode *) malloc(1 * sizeof(CLLNode));
    newNode->data = value;
    if (queue->capacity)
    {
        newNode->next = queue->head;
        queue->tail->next = newNode;
        queue->tail = newNode;
        queue->capacity += 1;
        return value;
    }
    newNode->next = newNode;
    queue->head = newNode;
    queue->tail = newNode;
    queue->capacity += 1;

    return value;
}

int dequeue(Queue *queue, int* intptr)
{
    // Returns 0 on successfull removing an element from the head (front)
    // returns -1 on removing from an empty queue
    // Use this to check for successfull Enqueue Operation
    if (!queue->capacity)
    {
        printf("Removing an element from an empty queue forbidden\n");
        return -1;
    }

    CLLNode* node = queue->head;
    *intptr = node->data;

    if (queue->capacity == 1)
    {
        queue->head = NULL;
        queue->tail = NULL;
        queue->capacity -= 1;
        free(node);

        return 0;
    }

    // When the size (capacity) of the queue is more than 1
    queue->head = node->next;
    queue->tail->next = node->next;
    free(node);
    queue->capacity -= 1;

    return 0;
}

int getQSize(Queue *queue)
{
    // Return the size or number of elements in the Queue
    return queue->capacity;
}

void freeQueue(Queue *queue)
{
    // Free up the entire Queue by dequeing
    int* temp = (int *) calloc(1, sizeof(int));
    while(queue->capacity)
    {
        dequeue(queue, temp);
    }
    free(queue);
}

void printQ(Queue *queue)
{
    // Helper function just to print the Current Staus of the Queue
    int qIndex = 0;
    CLLNode* current = queue->head;
    while (qIndex < queue->capacity)
    {
        printf("%d ", current->data);
        current = current->next;
        qIndex++;
    }

    printf("\n");
}

int main()
{
    Queue *newQueue = initQueue();

    int* dequedElement = (int *) malloc(sizeof(int));

    int opStatus;
    int index = 0;
    int items[] = {5, 6, 10, 1, -1, 0 , 100, 54};

    for(index = 0; index < sizeof(items) / sizeof(items[0]); index++)
    {
        enqueue(items[index], newQueue);
    }
    printQ(newQueue);

    for (index = 0; index < 3; index++)
    {
        dequeue(newQueue, dequedElement);
        printf("Removing %d\n", *dequedElement);
        enqueue(10 * index, newQueue);
    }

    dequeue(newQueue, dequedElement);
    printQ(newQueue);

    printf("Element removed is %d\n", *dequedElement);
    printf("Size of the Queue id %d\n", getQSize(newQueue));

    freeQueue(newQueue);
}