Repair a queue that says it is full while it still has empty cells.
What to build
A corrected queue of capacity 3 that reuses the cells freed at its front.
Requirements
- The starter's queue never wraps round, so it reports
fulltoo early. Fix it. enqueue xaddsx, or printsfullonly when the queue really holds 3 items.dequeueremoves the front item and prints it, or printsempty.
Input
The first line has q. Each of the next q lines has one command.
Output
One line for each dequeue, and for each enqueue that does not fit.
Constraints
1 ≤ q ≤ 100. The capacity is always 3.
Example
Input:
6
enqueue 1
enqueue 2
enqueue 3
dequeue
enqueue 4
dequeue
Output:
1
2
Why it works
In the starter, rear only ever moves right, so cells freed by a dequeue are never used again. Wrapping the positions with % makes the array a ring, and a count tells full from empty.
Examples
Example 1 · Input
6 enqueue 1 enqueue 2 enqueue 3 dequeue enqueue 4 dequeue
Expected output
1 2
Example 2 · Input
5 enqueue 1 enqueue 2 enqueue 3 enqueue 4 dequeue
Expected output
full 1
Hints
Hint 1
Follow the first example by hand: after three enqueues and one dequeue, where is rear, and is there a free cell?
Hint 2
Keep front and a count. The rear position is (front + count) % CAPACITY.
Hint 3
The queue is full only when count equals CAPACITY.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
#include <string.h>
#define CAPACITY 3
int items[CAPACITY];
int front = 0, count = 0;
int main(void) {
int q;
scanf("%d", &q);
for (int i = 0; i < q; i++) {
char cmd[10];
scanf("%9s", cmd);
if (strcmp(cmd, "enqueue") == 0) {
int x;
scanf("%d", &x);
if (count == CAPACITY) {
printf("full\n");
} else {
items[(front + count) % CAPACITY] = x;
count++;
}
} else {
if (count == 0) {
printf("empty\n");
} else {
printf("%d\n", items[front]);
front = (front + 1) % CAPACITY;
count--;
}
}
}
return 0;
}