-
Notifications
You must be signed in to change notification settings - Fork 0
/
3_3_stack_of_stacks.c
94 lines (79 loc) · 1.94 KB
/
3_3_stack_of_stacks.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
#include <stdio.h>
#include <stdlib.h>
struct stack {
struct node *top;
int n_items;
};
struct node {
void *value;
struct node *next;
};
void panic(char *s) {
fprintf(stderr,s);
exit(1);
}
struct stack *stack_new() {
struct stack *s = malloc(sizeof(*s));
if (s == NULL)
panic("enomem");
s->top = NULL;
s->n_items = 0;
return s;
}
struct node *node_new(void *value) {
struct node *n = malloc(sizeof(*n));
if (n == NULL)
panic("enomem");
n->value = value;
n->next = NULL;
return n;
}
struct node *s_peek(struct stack *s) {
return s->top;
}
void s_push(struct stack *s, struct node *n) {
n->next = s->top;
s->top = n;
s->n_items++;
}
struct node *s_pop(struct stack *s) {
struct node *popped = s->top;
if (popped == NULL)
return NULL;
s->top = popped->next;
s->n_items--;
return popped;
}
struct stack *b_current_stack(struct stack *balancer) {
struct node *n = s_peek(balancer);
return (struct stack *) (n ? n->value : NULL);
}
void b_push(struct stack *balancer, struct node *n, int thresh) {
struct stack *s = b_current_stack(balancer);
if (s == NULL || s->n_items >= thresh) {
s = stack_new();
s_push(balancer,node_new(s));
}
s_push(s,n);
}
struct node* b_pop(struct stack *balancer) {
struct stack *s = b_current_stack(balancer);
if (s == NULL)
return NULL;
struct node *n = s_pop(s);
if (s->n_items == 0) {
free(s_pop(balancer));
}
return n;
}
int main(void) {
struct stack *balancer = stack_new();
for (int i = 0; i < 10; i++) {
b_push(balancer, node_new((void *)0xbeef), 2);
printf("after push, n stacks in the balancer: %d\n",balancer->n_items);
}
for (int i = 0; i < 10; i++) {
struct node *n = b_pop(balancer);
printf("after pop, n stacks in the balancer: %d, val: %p\n",balancer->n_items, n->value);
}
}