來自于《冒號課堂》
順序表實現：
1 #include <iostream>
2 using namespace std;
3
4 typedef char ItemType;
5
6 typedef struct
7 {
8 ItemType* data;
9 int first;
10 int last;
11 int count;
12 int size;
13 } QueueType;
14
15 typedef QueueType* Queue;
16
17 int queue_initialize(Queue q)
18 {
19 int size = 100;
20 q->size = size;
21 q->data = (ItemType*)malloc(sizeof (ItemType) * size);
22 if (q->data == 0)
23 {
24 return -1;
25 }
26 q->first = 0;
27 q->last = -1;
28 q->count = 0;
29 return 0;
30 }
31
32 void queue_finalize(Queue q)
33 {
34 free(q->data);
35 q->data = 0;
36 q->first = 0;
37 q->last = -1;
38 q->count = 0;
39 }
40
41 int queue_empty(Queue q)
42 {
43 return q->count == 0;
44 }
45
46 int queue_length(Queue q)
47 {
48 return q->count;
49 }
50
51 static int queue_resize(Queue q)
52 {
53 int oldSize = q->size;
54 int newSize = oldSize * 2;
55 int newIndex;
56 int oldIndex = q->first;
57 ItemType* data = (ItemType*)malloc(sizeof (ItemType) * newSize);
58 if (data == 0)
59 {
60 return -1;
61 }
62
63 for (newIndex = 0; newIndex < q->count; ++newIndex)
64 {
65 data[newIndex] = q->data[oldIndex];
66 oldIndex = (oldIndex + 1) % oldSize;
67 }
68 free(q->data);
69 q->data = data;
70 q->first = 0;
71 q->last = oldSize - 1;
72 q->size = newSize;
73 return 0;
74 }
75
76 int queue_add(Queue q, ItemType item)
77 {
78 if (q->count >= q->size)
79 {
80 if (queue_resize(q) < 0)
81 {
82 return -1;
83 }
84 }
85 q->last = (q->last + 1) % q->size;
86 q->data[q->last] = item;
87 ++q->count;
88 return 0;
89 }
90
91 int queue_remove(Queue q, ItemType* item)
92 {
93 if (q->count <= 0)
94 {
95 return -1;
96 }
97 *item = q->data[q->first];
98 q->first = (q->first + 1) % q->size;
99 --q->count;
100 return 0;
101 }
102
103 int queue_head(Queue q, ItemType* item)
104 {
105 if (q->count <= 0)
106 {
107 return -1;
108 }
109 *item = q->data[q->first];
110 return 0;
111 }
112
113 int main()
114 {
115 QueueType queue;
116 Queue q = &queue;
117 char item;
118 int i;
119
120 queue_initialize(q);
121 for (i = 0; i < 26; ++i)
122 {
123 queue_add(q, 'a' + i);
124 }
125
126 printf("Queue is %s\n", queue_empty(q) ? "empty" : "nonempty");
127 printf("Queue length = %d\n", queue_length(q));
128
129 while (queue_remove(q, &item) == 0)
130 {
131 printf("removing queue item: [%c].\n", item);
132 }
133
134 printf("Queue is %s\n", queue_empty(q) ? "empty" : "nonempty");
135 queue_finalize(q);
136
137 return 0;
138 }
鏈表實現：
1 #include <iostream>
2 using namespace std;
3
4 typedef char ItemType;
5
6 typedef struct NodeType
7 {
8 ItemType item;
9 struct NodeType* next;
10 } NodeType;
11
12 typedef NodeType* Node;
13
14 typedef struct
15 {
16 Node head;
17 Node tail;
18 int count;
19 } QueueType;
20
21 typedef QueueType* Queue;
22
23 int queue_initialize(Queue q)
24 {
25 q->head = 0;
26 q->tail = 0;
27 q->count = 0;
28 return 0;
29 }
30
31 int queue_remove(Queue q, ItemType* item)
32 {
33 Node oldHead = q->head;
34 if (q->count <= 0)
35 {
36 return -1;
37 }
38 *item = oldHead->item;
39 q->head = oldHead->next;
40 free(oldHead);
41 if (--q->count == 0)
42 {
43 q->tail = 0;
44 }
45 return 0;
46 }
47
48 void queue_finalize(Queue q)
49 {
50 ItemType item;
51 while (queue_remove(q, &item) >= 0);
52 }
53
54 int queue_empty(Queue q)
55 {
56 return q->count <= 0;
57 }
58
59 int queue_length(Queue q)
60 {
61 return q->count;
62 }
63
64 int queue_add(Queue q, ItemType item)
65 {
66 Node node = (Node)malloc(sizeof (NodeType));
67 if (node == 0)
68 {
69 return -1;
70 }
71
72 node->item = item;
73 node->next = 0;
74 if (q->tail != 0)
75 {
76 q->tail->next = node;
77 q->tail = node;
78 }
79 else
80 {
81 q->head = q->tail = node;
82 }
83 ++q->count;
84 return 0;
85 }
86
87 int queue_head(Queue q, ItemType* item)
88 {
89 if (q->count <= 0)
90 {
91 return -1;
92 }
93 *item = q->head->item;
94 return 0;
95 }
96
97 int main()
98 {
99 QueueType queue;
100 Queue q = &queue;
101 char item;
102 int i;
103
104 queue_initialize(q);
105 for (i = 0; i < 26; ++i)
106 {
107 queue_add(q, 'a' + i);
108 }
109
110 printf("Queue is %s\n", queue_empty(q) ? "empty" : "nonempty");
111 printf("Queue length = %d\n", queue_length(q));
112
113 while (queue_remove(q, &item) == 0)
114 {
115 printf("removing queue item: [%c].\n", item);
116 }
117
118 printf("Queue is %s\n", queue_empty(q) ? "empty" : "nonempty");
119 queue_finalize(q);
120
121 return 0;
122 }
posted on 2011-05-14 18:37
unixfy 閱讀(273)
評論(0) 編輯 收藏 引用