本文描述如何使用C语言实现一个队列的功能，展示如何使用数组、链表结构实现队列的方法。
1 队列的基本功能
队列的基本功能包括：创建队列、销毁队列、判断队列是否为空、进队列、出队列、获取队列中的元素个数、获取队列头部元素、获取队列尾部元素。
2 使用单链表实现队列
实现如下：
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
124
|
struct Node {
int val;
struct Node* next;
};
typedef struct Node Node;
typedef struct {
Node* head;
Node* tail;
int size;
} myQueue;
myQueue* initQueue(void) {
// init head
Node* node = (Node*)malloc(sizeof(Node));
if (!node) {
printf("Init que head node failed, not mem.\n");
return NULL;
}
node->val = -1;
node->next = NULL;
// init queue
myQueue* queue = (myQueue*)malloc(sizeof(myQueue));
if (!queue) {
printf("Init que failed, not mem.\n");
return NULL;
}
queue->head = node;
queue->tail = node;
queue->size = 0;
return queue;
}
void destroyLinklist(Node* head) {
while (head) {
Node* next = head->next;
free(head);
head = next;
}
}
void destroyQueue(myQueue* que) {
if (que) {
destroyLinklist(que->head);
que->size = 0;
free(que);
}
}
int isQueueEmpty(myQueue* que) {
return que->size == 0;
}
int getQueueSize(myQueue* que) {
return que->size;
}
void pushQueue(myQueue* que, int value) {
Node* node = (Node*)malloc(sizeof(Node));
if (!node) {
return;
}
node->val = value;
node->next = NULL;
que->tail->next = node;
que->tail = node;
++(que->size);
}
void popQueue(myQueue* que) {
if (isQueueEmpty(que)) {
return;
}
Node* cur = que->head->next;
que->head->next = cur->next;
if (que->tail == cur) {
que->tail = que->head;
}
free(cur);
--(que->size);
}
int getQueueFront(myQueue* que) {
if (isQueueEmpty(que)) {
return -1;
}
return que->head->next->val;
}
int getQueueTail(myQueue* que) {
if (isQueueEmpty(que)) {
return -1;
}
return que->tail->val;
}
void printQueue(myQueue* que) {
Node* head = que->head->next;
printf("que:");
while (head != que->tail) {
printf("[%d|-]->", head->val);
head = head->next;
}
printf("[%d|^].\n", que->tail->val);
}
void reverseQueue(myQueue* que) {
if (isQueueEmpty(que)) {
return;
}
Node* front = que->head->next;
if (front != que->tail) {
que->head->next = front->next;
front->next = NULL;
que->tail->next = front;
que->tail = front;
}
}
|
3 使用数组实现队列(环形队列)
实现如下：
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
|
#define QUE_LEN 100
typedef struct {
int arr[QUE_LEN];
int front;
int tail;
int size;
int capacity;
} myQueue;
myQueue* initQueue(void) {
// init queue
myQueue* queue = (myQueue*)malloc(sizeof(myQueue));
if (!queue) {
printf("Init que failed, not mem.\n");
return NULL;
}
queue->front = 0;
queue->tail = 0;
queue->size = 0;
queue->capacity = QUE_LEN;
return queue;
}
void destroyQueue(myQueue* que) {
if (que) {
que->size = 0;
free(que);
}
}
int isQueueEmpty(myQueue* que) {
return (que->size == 0 && que->front == que->tail);
}
int isQueueFull(myQueue* que) {
return (que->size == que->capacity && que->front == que->tail);
}
int getQueueSize(myQueue* que) {
return que->size;
}
void pushQueue(myQueue* que, int value) {
if (isQueueFull(que)) {
return;
}
int capacity = que->capacity;
int tail = que->tail;
que->arr[tail] = value;
que->tail = (tail + 1) % capacity;
++(que->size);
}
void popQueue(myQueue* que) {
if (isQueueEmpty(que)) {
return;
}
int front = que->front;
que->front = (front + 1) % que->capacity;
--(que->size);
}
int getQueueFront(myQueue* que) {
if (isQueueEmpty(que)) {
return -1;
}
int front = que->front;
return que->arr[front];
}
int getQueueTail(myQueue* que) {
if (isQueueEmpty(que)) {
return -1;
}
int tail = (que->tail + que->capacity - 1) % que->capacity;
return que->arr[tail];
}
void printQueue(myQueue* que) {
if (isQueueEmpty(que)) {
printf("que is empty().\n");
return;
}
printf("queue:");
for (int i = 0; i < que->size; ++i) {
int front = (que->front + i) % que->capacity;
printf("|%d", que->arr[front]);
}
printf("|.\n");
}
void reverseQueue(myQueue* que) {
if (isQueueEmpty(que)) {
return;
}
if (isQueueFull(que)) {
que->front = (que->front + 1) % que->capacity;
que->tail = (que->tail + 1)% que->capacity;
return;
}
int front = getQueueFront(que);
popQueue(que);
pushQueue(que, front);
}
|