Queue
Using Linked List
Simple Queue
Node: Represents an element in the list, holding the data and a pointer to the next node.
Queue: Holds the pointers to the front and rear of the queue.
typedef struct Node
int data;
struct Node* next;
} Node;
Simple Queue
typedef struct Queue
Node* front;
Node* rear;
} Queue;
Initialization and Utility
// Function to initialize an empty queue
Queue* createQueue() {
Queue* q = (Queue*)malloc(sizeof(Queue));
if (q == NULL) {
perror("Failed to allocate memory for Queue");
exit(EXIT_FAILURE);
}
q->front = NULL;
q->rear = NULL;
return q;
}
// Function to check if the queue is empty
int isEmpty(Queue* q) {
return (q->front == NULL);
}
Enqueue Operation (Insertion)
Logic:
1. Create a new Node and allocate memory for it.
2. Set the new node's data and ensure its next pointer is NULL.
3. If the queue is empty, set both front and rear to the new node.
4. If not empty, the current rear's next pointer is set to the new node, and the rear pointer is updated to the
new node.
void enqueue(Queue* q, int data) {
// 1. Create a new Node
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
perror("Failed to allocate memory for Node");
exit(EXIT_FAILURE);
}
newNode->data = data;
newNode->next = NULL;
// 2. Handle empty queue case
if (isEmpty(q)) {
q->front = newNode;
q->rear = newNode;
}
// 3. Handle non-empty queue case
else {
// Current rear's next points to the new node
q->rear->next = newNode;
// Update rear to the new node
q->rear = newNode;
}
printf("Enqueued: %d\n", data);
}
Dequeue Operation (Deletion)
Logic:
1. Check if the queue is empty; if so, return an error value.
2. Store the front node (the one to be deleted) in a temporary pointer.
3. Store the data to be returned.
4. Move the front pointer to the next node (q->front = q->front->next).
5. If the queue becomes empty, set rear to NULL.
6. Free the memory of the original front node.
int dequeue(Queue* q) {
if (isEmpty(q)) {
printf("Error: Dequeue from an empty queue.\n");
return -1; // Return an indicator of failure
}
// 1. Store the front node and its data
Node* temp = q->front;
int data = temp->data;
// 2. Move the front pointer to the next node
q->front = q->front->next;
// 3. If front becomes NULL, the queue is empty, so rear must also be NULL
if (q->front == NULL) {
q->rear = NULL;
}
// 4. Free the memory of the dequeued node
free(temp);
printf("Dequeued: %d\n", data);
return data;
}
// Full code
int main() {
Queue* my_queue = createQueue();
// Enqueue operations
enqueue(my_queue, 10);
enqueue(my_queue, 20);
enqueue(my_queue, 30);
// Dequeue operations
dequeue(my_queue); // Dequeued: 10
dequeue(my_queue); // Dequeued: 20
if (!isEmpty(my_queue)) {
printf("Current front element: %d\n", my_queue->front->data); // Should be 30
}
dequeue(my_queue); // Dequeued: 30
dequeue(my_queue); // Error: Dequeue from an empty queue.
// Clean up allocated memory for the Queue structure itself
free(my_queue);
return 0;
}
