Queues with C

Search…
Queues with C
Basic template and methods
Operations:
int peek − Gets the element at the front of the queue without removing it.
bool isFull − Checks if the queue is full.
bool isEmpty − Checks if the queue is empty.
void enQueue − add (store) an item to the queue.
void deQueue − remove (access) an item from the queue.
void printQueue
Construct Queue by Array:
1
#include <stdio.h>
2
#include <stdlib.h>
3
#include <stdbool.h>
4
#include <limits.h>
5
​
6
​
7
struct Queue {
8
    unsigned capacity;
9
    int size;
10
    int front; // index of the front node
11
    int rear; // index of the last one
12
    int* array;
13
};
14
​
15
struct Queue* createQueue(unsigned capacity){
16
    struct Queue* queue = (struct Queue*) malloc(sizeof(struct Queue));
17
    queue -> capacity = capacity;
18
    queue -> size = 0;
19
    queue -> front = 0;
20
    queue -> rear = capacity - 1; // key !!
21
    queue -> array = (int*)malloc(queue -> capacity * (sizeof(int)));
22
    
23
    return queue;
24
}
25
​
26
​
27
bool isFull(struct Queue* queue){
28
    return queue -> size == queue -> capacity;
29
}
30
​
31
bool isEmpty(struct Queue* queue){
32
    return queue -> size == 0;
33
}
34
​
35
​
36
void enQueue(struct Queue* queue, int data){
37
    if(isFull(queue)){
38
        return;
39
    }
40
    
41
    queue->rear = (queue->rear + 1) % queue->capacity;
42
    queue->size = queue->size + 1;
43
    queue->array[queue->rear] = data;
44
}
45
​
46
int deQueue(struct Queue* queue){
47
    if(isEmpty(queue)){
48
        return INT_MIN;
49
    }
50
    
51
    int frontData = queue->array[queue->front];
52
    queue->front = (queue->front + 1 ) % queue->capacity;
53
    queue->size = queue->size - 1;
54
    return frontData;
55
}
56
​
57
int front(struct Queue* queue){
58
    if(isEmpty(queue)){
59
        return INT_MIN;
60
    }
61
    return queue->array[queue->front];
62
}
63
​
64
int rear(struct Queue* queue){
65
    if(isFull(queue)){
66
        return INT_MIN;
67
    }
68
    return queue->array[queue->rear];
69
}
70
    
71
​
72
void printQueue(struct Queue* queue){
73
    if(isEmpty(queue)){
74
        return;
75
    }
76
    
77
    for(int i = queue->front; i < queue->rear + 1; i++){
78
        printf("queue[%d] = %d \n", i, queue->array[i]);
79
    }
80
}
81
​
Copied!
Test Code:
1
int main(){
2
​
3
    struct Queue* queue = createQueue(10);
4
 
5
    enQueue(queue, 10);
6
    enQueue(queue, 20);
7
    enQueue(queue, 30);
8
    enQueue(queue, 40);
9
 
10
    printf("%d dequeued from queue\n\n",
11
           deQueue(queue));
12
 
13
    printf("Front item is %d\n", front(queue));
14
    printf("Rear item is %d\n", rear(queue));
15
    printQueue(queue);
16
​
17
    return 0;
18
}
Copied!
Construct Queue by Linked List:
1
#include <stdio.h>
2
#include <stdlib.h>
3
#include <stdbool.h>
4
#include <limits.h>
5
​
6
struct queueNode {
7
    int data;
8
    struct queueNode* next;
9
};
10
​
11
struct Queue {
12
    struct queueNode *front, *rear;
13
    unsigned capacity;
14
    int size;
15
};
16
​
17
struct queueNode* newNode(int data){
18
    struct queueNode* node = (struct queueNode*) malloc(sizeof(struct queueNode));
19
    node -> data = data;
20
    node -> next = NULL;
21
​
22
    return node;
23
}
24
​
25
struct Queue* createQueue(unsigned capacity){
26
    struct Queue* queue = (struct Queue*) malloc (sizeof (struct Queue));
27
    
28
    queue->capacity = capacity;
29
    queue->size = 0;
30
    queue->front = NULL;
31
    queue->rear = NULL;
32
    
33
    return queue;
34
    
35
}
36
​
37
​
38
bool isFull(struct Queue* queue){
39
    return queue -> size == queue -> capacity;
40
}
41
​
42
bool isEmpty(struct Queue* queue){
43
    return queue -> size == 0;
44
}
45
​
46
​
47
void enQueue(struct Queue* queue, int data){
48
​
49
    if(isFull(queue)){
50
        return;
51
    }
52
    
53
    struct queueNode* node = newNode(data);
54
    
55
    if(isEmpty(queue)){
56
        queue->front = node;
57
        queue->rear = node;
58
        queue->size = 1;
59
        return;
60
    }
61
    
62
    queue->rear->next = node;
63
    queue->rear = node;
64
    queue->size = queue->size + 1;
65
}
66
​
67
int deQueue(struct Queue* queue){
68
    if(isEmpty(queue)){
69
        return INT_MIN;
70
    }
71
    
72
    struct queueNode* tmp = queue->front;
73
    
74
    int frontData = tmp->data;
75
    queue->front = queue->front->next;
76
    
77
    if(queue->front == NULL){
78
        queue->rear = NULL;
79
    }
80
    queue->size = queue->size - 1;
81
    free(tmp);
82
    
83
    return frontData;
84
}
85
​
86
int front(struct Queue* queue){
87
    if(isEmpty(queue)){
88
        return INT_MIN;
89
    }
90
    return queue->front->data;
91
}
92
​
93
int rear(struct Queue* queue){
94
    if(isFull(queue)){
95
        return INT_MIN;
96
    }
97
    return queue->rear->data;
98
}
99
    
100
​
101
void printQueue(struct Queue* queue){
102
    if(isEmpty(queue)){
103
        return;
104
    }
105
​
106
    int i = 0;
107
    struct queueNode* q = queue->front;
108
    while( q != NULL){
109
        printf("Node[%d] = %d \n", i, q->data);
110
        q = q->next;
111
    }
112
}
Copied!
Test Code:
1
int main(){
2
​
3
    struct Queue* queue = createQueue(10);
4
 
5
    enQueue(queue, 10);
6
    enQueue(queue, 20);
7
    deQueue(queue);
8
    deQueue(queue);
9
    enQueue(queue, 30);
10
    enQueue(queue, 40);
11
    enQueue(queue, 50);
12
    deQueue(queue);
13
 
14
​
15
    printf("Front item is %d\n", front(queue));
16
    printf("Rear item is %d\n", rear(queue));
17
    printQueue(queue);
18
​
19
    return 0;
20
}
Copied!
​https://www.geeksforgeeks.org/queue-set-1introduction-and-array-implementation/
https://www.geeksforgeeks.org/queue-linked-list-implementation/​
Templates and methods - Previous
Stacks with C
Next - Templates and methods
Graphs with C/C++
Last modified 3mo ago
Copy link
Contents
Operations:
Construct Queue by Array:
Test Code:
Construct Queue by Linked List:
Test Code: