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!