-
Notifications
You must be signed in to change notification settings - Fork 0
/
circular-queue.c
144 lines (115 loc) · 3.23 KB
/
circular-queue.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
/**
* A circlular queue: a first-in-first-out data structure with a fixed buffer
* size.
*/
typedef struct CircularQueue {
int size;
int readPos; // Will be `-1` when the queue is empty
int writePos;
int array[];
} CircularQueue;
/**
* Constructs a new instance of a circular queue and returns a pointer to it.
* (Make sure to `free` the pointer once you're finished with it.)
*/
CircularQueue *newCircularQueue(int bufferSize) {
if (bufferSize < 1) {
printf("Error: buffer size must be positive.\n");
return NULL;
}
CircularQueue *ptr = malloc(sizeof(CircularQueue) + bufferSize * sizeof(int));
ptr->size = bufferSize;
ptr->readPos = -1;
ptr->writePos = 0;
return ptr;
}
/** Returns whether or not a circular queue is empty. */
bool isEmpty(CircularQueue *queue) { return queue->readPos == -1; }
/** Returns whether or not a circular queue is full. */
bool isFull(CircularQueue *queue) { return queue->readPos == queue->writePos; }
/**
* Adds an element to a circular queue if the queue is not already full.
*
* @param queue A pointer to the circular queue.
* @param element The element to add.
* @return `0` if the element was successfully added, `1` if the circular queue
* was already full.
*/
int enqueue(CircularQueue *queue, int element) {
if (isFull(queue)) {
printf("Enqueue error: circular queue is already full.\n");
return 1;
}
if (isEmpty(queue))
queue->readPos = queue->writePos;
queue->array[queue->writePos] = element;
queue->writePos = (queue->writePos + 1) % queue->size;
return 0;
}
/**
* Removes an element from a circular queue if the queue is not already empty.
*
* @param queue A pointer to the circular queue.
* @return A pointer to the element removed, or `NULL` if the circular queue was
* already empty.
*/
int *dequeue(CircularQueue *queue) {
if (isEmpty(queue)) {
printf("Dequeue error: circular queue is already empty.\n");
return NULL;
}
int dequeued = queue->array[queue->readPos];
queue->readPos = (queue->readPos + 1) % queue->size;
if (queue->readPos == queue->writePos)
queue->readPos = -1;
int *ptr = &dequeued;
return ptr;
}
/** Clears the contents of a circular queue. */
void clear(CircularQueue *queue) {
queue->readPos = -1;
queue->writePos = 0;
}
/**
* Prints the contents of a circular queue to the console as comma-separated
* values, in read order.
*/
void print(CircularQueue *queue) {
if (!isEmpty(queue)) {
printf("%d", queue->array[queue->readPos]);
int i = queue->readPos + 1;
while (i != queue->writePos) {
printf(", %d", queue->array[i]);
i = (i + 1) % queue->size;
}
}
printf("\n");
}
int main() {
assert(newCircularQueue(0) == NULL);
CircularQueue *q = newCircularQueue(5);
print(q);
assert(isEmpty(q));
assert(dequeue(q) == NULL);
assert(enqueue(q, 2) == 0);
enqueue(q, 34);
assert(*dequeue(q) == 2);
enqueue(q, 1);
enqueue(q, 58);
enqueue(q, 29);
enqueue(q, 37);
assert(isFull(q));
assert(enqueue(q, 9) == 1);
print(q);
clear(q);
assert(isEmpty(q));
enqueue(q, 1);
assert(*dequeue(q) == 1);
free(q);
printf("All tests passed successfully.\n");
return 0;
}