In C: Declare two structures . The first one is a structure named Node. This str
ID: 3711117 • Letter: I
Question
In C:
Declare two structures . The first one is a structure named Node. This structure will have two members: 1) a pointer to the string to store; and 2) a pointer to the next Node to build the queue. The second structure is named Queue. This structure will have a single member named front. This member is a pointer to the the first node in the queue.
Implement a function that constructs a Queue. The constructor allocates the Queue in the heap, and must return NULL when the constructor is not able to create a Queue. The Queue must be empty, and to signal this the front pointer must be NULL. Must have these parameters:
1. Name: CreateQueue
2. Return type: A pointer to the created Queue
Implement a function that destructs a Queue. The destructor deallocates all the elements present in the Queue, and sets the pointer to the Queue to NULL. Must have these parameters:
1. Name: DestroyQueue
2. Return type: void
3. Input: A double pointer to the queue to deallocate
Explanation / Answer
// A C program to demonstrate linked list based implementation of queue
#include <stdlib.h>
#include <stdio.h>
// A linked list (LL) node to store a queue entry struct Node
{
int key; struct Node *next;
};
// The queue, front stores the front node of LL and rear stores ths
// last node of LL struct Queue
{
struct Node front, rear;
};
// A utility function to create a new linked list node.
struct Node* newNode(int k)
{
struct Node *temp = (struct Node*)malloc(sizeof(struct Node));
temp->key = k;
temp->next = NULL;
return temp;
}
// A utility function to create an empty queue
struct Queue *createQueue()
{
struct Queue *q = (struct Queue*)malloc(sizeof(struct Queue));
q->front = q->rear = NULL;
return q;
}
// The function to add a key k to q
void enQueue(struct Queue *q, int k)
{
// Create a new LL node struct Node *temp = newNode(k);
// If queue is empty, then new node is front and rear both
if (q->rear == NULL)
{
q->front = q->rear = temp;
return;
}
// Add the new node at the end of queue and change rear
q->rear->next = temp;
q->rear = temp;
}
// Function to remove a key from given queue q struct Node deQueue(struct Queue q)
{
// If queue is empty, return NULL.
if (q->front == NULL)
return NULL;
// Store previous front and move front one node ahead
struct Node *temp = q->front;
q->front = q->front->next;
// If front becomes NULL, then change rear also as NULL
if (q->front == NULL)
q->rear = NULL;
return temp;
}
// Driver Program to test anove functions
int main()
{
struct Queue *q = createQueue();
enQueue(q, 10);
enQueue(q, 20);
deQueue(q);
deQueue(q);
enQueue(q, 30);
enQueue(q, 40);
enQueue(q, 50);
struct Node *n = deQueue(q);
if (n != NULL)
printf("Dequeued item is %d", n->key);
return 0;
}