queue.c (1334B)
1 /* queue implementation based on linked list */ 2 #include <assert.h> 3 #include <stdio.h> 4 #include <string.h> 5 #include <stdlib.h> 6 7 typedef struct node node; 8 struct node { 9 node *list; 10 void *data; 11 }; 12 13 typedef struct queue queue; 14 struct queue { 15 node *head; 16 node *tail; 17 long long sz; 18 }; 19 20 queue * 21 queueinit(void) 22 { 23 queue *q = malloc(sizeof(queue)); 24 q->sz = 0; 25 q->head = q->tail = NULL; 26 return q; 27 } 28 29 void 30 queueput(queue *q, void *d) 31 { 32 node *np; 33 34 np = malloc(sizeof(node)); 35 np->data = d; 36 np->list = NULL; 37 if(q->head) 38 q->head->list = np; 39 q->head = np; 40 41 if(!q->sz) 42 q->tail = q->head; 43 q->sz++; 44 } 45 46 void * 47 queuepeek(queue *q) 48 { 49 return q->tail->data; 50 } 51 52 long long 53 queuesz(queue *q) 54 { 55 return q->sz; 56 } 57 58 void * 59 queueget(queue *q) 60 { 61 void *r; 62 node *np; 63 64 if(!q->sz) 65 return NULL; 66 67 np = q->tail; 68 q->tail = q->tail->list; 69 q->sz--; 70 if(!q->sz) 71 q->head = NULL; 72 r = np->data; 73 free(np); 74 return r; 75 } 76 77 int 78 main(int argc, char **argv) 79 { 80 (void)argc; 81 (void)argv; 82 83 int a[] = { 84 1, 2, 3, 4, 5, 85 6, 7, 8, 9, 10 86 }; 87 88 queue *q; 89 int n; 90 91 q = queueinit(); 92 for(int i=0; i<10; i++) 93 queueput(q, &a[i]); 94 95 for(int i=0; i<10; i++){; 96 assert(queuesz(q) == 10-i); 97 n = *(int *)queuepeek(q); 98 assert(n == i+1); 99 n = *(int *)queueget(q); 100 printf("%d\n", n); 101 assert(n == i+1); 102 } 103 assert(queuesz(q) == 0); 104 105 free(q); 106 107 return 0; 108 }