Merge branch 'master' of caffeine:/users/www/www/
[mspang/www.git] / unix102 / queue.txt
1 #include <stdio.h>
2 #include <stdlib.h>
3
4 struct list {
5    int head;
6    struct list *tail;
7 };
8
9 typedef struct list list;
10
11 typedef struct {
12    list *front;
13    list *back;
14 } queue;
15
16 void list_free(list *lst) {
17    list *p;
18
19    while (lst != NULL) {
20       p = lst;
21       lst = lst->tail;
22       free(p);
23    }
24 }
25
26 list * cons(int val, list *lst) {
27    list *new = malloc(sizeof(list));
28    if (new == NULL) abort();
29
30    new->head = val;
31    new->tail = lst;
32
33    return new;
34 }
35
36 void list_print(list *lst) {
37    list *p = lst;
38
39    while (p != NULL) {
40       printf("%d ", p->head);
41       p = p->tail;
42    }
43 }
44
45 queue * make_queue() {
46    queue *new = malloc(sizeof(queue));
47    if (new == NULL) abort();
48
49    new->front = NULL;
50    new->back = NULL;
51
52    return new;
53 }
54
55 void push(int val, queue *q) {
56    if (q->front == NULL) { // empty queue
57       q->front = cons(val, NULL);
58       q->back = q->front;
59    }
60
61    else {
62       list *new = cons(val, NULL);
63       (q->back)->tail = new;
64       q->back = new;
65    }
66 }
67
68 int pop(queue *q) {
69    int val = (q->front)->head;
70    list *newhead = (q->front)->tail;
71    (q->front)->tail = NULL;
72    list_free(q->front);
73    q->front = newhead;
74
75    return val;
76 }
77
78 void queue_print(queue *q) {
79    printf("back ");
80    list_print(q->front);
81    printf("front\n");
82 }
83
84 void queue_free(queue *q) {
85    list_free(q->front);
86    free(q);
87 }
88
89 int main() {
90    queue *q = make_queue();
91    push(5, q);
92    push(3, q);
93    push(1, q);
94    queue_print(q);
95    printf("popped %d!\n", pop(q));
96    queue_print(q);
97    queue_free(q);
98
99    return 0;
100 }