stack.c (1309B)
1 /* stack implementation based on linked list */ 2 #include <assert.h> 3 #include <stdio.h> 4 #include <stdlib.h> 5 #include <string.h> 6 7 typedef struct node node; 8 struct node { 9 void *data; 10 node *next; 11 node *prev; 12 }; 13 14 typedef struct stack stack; 15 struct stack { 16 node *head; 17 size_t sz; 18 }; 19 20 void 21 stackinit(stack *s) 22 { 23 s->head = NULL; 24 s->sz = 0; 25 } 26 27 size_t 28 stacksz(stack *s) 29 { 30 return s->sz; 31 } 32 33 void 34 stackpush(stack *s, void *a) 35 { 36 s->sz++; 37 if(s->head == NULL){ 38 s->head = malloc(sizeof(node)); 39 s->head->data = a; 40 s->head->next = malloc(sizeof(node)); 41 s->head->next->prev = s->head; 42 s->head->prev = NULL; 43 s->head = s->head->next; 44 return; 45 } 46 47 s->head->data = a; 48 s->head->next = malloc(sizeof(node)); 49 s->head->next->prev = s->head; 50 s->head = s->head->next; 51 } 52 53 void * 54 stackpop(stack *s) 55 { 56 void *r; 57 node *np; 58 59 if(s->head->prev == NULL) 60 return NULL; 61 62 r = s->head->prev->data; 63 np = s->head; 64 s->head = s->head->prev; 65 free(np); 66 s->sz--; 67 return r; 68 } 69 70 int 71 main(int argc, char **argv) 72 { 73 int a[] = { 74 1, 2, 3, 4, 5, 75 6, 7, 8, 9, 10 76 }; 77 78 stack s; 79 80 stackinit(&s); 81 for(int i=0; i<10; i++){ 82 stackpush(&s, &a[i]); 83 assert(stacksz(&s) == i+1); 84 } 85 86 for(int i=0; i<10; i++){ 87 assert(stacksz(&s) == 10-i); 88 assert(*(int *)stackpop(&s) == a[9-i]); 89 } 90 91 assert(NULL == stackpop(&s)); 92 93 return 0; 94 }