Build a queue of whole numbers on an array of capacity c that wraps round. Handle these commands:
enqueue x: add x at the rear, or printfullif the queue already holdscnumbers.dequeue: remove the front number and print it, or printempty.size: print how many numbers are in the queue.
What to build
A queue on a fixed array whose positions wrap round to the start.
Requirements
- Keep the index of the front item and a count of the items.
- Work out the rear position with the remainder operator.
- Print
fulloremptywhen a command cannot be carried out.
Input
The first line has c and q (1 ≤ c ≤ 100, 1 ≤ q ≤ 1000). Each of the next q lines has one command.
Output
One line for each dequeue and size, and for each enqueue that does not fit.
Constraints
1 ≤ c ≤ 100 and 1 ≤ q ≤ 1000.
Example
Input:
3 7
enqueue 1
enqueue 2
enqueue 3
enqueue 4
dequeue
enqueue 5
size
Output:
full
1
3
Why it works
The remainder after dividing by the capacity turns the position after the last cell back into 0, so cells freed at the start are used again.
Examples
Example 1 · Input
3 7 enqueue 1 enqueue 2 enqueue 3 enqueue 4 dequeue enqueue 5 size
Expected output
full 1 3
Example 2 · Input
1 3 dequeue enqueue 9 dequeue
Expected output
empty 9
Hints
Hint 1
Keep front and count in a struct. The rear is (front + count) % c.
Hint 2
Enqueue: refuse with full when count == c. Dequeue: refuse with empty when count == 0.
Hint 3
After a dequeue, front = (front + 1) % c.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
#include <string.h>
typedef struct {
int items[100];
int front;
int count;
int capacity;
} Queue;
int main(void) {
Queue q;
int n;
scanf("%d %d", &q.capacity, &n);
q.front = 0;
q.count = 0;
for (int i = 0; i < n; i++) {
char cmd[10];
scanf("%9s", cmd);
if (strcmp(cmd, "enqueue") == 0) {
int x;
scanf("%d", &x);
if (q.count == q.capacity) {
printf("full\n");
} else {
q.items[(q.front + q.count) % q.capacity] = x;
q.count++;
}
} else if (strcmp(cmd, "dequeue") == 0) {
if (q.count == 0) {
printf("empty\n");
} else {
printf("%d\n", q.items[q.front]);
q.front = (q.front + 1) % q.capacity;
q.count--;
}
} else {
printf("%d\n", q.count);
}
}
return 0;
}