Implement push and pop for a stack that doubles its capacity when full.
Solution
main.c
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
struct stack {
int *items;
size_t len, cap;
};
bool push(struct stack *s, int v) {
if (s->len == s->cap) {
size_t cap = s->cap ? 2 * s->cap : 2;
int *tmp = realloc(s->items, cap * sizeof *tmp);
if (tmp == NULL)
return false;
s->items = tmp;
s->cap = cap;
}
s->items[s->len++] = v;
return true;
}
bool pop(struct stack *s, int *v) {
if (s->len == 0)
return false;
*v = s->items[--s->len];
return true;
}
int main(void) {
struct stack s = {0};
for (int v = 1; v <= 10; v++)
if (!push(&s, v))
return 1;
int v;
printf("popped:");
for (int i = 0; i < 3 && pop(&s, &v); i++)
printf(" %d", v);
printf("\nlen %zu, cap %zu\n", s.len, s.cap);
free(s.items);
return 0;
}
Output Verified by compiling and running
popped: 10 9 8
len 7, cap 16
Capacity goes 2 → 4 → 8 → 16 as 10 items arrive; doubling keeps the average cost of a push constant. Pop only shrinks len; the memory is reused by later pushes.
Share your method, a shortcut, or ask about a step you didn't follow.
No comments yet. Be the first to share your solution!
We use Google Analytics cookies to see how LearnFrenzy is used and make it better, and Google AdSense to keep it free.
No analytics or ad cookies are set until you accept. Privacy Policy
·
Discussion & Comments 0
Share your method, a shortcut, or ask about a step you didn't follow.
No comments yet. Be the first to share your solution!