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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
| #include <stdio.h>
#include <stdlib.h>
typedef int data;
typedef struct node* node;
typedef struct double_queue* dqueue;
struct node {
data item;
node prev, next;
};
struct double_queue {
int count;
node head, tail;
};
void dq_init(dqueue dq) {
dq->count = 0;
dq->head = dq->tail = NULL;
}
int dq_empty(dqueue dq) {
return dq->count == 0;
}
//add item from head
void dq_unshift(dqueue dq, data item) {
node t = malloc(sizeof *t);
t->item = item;
t->prev = NULL;
t->next = dq->head;
if (dq->count) {
dq->head->prev = t;
} else {
dq->tail = t;
}
dq->head = t;
dq->count++;
}
//add item from tail
void dq_push(dqueue dq, data item) {
node t = malloc(sizeof *t);
t->item = item;
t->prev = dq->tail;
t->next = NULL;
if (dq->count) {
dq->tail->next = t;
} else {
dq->head = t;
}
dq->tail= t;
dq->count++;
}
//delete first item
data dq_shift(dqueue dq) {
data item = dq->head->item;
dq->head->next->prev = NULL;
dq->head = dq->head->next;
dq->count--;
return item;
}
//delete last item
data dq_pop(dqueue dq) {
data item = dq->tail->item;
dq->tail->prev->next = NULL;
dq->tail = dq->tail->prev;
dq->count--;
return item;
}
void dq_for_each(dqueue dq, void f(data)) {
node t = malloc(sizeof *t);
for (t = dq->head; t != NULL; t = t->next) {
f(t->item);
}
}
int* dq_map(dqueue dq, data f(data)) {
int *a = malloc(dq->count * sizeof(int)), i;
node t = malloc(sizeof *t);
for (t = dq->head, i = 0; t != NULL; t = t->next, i++) {
a[i] = f(t->item);
}
return a;
}
void f(data item) {
printf("%d ", item);
}
data f2(data item) {
return 10*item;
}
void array_for_each(int a[]) {
}
int main() {
int i;
dqueue dq = malloc(sizeof *dq);
dq_init(dq);
for (i = 0; i < 4; i++) {
dq_push(dq, 3*i+1);
}
printf("count: %d\n", dq->count);
dq_for_each(dq, f);
printf("\n");
int *a = dq_map(dq, f2);
for (i = 0; i < dq->count; i++) {
printf("%d ", a[i]);
}
printf("\n");
data tail = dq_pop(dq);
printf("delete tail: %d\n", tail);
data head = dq_shift(dq);
printf("delete head: %d\n", head);
printf("count: %d\n", dq->count);
dq_for_each(dq, f);
printf("\n");
return 0;
}
|