Run a list of commands on a stack that has a fixed capacity.
What to build
An array stack that refuses to overflow or underflow.
Requirements
push xaddsx, or printsoverflowif the stack already holdscitems.popremoves the top item and prints it, or printsunderflow.peekprints the top item without removing it, or printsempty.sizeprints the number of items.
Input
The first line has c and q. Each of the next q lines has one command.
Output
One line for each pop, peek and size, and for each push that does not fit.
Constraints
1 ≤ c ≤ 100 and 1 ≤ q ≤ 1000.
Example
Input:
2 6
push 5
push 7
push 9
peek
pop
size
Output:
overflow
7
7
1
Why it works
Every command looks only at the top of the stack, so each one takes the same small number of steps however many items there are.
Examples
Example 1 · Input
2 6 push 5 push 7 push 9 peek pop size
Expected output
overflow 7 7 1
Example 2 · Input
3 3 pop peek size
Expected output
underflow empty 0
Hints
Hint 1
Keep the items in an array and top as the index of the newest item, starting at -1.
Hint 2
The stack is full when top is c - 1, and empty when top is -1.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
#include <string.h>
int items[100];
int top = -1;
int main(void) {
int c, q;
scanf("%d %d", &c, &q);
for (int i = 0; i < q; i++) {
char cmd[10];
scanf("%9s", cmd);
if (strcmp(cmd, "push") == 0) {
int x;
scanf("%d", &x);
if (top == c - 1) printf("overflow\n");
else items[++top] = x;
} else if (strcmp(cmd, "pop") == 0) {
if (top == -1) printf("underflow\n");
else printf("%d\n", items[top--]);
} else if (strcmp(cmd, "peek") == 0) {
if (top == -1) printf("empty\n");
else printf("%d\n", items[top]);
} else {
printf("%d\n", top + 1);
}
}
return 0;
}