Program On Queue In C

Have you ever seen a program on queue in C? No. Then you are in the right place. Today we will write a program in C that will use the queue data structure.

What is Queue?

program on queue in c
Queue

In C, a queue is essentially a linear data structure for managing and storing data components. First In, First Out is the sequence that it follows (FIFO).

The first element adds to an array in a queue is also the first element withdraw from the array.

Let’s use the example of a ticket booth for buses as an example.

program on queue in c
The queue for Buying a Ticket

Here Queue approach has been implemented. The first person who arrives will take the tickets since the queue implements a first-come, first-served basis.

There is an open line at both ends. There are two ends: one for inserting data and the other for removing it. GeeksforGeeks has written a good article on Queue Data Structure, Take a look

Program on Queue in C

We will try to implement LRU caching using Queue in C. When the cache is full and a new page is referred to that is not included in the cache, the LRU caching mechanism removes the least recently used frame.

The queue is using a doubly-linked list. The maximum queue size will match the total number of available frames (cache size). The pages that have been used most recently will be in the front, while the ones that have been used least recently will be toward the back.

// A C program to show implementation of LRU cache
#include <stdio.h>
#include <stdlib.h>
  
// A Queue Node (Queue is implemented using Doubly Linked List)
typedef struct QNode {
    struct QNode *prev, *next;
    unsigned pageNumber; // the page number stored in this QNode
} QNode;
  
// A Queue (A FIFO collection of Queue Nodes)
typedef struct Queue {
    unsigned count; // Number of filled frames
    unsigned numberOfFrames; // total number of frames
    QNode *front, *rear;
} Queue;
  
// A hash (Collection of pointers to Queue Nodes)
typedef struct Hash {
    int capacity; // how many pages can be there
    QNode** array; // an array of queue nodes
} Hash;
  
// A utility function to create a new Queue Node. The queue Node
// will store the given 'pageNumber'
QNode* newQNode(unsigned pageNumber)
{
    // Allocate memory and assign 'pageNumber'
    QNode* temp = (QNode*)malloc(sizeof(QNode));
    temp->pageNumber = pageNumber;
  
    // Initialize prev and next as NULL
    temp->prev = temp->next = NULL;
  
    return temp;
}
  
// A utility function to create an empty Queue.
// The queue can have at most 'numberOfFrames' nodes
Queue* createQueue(int numberOfFrames)
{
    Queue* queue = (Queue*)malloc(sizeof(Queue));
  
    // The queue is empty
    queue->count = 0;
    queue->front = queue->rear = NULL;
  
    // Number of frames that can be stored in memory
    queue->numberOfFrames = numberOfFrames;
  
    return queue;
}
  
// A utility function to create an empty Hash of given capacity
Hash* createHash(int capacity)
{
    // Allocate memory for hash
    Hash* hash = (Hash*)malloc(sizeof(Hash));
    hash->capacity = capacity;
  
    // Create an array of pointers for referring queue nodes
    hash->array = (QNode**)malloc(hash->capacity * sizeof(QNode*));
  
    // Initialize all hash entries as empty
    int i;
    for (i = 0; i < hash->capacity; ++i)
        hash->array[i] = NULL;
  
    return hash;
}
  
// A function to check if there is slot available in memory
int AreAllFramesFull(Queue* queue)
{
    return queue->count == queue->numberOfFrames;
}
  
// A utility function to check if queue is empty
int isQueueEmpty(Queue* queue)
{
    return queue->rear == NULL;
}
  
// A utility function to delete a frame from queue
void deQueue(Queue* queue)
{
    if (isQueueEmpty(queue))
        return;
  
    // If this is the only node in list, then change front
    if (queue->front == queue->rear)
        queue->front = NULL;
  
    // Change rear and remove the previous rear
    QNode* temp = queue->rear;
    queue->rear = queue->rear->prev;
  
    if (queue->rear)
        queue->rear->next = NULL;
  
    free(temp);
  
    // decrement the number of full frames by 1
    queue->count--;
}
  
// A function to add a page with given 'pageNumber' to both queue
// and hash
void Enqueue(Queue* queue, Hash* hash, unsigned pageNumber)
{
    // If all frames are full, remove the page at the rear
    if (AreAllFramesFull(queue)) {
        // remove page from hash
        hash->array[queue->rear->pageNumber] = NULL;
        deQueue(queue);
    }
  
    // Create a new node with given page number,
    // And add the new node to the front of queue
    QNode* temp = newQNode(pageNumber);
    temp->next = queue->front;
  
    // If queue is empty, change both front and rear pointers
    if (isQueueEmpty(queue))
        queue->rear = queue->front = temp;
    else // Else change the front
    {
        queue->front->prev = temp;
        queue->front = temp;
    }
  
    // Add page entry to hash also
    hash->array[pageNumber] = temp;
  
    // increment number of full frames
    queue->count++;
}
  
// This function is called when a page with given 'pageNumber' is referenced
// from cache (or memory). There are two cases:
// 1. Frame is not there in memory, we bring it in memory and add to the front
// of queue
// 2. Frame is there in memory, we move the frame to front of queue
void ReferencePage(Queue* queue, Hash* hash, unsigned pageNumber)
{
    QNode* reqPage = hash->array[pageNumber];
  
    // the page is not in cache, bring it
    if (reqPage == NULL)
        Enqueue(queue, hash, pageNumber);
  
    // page is there and not at front, change pointer
    else if (reqPage != queue->front) {
        // Unlink rquested page from its current location
        // in queue.
        reqPage->prev->next = reqPage->next;
        if (reqPage->next)
            reqPage->next->prev = reqPage->prev;
  
        // If the requested page is rear, then change rear
        // as this node will be moved to front
        if (reqPage == queue->rear) {
            queue->rear = reqPage->prev;
            queue->rear->next = NULL;
        }
  
        // Put the requested page before current front
        reqPage->next = queue->front;
        reqPage->prev = NULL;
  
        // Change prev of current front
        reqPage->next->prev = reqPage;
  
        // Change front to the requested page
        queue->front = reqPage;
    }
}
  
// Driver program to test above functions
int main()
{
    // Let cache can hold 4 pages
    Queue* q = createQueue(4);
  
    // Let 10 different pages can be requested (pages to be
    // referenced are numbered from 0 to 9
    Hash* hash = createHash(10);
  
    // Let us refer pages 1, 2, 3, 1, 4, 5
    ReferencePage(q, hash, 1);
    ReferencePage(q, hash, 2);
    ReferencePage(q, hash, 3);
    ReferencePage(q, hash, 1);
    ReferencePage(q, hash, 4);
    ReferencePage(q, hash, 5);
  
    // Let us print cache frames after the above referenced pages
    printf("%d ", q->front->pageNumber);
    printf("%d ", q->front->next->pageNumber);
    printf("%d ", q->front->next->next->pageNumber);
    printf("%d ", q->front->next->next->next->pageNumber);
  
    return 0;
}

The Code is take from GeeksforGeeks

READ MORE

C/C++ related posts Visit HERE

Python-related posts Visit HERE

Databases related posts Visit HERE

Data Structures related posts visit HERE

Algorithms related posts visit HERE

Data Science related posts visit HERE

Follow us:

Leave a Comment