give with output and time complexity
Here's the complete queue implementation with output and time complexity analysis:
#include <stdio.h>
#include <stdlib.h>
// Node structure for singly linked list-based queue
struct Node {
int data; // Data stored in the node
struct Node *next; // Pointer to next node
};
// Global front and rear pointers for queue operations
struct Node *front = NULL; // Points to first element (front of queue)
struct Node *rear = NULL; // Points to last element (rear of queue)
// Enqueue operation: Insert new element at rear (end) of queue [O(1)]
void enqueue(int value) {
struct Node *t; // Temporary pointer for new node
// Allocate memory for new node
t = (struct Node*)malloc(sizeof(struct Node));
// Check for memory allocation failure
if (t == NULL) {
printf("Queue Overflow! Memory not available\n");
return;
}
// Initialize new node
t->data = value;
t->next = NULL;
// Case 1: Queue is empty (first element)
if (front == NULL) {
front = rear = t; // Both front and rear point to new node
}
// Case 2: Queue has elements (add to rear)
else {
rear->next = t; // Link current rear to new node
rear = t; // Update rear to new node
}
printf("%d inserted into queue\n", value);
}
// Dequeue operation: Remove and return element from front of queue [O(1)]
int dequeue() {
struct Node *t; // Temporary pointer to front node
int x = -1; // Return value (-1 if empty)
// Check if queue is empty
if (front == NULL) {
printf("Queue Underflow! Queue is empty\n");
} else {
// Store front node and its data
t = front;
x = front->data;
// Move front pointer to next node
front = front->next;
// If queue becomes empty after deletion
if (front == NULL) {
rear = NULL; // Set rear to NULL too
}
// Free memory of deleted node
free(t);
}
return x;
}
// Display all elements in queue from front to rear [O(n)]
void display() {
struct Node *p = front; // Traversal pointer starting from front
// Check if queue is empty
if (p == NULL) {
printf("Queue is empty\n");
return;
}
printf("Queue elements are: ");
// Traverse and print all nodes until reaching NULL
while (p != NULL) {
printf("%d ", p->data);
p = p->next; // Move to next node
}
printf("\n");
}
// Main function demonstrating queue operations
int main() {
// Insert elements at rear (enqueue)
enqueue(10);
enqueue(20);
enqueue(30);
// Display current queue: 10 20 30
display();
// Remove element from front (dequeue)
printf("Deleted element: %d\n", dequeue());
// Display updated queue: 20 30
display();
return 0;
}
Expected Output
10 inserted into queue
20 inserted into queue
30 inserted into queue
Queue elements are: 10 20 30
Deleted element: 10
Queue elements are: 20 30
Time Complexity Analysis
Operation Time Complexity Space Complexity Remarks
enqueue() O(1) O(1) Direct access to rear pointer
dequeue() O(1) O(1) Direct access to front pointer
display() O(n) O(1) Must traverse all n elements
Overall O(1) amortized O(n) For basic queue operations
Save as: queue_linkedlist.c
Key Advantages:
Dynamic memory allocation (grows as needed)
No fixed size limitation
Both enqueue/dequeue operations are O(1) - optimal for queue
Proper memory management with free()