Queues in Data Structures

1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5#define MAX_SIZE 100
6
7// Array-based queue implementation
8typedef struct {
9    int items[MAX_SIZE];
10    int front;
11    int rear;
12} Queue;
13
14// Initialize queue
15void initialize(Queue *q) {
16    q->front = -1;
17    q->rear = -1;
18}
19
20// Check if queue is full
21bool isFull(Queue *q) {
22    return q->rear == MAX_SIZE - 1;
23}
24
25// Check if queue is empty
26bool isEmpty(Queue *q) {
27    return q->front == -1 || q->front > q->rear;
28}
29
30// Add an element to the queue (enqueue)
31bool enqueue(Queue *q, int value) {
32    if (isFull(q)) {
33        printf("Queue Overflow!\n");
34        return false;
35    }
36    
37    if (q->front == -1) {
38        q->front = 0;
39    }
40    
41    q->items[++(q->rear)] = value;
42    return true;
43}
44
45// Remove an element from the queue (dequeue)
46int dequeue(Queue *q) {
47    if (isEmpty(q)) {
48        printf("Queue Underflow!\n");
49        return -1; // Assuming -1 is not a valid queue element
50    }
51    
52    int value = q->items[q->front];
53    q->front++;
54    
55    // Reset the queue when it becomes empty
56    if (q->front > q->rear) {
57        q->front = q->rear = -1;
58    }
59    
60    return value;
61}
62
63// Get the front element without removing it
64int front(Queue *q) {
65    if (isEmpty(q)) {
66        printf("Queue is empty!\n");
67        return -1;
68    }
69    
70    return q->items[q->front];
71}
72
73// Get the size of the queue
74int size(Queue *q) {
75    if (isEmpty(q)) {
76        return 0;
77    }
78    return q->rear - q->front + 1;
79}
80
81int main() {
82    Queue queue;
83    initialize(&queue);
84    
85    // Enqueue elements
86    enqueue(&queue, 10);
87    enqueue(&queue, 20);
88    enqueue(&queue, 30);
89    enqueue(&queue, 40);
90    
91    printf("Front element: %d\n", front(&queue));
92    printf("Queue size: %d\n", size(&queue));
93    
94    printf("Dequeued element: %d\n", dequeue(&queue));
95    printf("Dequeued element: %d\n", dequeue(&queue));
96    
97    printf("Queue size after dequeuing: %d\n", size(&queue));
98    printf("Front element after dequeuing: %d\n", front(&queue));
99    
100    return 0;
101}
102
103// Output:
104// Front element: 10
105// Queue size: 4
106// Dequeued element: 10
107// Dequeued element: 20
108// Queue size after dequeuing: 2
109// Front element after dequeuing: 30

1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5#define MAX_SIZE 5  // Small size to demonstrate circular behavior
6
7// Circular queue implementation
8typedef struct {
9    int items[MAX_SIZE];
10    int front;
11    int rear;
12    int size;  // Track number of elements
13} CircularQueue;
14
15// Initialize circular queue
16void initialize(CircularQueue *q) {
17    q->front = -1;
18    q->rear = -1;
19    q->size = 0;
20}
21
22// Check if circular queue is full
23bool isFull(CircularQueue *q) {
24    return q->size == MAX_SIZE;
25}
26
27// Check if circular queue is empty
28bool isEmpty(CircularQueue *q) {
29    return q->size == 0;
30}
31
32// Add an element to the circular queue (enqueue)
33bool enqueue(CircularQueue *q, int value) {
34    if (isFull(q)) {
35        printf("Queue Overflow!\n");
36        return false;
37    }
38    
39    // If queue is empty, set front to 0
40    if (isEmpty(q)) {
41        q->front = 0;
42    }
43    
44    // Move rear circularly and add element
45    q->rear = (q->rear + 1) % MAX_SIZE;
46    q->items[q->rear] = value;
47    q->size++;
48    
49    return true;
50}
51
52// Remove an element from the circular queue (dequeue)
53int dequeue(CircularQueue *q) {
54    if (isEmpty(q)) {
55        printf("Queue Underflow!\n");
56        return -1;
57    }
58    
59    int value = q->items[q->front];
60    
61    // If the last element is being removed
62    if (q->front == q->rear) {
63        q->front = q->rear = -1;
64    } else {
65        // Move front circularly
66        q->front = (q->front + 1) % MAX_SIZE;
67    }
68    
69    q->size--;
70    return value;
71}
72
73// Get the front element without removing it
74int front(CircularQueue *q) {
75    if (isEmpty(q)) {
76        printf("Queue is empty!\n");
77        return -1;
78    }
79    
80    return q->items[q->front];
81}
82
83// Get the size of the circular queue
84int size(CircularQueue *q) {
85    return q->size;
86}
87
88// Display the circular queue
89void display(CircularQueue *q) {
90    if (isEmpty(q)) {
91        printf("Queue is empty\n");
92        return;
93    }
94    
95    printf("Circular Queue: ");
96    int i = q->front;
97    int count = 0;
98    
99    while (count < q->size) {
100        printf("%d ", q->items[i]);
101        i = (i + 1) % MAX_SIZE;
102        count++;
103    }
104    printf("\n");
105}
106
107int main() {
108    CircularQueue queue;
109    initialize(&queue);
110    
111    printf("Enqueuing 10, 20, 30, 40, 50\n");
112    enqueue(&queue, 10);
113    enqueue(&queue, 20);
114    enqueue(&queue, 30);
115    enqueue(&queue, 40);
116    enqueue(&queue, 50);
117    
118    display(&queue);
119    
120    printf("Trying to enqueue 60: ");
121    if (!enqueue(&queue, 60)) {
122        printf("Failed, queue is full\n");
123    }
124    
125    printf("Dequeuing two elements\n");
126    printf("Dequeued: %d\n", dequeue(&queue));
127    printf("Dequeued: %d\n", dequeue(&queue));
128    
129    display(&queue);
130    
131    printf("Enqueuing 60, 70 after dequeuing\n");
132    enqueue(&queue, 60);
133    enqueue(&queue, 70);
134    
135    display(&queue);
136    
137    return 0;
138}
139
140// Output:
141// Enqueuing 10, 20, 30, 40, 50
142// Circular Queue: 10 20 30 40 50 
143// Trying to enqueue 60: Failed, queue is full
144// Dequeuing two elements
145// Dequeued: 10
146// Dequeued: 20
147// Circular Queue: 30 40 50 
148// Enqueuing 60, 70 after dequeuing
149// Circular Queue: 30 40 50 60 70

1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5// Node structure for linked list
6typedef struct Node {
7    int data;
8    struct Node *next;
9} Node;
10
11// Queue structure using linked list
12typedef struct {
13    Node *front;
14    Node *rear;
15    int size;
16} LinkedQueue;
17
18// Create a new node
19Node* createNode(int data) {
20    Node* newNode = (Node*)malloc(sizeof(Node));
21    if (newNode == NULL) {
22        printf("Memory allocation failed\n");
23        exit(1);
24    }
25    newNode->data = data;
26    newNode->next = NULL;
27    return newNode;
28}
29
30// Initialize queue
31void initialize(LinkedQueue *q) {
32    q->front = NULL;
33    q->rear = NULL;
34    q->size = 0;
35}
36
37// Check if queue is empty
38bool isEmpty(LinkedQueue *q) {
39    return q->front == NULL;
40}
41
42// Add an element to the queue (enqueue)
43void enqueue(LinkedQueue *q, int value) {
44    Node* newNode = createNode(value);
45    
46    // If queue is empty, both front and rear point to the new node
47    if (isEmpty(q)) {
48        q->front = q->rear = newNode;
49    } else {
50        // Add the new node at the end and update rear
51        q->rear->next = newNode;
52        q->rear = newNode;
53    }
54    
55    q->size++;
56}
57
58// Remove an element from the queue (dequeue)
59int dequeue(LinkedQueue *q) {
60    if (isEmpty(q)) {
61        printf("Queue Underflow!\n");
62        return -1;
63    }
64    
65    // Store the front node and its data
66    Node* temp = q->front;
67    int value = temp->data;
68    
69    // Move front to the next node
70    q->front = q->front->next;
71    
72    // If front becomes NULL, set rear to NULL as well
73    if (q->front == NULL) {
74        q->rear = NULL;
75    }
76    
77    // Free the memory of the dequeued node
78    free(temp);
79    q->size--;
80    
81    return value;
82}
83
84// Get the front element without removing it
85int front(LinkedQueue *q) {
86    if (isEmpty(q)) {
87        printf("Queue is empty!\n");
88        return -1;
89    }
90    
91    return q->front->data;
92}
93
94// Get the size of the queue
95int size(LinkedQueue *q) {
96    return q->size;
97}
98
99// Display the queue
100void display(LinkedQueue *q) {
101    if (isEmpty(q)) {
102        printf("Queue is empty\n");
103        return;
104    }
105    
106    printf("Queue: ");
107    Node* current = q->front;
108    while (current != NULL) {
109        printf("%d ", current->data);
110        current = current->next;
111    }
112    printf("\n");
113}
114
115// Free the memory used by the queue
116void freeQueue(LinkedQueue *q) {
117    Node* current = q->front;
118    Node* next;
119    
120    while (current != NULL) {
121        next = current->next;
122        free(current);
123        current = next;
124    }
125    
126    q->front = q->rear = NULL;
127    q->size = 0;
128}
129
130int main() {
131    LinkedQueue queue;
132    initialize(&queue);
133    
134    printf("Enqueuing 10, 20, 30, 40, 50\n");
135    enqueue(&queue, 10);
136    enqueue(&queue, 20);
137    enqueue(&queue, 30);
138    enqueue(&queue, 40);
139    enqueue(&queue, 50);
140    
141    display(&queue);
142    printf("Queue size: %d\n", size(&queue));
143    printf("Front element: %d\n", front(&queue));
144    
145    printf("Dequeuing two elements\n");
146    printf("Dequeued: %d\n", dequeue(&queue));
147    printf("Dequeued: %d\n", dequeue(&queue));
148    
149    display(&queue);
150    printf("Queue size after dequeuing: %d\n", size(&queue));
151    
152    // Free memory
153    freeQueue(&queue);
154    
155    return 0;
156}
157
158// Output:
159// Enqueuing 10, 20, 30, 40, 50
160// Queue: 10 20 30 40 50 
161// Queue size: 5
162// Front element: 10
163// Dequeuing two elements
164// Dequeued: 10
165// Dequeued: 20
166// Queue: 30 40 50 
167// Queue size after dequeuing: 3

1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4
5#define MAX_VERTICES 100
6
7// Queue structure for BFS
8typedef struct {
9    int items[MAX_VERTICES];
10    int front;
11    int rear;
12} Queue;
13
14// Graph structure
15typedef struct {
16    int vertices;
17    int** adjacencyMatrix;
18    bool* visited;
19} Graph;
20
21// Queue operations
22void initializeQueue(Queue* q) {
23    q->front = -1;
24    q->rear = -1;
25}
26
27bool isQueueEmpty(Queue* q) {
28    return q->front == -1;
29}
30
31void enqueue(Queue* q, int value) {
32    if (q->front == -1) {
33        q->front = 0;
34    }
35    q->rear++;
36    q->items[q->rear] = value;
37}
38
39int dequeue(Queue* q) {
40    int item = q->items[q->front];
41    
42    if (q->front == q->rear) {
43        q->front = q->rear = -1;
44    } else {
45        q->front++;
46    }
47    
48    return item;
49}
50
51// Graph operations
52Graph* createGraph(int vertices) {
53    Graph* graph = (Graph*)malloc(sizeof(Graph));
54    graph->vertices = vertices;
55    
56    // Create adjacency matrix
57    graph->adjacencyMatrix = (int**)malloc(vertices * sizeof(int*));
58    for (int i = 0; i < vertices; i++) {
59        graph->adjacencyMatrix[i] = (int*)malloc(vertices * sizeof(int));
60        for (int j = 0; j < vertices; j++) {
61            graph->adjacencyMatrix[i][j] = 0;
62        }
63    }
64    
65    // Initialize visited array
66    graph->visited = (bool*)malloc(vertices * sizeof(bool));
67    
68    return graph;
69}
70
71void addEdge(Graph* graph, int src, int dest) {
72    // Add edge (for undirected graph)
73    graph->adjacencyMatrix[src][dest] = 1;
74    graph->adjacencyMatrix[dest][src] = 1;
75}
76
77void resetVisited(Graph* graph) {
78    for (int i = 0; i < graph->vertices; i++) {
79        graph->visited[i] = false;
80    }
81}
82
83// Breadth-First Search algorithm using queue
84void BFS(Graph* graph, int startVertex) {
85    Queue queue;
86    initializeQueue(&queue);
87    
88    // Reset all vertices as not visited
89    resetVisited(graph);
90    
91    // Mark the start vertex as visited and enqueue it
92    graph->visited[startVertex] = true;
93    printf("BFS starting from vertex %d: ", startVertex);
94    printf("%d ", startVertex);
95    enqueue(&queue, startVertex);
96    
97    // Process vertices in BFS order
98    while (!isQueueEmpty(&queue)) {
99        // Dequeue a vertex
100        int currentVertex = dequeue(&queue);
101        
102        // Visit all adjacent vertices
103        for (int i = 0; i < graph->vertices; i++) {
104            if (graph->adjacencyMatrix[currentVertex][i] == 1 && !graph->visited[i]) {
105                graph->visited[i] = true;
106                printf("%d ", i);
107                enqueue(&queue, i);
108            }
109        }
110    }
111    printf("\n");
112}
113
114// Free the graph memory
115void freeGraph(Graph* graph) {
116    for (int i = 0; i < graph->vertices; i++) {
117        free(graph->adjacencyMatrix[i]);
118    }
119    free(graph->adjacencyMatrix);
120    free(graph->visited);
121    free(graph);
122}
123
124int main() {
125    // Create a graph with 7 vertices
126    Graph* graph = createGraph(7);
127    
128    // Add edges to create a sample graph
129    addEdge(graph, 0, 1);
130    addEdge(graph, 0, 2);
131    addEdge(graph, 1, 3);
132    addEdge(graph, 1, 4);
133    addEdge(graph, 2, 5);
134    addEdge(graph, 2, 6);
135    
136    // Perform BFS starting from vertex 0
137    BFS(graph, 0);
138    
139    // Free the graph memory
140    freeGraph(graph);
141    
142    return 0;
143}
144
145// Output:
146// BFS starting from vertex 0: 0 1 2 3 4 5 6