Project 1 - Implement a fully functional Queue in C language using Linked lists

CODE:

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

// Queue node
struct QueueNode {
int data;
struct QueueNode* next;
};

// Queue data structure
struct Queue {
struct QueueNode *front, *rear;
};

// Create a new node
struct QueueNode* createNode(int data) {
struct QueueNode* newNode = (struct QueueNode*)malloc(sizeof(struct QueueNode));
newNode->data = data;
newNode->next = NULL;
return newNode;
}

// Initialize a new empty queue
struct Queue* createQueue() {
struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
queue->front = queue->rear = NULL;
return queue;
}

// Add an element to the rear of the queue
void enqueue(struct Queue* queue, int data) {
struct QueueNode* newNode = createNode(data);

if (queue->rear == NULL) {
queue->front = queue->rear = newNode;
return;
}

queue->rear->next = newNode;
queue->rear = newNode;
}

// Remove an element from the front of the queue
void dequeue(struct Queue* queue) {
if (queue->front == NULL) {
printf("Queue is empty\n");
return;
}

struct QueueNode* temp = queue->front;
queue->front = queue->front->next;

if (queue->front == NULL) {
queue->rear = NULL;
}

free(temp);
}

// Get the element at the front of the queue without removing it
int peek(struct Queue* queue) {
if (queue->front == NULL) {
printf("Queue is empty\n");
return -1;
}

return queue->front->data;
}

// Check if the queue is empty
int isEmpty(struct Queue* queue) {
return queue->front == NULL;
}

// Print the elements of the queue
void printQueue(struct Queue* queue) {
struct QueueNode* temp = queue->front;

if (temp == NULL) {
printf("Queue is empty\n");
return;
}

printf("Queue elements are: ");
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}

// Driver program to test the queue implementation
int main() {
struct Queue* queue = createQueue();

// Add elements to the queue
enqueue(queue, 10);
enqueue(queue, 20);
enqueue(queue, 30);
enqueue(queue, 40);

// Print the queue elements
printQueue(queue);

// Print the front element of the queue
printf("Front element is %d\n", peek(queue));

// Remove elements from the queue
dequeue(queue);
dequeue(queue);

// Print the queue elements after removal
printQueue(queue);

// Print the front element of the queue after removal
printf("Front element is %d\n", peek(queue));

return 0;
}

Doubly Linked List

It is called the doubly linked list because there are two pointers, one point to the next node and other points to the previous node. The operations performed in doubly linked are similar to that of a singly linked list.

Introduction to Implementation of Queue using Linked List

A queue is a linear data structure that follows the First in, First out principle(FIFO). Queue supports operations like enqueue and dequeue. It can be implemented using an array and linked list. The benefit of implementing a queue using a linked list over arrays is that it allows to grow the queue as per the requirements, i.e., memory can be allocated dynamically.

Operation on Linked Queue

Each node of a linked queue consists of two fields: data and next(storing address of next node). The data field of each node contains the assigned value, and the next points to the node containing the next item in the queue.

A linked queue consists of two pointers, i.e., the front pointer and the rear pointer. The front pointer stores the address of the first element of the queue, and the rear pointer stores the address of the last element of the queue.

Insertion is performed at the rear end, whereas deletion is performed at the front end of the queue. If front and rear both points to NULL, it signifies that the queue is empty.

The two main operations performed on the linked queue are:

• Insertion
• Deletion

Insertion

Insert operation or insertion on a linked queue adds an element to the end of the queue. The new element which is added becomes the last element of the queue.

Deletion

Deletion or delete operation on a linked queue removes the element which was first inserted in the queue, i.e., always the first element of the queue is removed.

• Queue is a linear data structure that follows the First in, First Out Principle (FIFO).
• Queue can be represented using nodes of a linked list.
• Queue supports operations such as enqueue, dequeue and print().
• Elements can be enqueued from one end and dequeued from the other one end.
• Enqueue and Dequeue operations take O(1) time.