_{C++基础教程}
——
作业及参考答案全部汇总文档
^{_节9队列和栈阶段作业}

最新版本V2.0
王道C++团队
COPYRIGHT ⓒ 2021-2024. 王道版权所有

基础题篇

_Gn!

下面都是一些基础的语法、概念编程练习题。

手动实现链式栈

_Gn!

基于以下头文件，手动实现一个链式栈：

xxxxxxxxxx
33
1
#ifndef LINKED_STACK_H
2
#define LINKED_STACK_H
3
#include <stdbool.h>
4
#include <stdio.h>
5
#include <stdlib.h>
6

7
typedef int ElementType;
8

9
// 栈的一个结点栈帧,类型定义
10
typedef struct node_s {
11
    ElementType data;
12
    struct node_s *next;
13
}StackFrame;    
14

15
typedef struct {
16
    StackFrame *top;    // 栈顶指针
17
}LinkedStack;
18

19
// 基本操作
20
// 创建链式栈
21
LinkedStack *stack_create();
22
// 销毁链式栈
23
void stack_destroy(LinkedStack *stack);
24
// 判空
25
bool is_empty(LinkedStack *stack);
26
// 入栈
27
void stack_push(LinkedStack *stack, ElementType data);
28
// 出栈并返回栈顶元素
29
ElementType stack_pop(LinkedStack *stack);
30
// 访问栈顶元素
31
ElementType stack_peek(LinkedStack *stack);
32

33
#endif // !LINKED_STACK_H

参考代码如下：

参考代码：

以下是实现源文件的代码，即所有函数的实现如下：

xxxxxxxxxx
60
1
#include "linked_stack.h"
2

3
// 新建一个空栈
4
LinkedStack *stack_create() {
5
    // callock可以不用手动初始化空指针
6
    return calloc(1, sizeof(LinkedStack));
7
}
8
// 对于链式栈而言，销毁栈就是销毁链表
9
void stack_destroy(LinkedStack *stack) {
10
    // 相当于遍历链表(出栈)然后在遍历中逐个free结点
11
    StackFrame *curr = stack->top;
12
    while (curr != NULL) {
13
        StackFrame *tmp = curr->next;   // 保存后继结点
14
        free(curr);
15
        curr = tmp;
16
    }
17
    // 最后free栈结构体
18
    free(stack);
19
}
20

21
bool is_empty(LinkedStack *stack) {
22
    return stack->top == NULL;
23
}
24

25
// 相当于链表头插法插入结点，栈顶指针相当于链表的头指针
26
void stack_push(LinkedStack *stack, ElementType data) {
27
    // 1.新建一个栈帧结点
28
    StackFrame *new_frame = malloc(sizeof(StackFrame));
29
    if (new_frame == NULL) {
30
        printf("malloc failed in stack_push.\n");
31
        exit(1);
32
    }
33
    // 2.初始化新栈帧
34
    new_frame->data = data;
35
    new_frame->next = stack->top;
36
    // 3.更新栈顶指针
37
    stack->top = new_frame;
38
}
39

40
// 相当于链表在头部删除第一个结点,栈顶指针相当于链表的头指针
41
ElementType stack_pop(LinkedStack *stack) {
42
    // 1.栈判空处理
43
    if (is_empty(stack)) {
44
        printf("error: stack is empty.\n");
45
        exit(1);
46
    }
47
    // 2.出栈返回栈顶元素,并free结点,更新栈顶指针
48
    StackFrame *curr = stack->top;
49
    ElementType data = curr->data;
50
    stack->top = curr->next;
51
    free(curr);
52
    return data;
53
}
54
ElementType stack_peek(LinkedStack *stack) {
55
    if (is_empty(stack)) {
56
        printf("error: stack is empty.\n");
57
        exit(1);
58
    }
59
    return stack->top->data;
60
}

测试用例代码如下：

xxxxxxxxxx
35
1
#define _CRT_SECURE_NO_WARNINGS
2
#include <stdio.h>
3
#include <stdlib.h>
4
#include <string.h>
5
#include "linked_stack.h"
6

7
int main(void) {
8
    // 创建一个空栈
9
    LinkedStack *stack = stack_create();
10
    if (stack == NULL) {
11
        printf("Failed to create stack.\n");
12
        return -1;
13
    }
14

15
    // 入栈操作
16
    stack_push(stack, 1);
17
    stack_push(stack, 2);
18
    stack_push(stack, 3);
19

20
    // 查看栈顶元素
21
    printf("当前栈顶元素是: %d\n", stack_peek(stack)); // 应该输出 3
22

23
    // 出栈操作，并打印出栈的元素
24
    printf("依次出栈以下元素:\n");
25
    while (!is_empty(stack)) {
26
        printf("%d\n", stack_pop(stack)); // 应该依次输出 3, 2, 1
27
    }
28

29
    // 再次尝试查看栈顶元素，预期会触发错误提示
30
    printf("栈为空时,尝试访问栈顶元素:\n");
31
    stack_peek(stack);  // 应该输出错误信息并退出
32

33
    // 销毁栈
34
    stack_destroy(stack);   return 0;
35
}

以上。

手动实现动态数组循环队列

_Gn!

基于以下动态数组队列的头文件定义，实现一个动态数组队列：

xxxxxxxxxx
35
1
#ifndef DYNAMIC_QUEUE_H
2
#define DYNAMIC_QUEUE_H
3

4
#include <stdbool.h>
5
#include <stdlib.h>
6
#include <stdio.h>
7

8
typedef int ElementType;    // 该队列当前存储int元素
9
#define DEFAULT_CAPACITY 10 // 数组队列的初始长度是10
10
#define THRESHOLD 1000  // 超过阈值每次扩容1.5倍扩，否则2倍的扩
11

12
// 定义队列结构体
13
typedef struct {
14
    ElementType *data;   // 动态数组存储队列元素
15
    int front;           // 标记队头元素的索引
16
    int rear;            // 标记队尾元素下一个位置的索引
17
    int size;            // 当前队列中元素数量
18
    int capacity;        // 队列容量
19
} DynamicQueue;
20

21
// 队列基本操作函数声明
22
// 创建动态数组队列
23
DynamicQueue *create_queue();
24
// 销毁动态数组队列
25
void destroy_queue(DynamicQueue *q);
26
// 判空
27
bool is_empty(DynamicQueue *q);
28
// 判满
29
bool is_full(DynamicQueue *q);
30
// 入队列
31
bool enqueue(DynamicQueue *q, ElementType data);
32
// 出队列并且返回队头元素
33
ElementType dequeue(DynamicQueue *q);
34

35
#endif // DYNAMIC_QUEUE_H

注意：你要实现一个循环队列，而不是一个普通队列。

参考代码如下：

参考代码：

以下是实现源文件的代码，即所有函数的实现如下：

xxxxxxxxxx
95
1
#include "dynamic_queue.h"
2

3
// 创建并初始化队列
4
DynamicQueue *create_queue() {
5
    DynamicQueue *q = calloc(1, sizeof(DynamicQueue));
6
    if (q == NULL) {
7
        printf("error: calloc failed in create_queue.\n");
8
        return NULL;
9
    }
10
    // front、rear、size自动初始化0值，无需再手动初始化了
11
    q->data = calloc(DEFAULT_CAPACITY, sizeof(ElementType));    // 使用calloc避免随机值
12
    if (q->data == NULL) {
13
        printf("error: calloc failed in create_queue.\n");
14
        free(q);
15
        return NULL;
16
    }
17
    q->capacity = DEFAULT_CAPACITY;
18
    return q;
19
}
20

21
// 销毁队列
22
void destroy_queue(DynamicQueue *q) {
23
    free(q->data);
24
    free(q);
25
}
26

27
// 检查队列是否为空
28
bool is_empty(DynamicQueue *q) {
29
    return q->size == 0;
30
}
31

32
// 检查队列是否已满
33
bool is_full(DynamicQueue *q) {
34
    return q->size == q->capacity;
35
}
36

37
/*
38
    这里采用一种简单粗暴的扩容手段:
39
    直接分配新容量的内存块
40
    然后遍历旧内存块中的队列元素,将这些元素全部从头开始复制到新内存块中
41
    这样的操作在完成后,需要更新front索引和rear索引
42
*/
43
static bool resize_queue(DynamicQueue *q) {
44
    int old_capacity = q->capacity;
45
    int new_capacity = (old_capacity < THRESHOLD) ?
46
        (old_capacity << 1) :
47
    (old_capacity + (old_capacity >> 1));
48

49
    // 重新分配一个新的,更长的动态数组
50
    ElementType *new_data = malloc(new_capacity * sizeof(ElementType));
51
    if (new_data == NULL) {
52
        printf("error: realloc failed in resize_queue.\n");
53
        return false;
54
    }
55

56
    int curr = q->front;    // curr索引用于遍历整个队列中的元素
57
    int index = 0;
58
    while (index < q->size) {
59
        new_data[index] = q->data[curr];
60
        curr = (curr + 1) % q->capacity;
61
        index++;
62
    } // while循环结束时,new_data就从头开始包含了队列的所有元素 
63
    free(q->data);
64
    q->data = new_data;
65
    q->front = 0;
66
    q->rear = q->size;
67
    q->capacity = new_capacity;
68
    return true;
69
}
70

71
// 入队操作
72
bool enqueue(DynamicQueue *q, ElementType data) {
73
    if (is_full(q)) {
74
        if (!resize_queue(q)) {
75
            printf("error: 扩容失败.\n");
76
            return false; // 队列扩容失败,入队也同步失败
77
        }
78
    }
79
    q->data[q->rear] = data;
80
    q->rear = (q->rear + 1) % q->capacity;  // 循环队列
81
    q->size++;
82
    return true;
83
}
84

85
// 出队操作
86
ElementType dequeue(DynamicQueue *q) {
87
    if (is_empty(q)) {
88
        printf("error: 队列为空，无法出队。\n");
89
        exit(1);
90
    }
91
    ElementType item = q->data[q->front];
92
    q->front = (q->front + 1) % q->capacity; // 循环队列
93
    q->size--;
94
    return item;
95
}

测试用例代码：

xxxxxxxxxx
35
1
#include "dynamic_queue.h"
2
#include <stdio.h>
3

4
int main(void) {
5
    // 创建队列
6
    DynamicQueue *queue = create_queue();
7
    if (queue == NULL) {
8
        printf("创建队列失败。\n");
9
        return 1;
10
    }
11

12
    // 入队测试
13
    for (int i = 0; i < 15; i++) {
14
        if (enqueue(queue, i)) {
15
            printf("已入队: %d\n", i);
16
        }
17
        else {
18
            printf("入队失败: %d\n", i);
19
        }
20
    }
21

22
    // 打印队列容量和大小
23
    printf("队列容量: %d, 队列大小: %d\n", queue->capacity, queue->size);
24

25
    // 出队测试
26
    printf("正在出队...\n");
27
    while (!is_empty(queue)) {
28
        printf("已出队: %d\n", dequeue(queue));
29
    }
30

31
    // 销毁队列
32
    destroy_queue(queue);
33

34
    return 0;
35
}

以上。

栈的应用：括号匹配问题

_Gn!

在上述已实现的一个链式栈（数组栈也行）的基础上，编写代码完成字符串括号的匹配校验。

括号都是英文字符括号，而且有三类：{}、[]、()

注：

1.若字符串中没有括号，也算做括号匹配成功。

2.思路可以参考文档《栈》

参考代码如下：

参考代码如下：

首先是链式栈的头文件，该文件中需要修改栈中元素的类型为char类型：

x
1
#ifndef LINKED_STACK_H
2
#define LINKED_STACK_H
3
#include <stdbool.h>
4
#include <stdio.h>
5
#include <stdlib.h>
6

7
// 由于栈中要存储字符，所以元素类型要改成char类型
8
typedef char ElementType;
9

10
// 栈的一个结点栈帧,类型定义
11
typedef struct node_s {
12
    ElementType data;
13
    struct node_s *next;
14
}StackFrame;
15

16
typedef struct {
17
    StackFrame *top;    // 栈顶指针
18
}LinkedStack;
19

20
// 基本操作
21
// 创建链式栈
22
LinkedStack *stack_create();
23
// 销毁链式栈
24
void stack_destroy(LinkedStack *stack);
25
// 判空
26
bool is_empty(LinkedStack *stack);
27
// 入栈
28
void stack_push(LinkedStack *stack, ElementType data);
29
// 出栈并返回栈顶元素
30
ElementType stack_pop(LinkedStack *stack);
31
// 访问栈顶元素
32
ElementType stack_peek(LinkedStack *stack);
33

34
#endif // !LINKED_STACK_H

链式栈的实现代码：

x
1
#include "linked_stack.h"
2

3
// 新建一个空栈
4
LinkedStack *stack_create() {
5
    // callock可以不用手动初始化空指针
6
    return calloc(1, sizeof(LinkedStack));
7
}
8
// 对于链式栈而言，销毁栈就是销毁链表
9
void stack_destroy(LinkedStack *stack) {
10
    // 相当于遍历链表(出栈)然后在遍历中逐个free结点
11
    StackFrame *curr = stack->top;
12
    while (curr != NULL) {
13
        StackFrame *tmp = curr->next;   // 保存后继结点
14
        free(curr);
15
        curr = tmp;
16
    }
17
    // 最后free栈结构体
18
    free(stack);
19
}
20

21
bool is_empty(LinkedStack *stack) {
22
    return stack->top == NULL;
23
}
24

25
// 相当于链表头插法插入结点，栈顶指针相当于链表的头指针
26
void stack_push(LinkedStack *stack, ElementType data) {
27
    // 1.新建一个栈帧结点
28
    StackFrame *new_frame = malloc(sizeof(StackFrame));
29
    if (new_frame == NULL) {
30
        printf("malloc failed in stack_push.\n");
31
        exit(1);
32
    }
33
    // 2.初始化新栈帧
34
    new_frame->data = data;
35
    new_frame->next = stack->top;
36
    // 3.更新栈顶指针
37
    stack->top = new_frame;
38
}
39

40
// 相当于链表在头部删除第一个结点,栈顶指针相当于链表的头指针
41
ElementType stack_pop(LinkedStack *stack) {
42
    // 1.栈判空处理
43
    if (is_empty(stack)) {
44
        printf("error: stack is empty.\n");
45
        exit(1);
46
    }
47
    // 2.出栈返回栈顶元素,并free结点,更新栈顶指针
48
    StackFrame *curr = stack->top;
49
    ElementType data = curr->data;
50
    stack->top = curr->next;
51
    free(curr);
52
    return data;
53
}
54
ElementType stack_peek(LinkedStack *stack) {
55
    if (is_empty(stack)) {
56
        printf("error: stack is empty.\n");
57
        exit(1);
58
    }
59
    return stack->top->data;
60
}

括号匹配函数以及相关的测试代码：

x
1
#define _CRT_SECURE_NO_WARNINGS
2
#include <stdio.h>
3
#include <stdlib.h>
4
#include <ctype.h>
5
#include <stdbool.h>
6
#include "linked_stack.h"   // 已实现的链式栈
7

8
char get_right_bracket(char ch) {
9
    switch (ch) {
10
        case '{': return '}';
11
        case '[': return ']';
12
        case '(': return ')';
13
        default: return 0;
14
    }
15
}
16
bool is_left_bracket(char ch) {
17
    return ch == '{'
18
        || ch == '['
19
        || ch == '(';
20
}
21

22
bool is_right_bracket(char ch) {
23
    return ch == '}'
24
        || ch == ']'
25
        || ch == ')';
26
}
27

28
bool is_matching(char *str, LinkedStack *stack) {
29
    while (*str) {
30
        // 排除非括号字符
31
        if (is_left_bracket(*str)) {
32
            // 字符是左括号,于是将它对应的右括号入栈
33
            char right_bracket = get_right_bracket(*str);
34
            stack_push(stack, right_bracket);
35
        }
36
        if (is_right_bracket(*str)) {
37
            // 如果遇到右括号时栈为空,说明右括号在前面,匹配失败
38
            // 如果栈不为空就出栈,和当前字符比较,如果不一致就匹配失败
39
            if (is_empty(stack) || stack_pop(stack) != *str) {
40
                return false;
41
            }
42
        }
43
        str++;
44
    }
45
    // 字符串遍历完成,判断栈是否空
46
    return is_empty(stack);
47
}
48

49
int main(void) {
50
    LinkedStack *stack = stack_create();
51
    char *str = "1()23{[}";
52
    if (is_matching(str, stack)) {
53
        printf("匹配成功!\n");
54
    }
55
    else {
56
        printf("匹配失败!\n");
57
    }
58
    stack_destroy(stack);
59
    return 0;
60
}

以上。

扩展题篇

_Gn!

以下题目都属于扩展题。

扩展：手动实现动态数组栈

_Gn!

基于以下头文件，手动实现一个动态数组栈：

x
1
#ifndef DYNAMIC_STACK_H
2
#define DYNAMIC_STACK_H
3
#include <stdio.h>
4
#include <stdlib.h>
5
#include <stdbool.h>
6

7
typedef int ElementType;
8

9
typedef struct {
10
    ElementType *elements;   // 指向动态数组首元素的指针
11
    int size;   // 元素的个数
12
    int capacity; // 数组的容量，也就是栈的容量
13
} DynamicStack;
14

15
// 创建动态数组栈
16
DynamicStack *stack_create();
17
// 销毁动态数组栈
18
void stack_destroy(DynamicStack *s);
19
// 入栈
20
void stack_push(DynamicStack *s, ElementType val);
21
// 出栈并返回栈顶元素
22
ElementType stack_pop(DynamicStack *s);
23
// 访问栈顶元素
24
ElementType  stack_peek(DynamicStack *s);
25
// 判空
26
bool is_empty(DynamicStack *s);
27

28
#endif // !DYNAMIC_ARR_STACK_H

当栈中元素已满时，就需要扩容此数组，扩容策略可以自行拟定。

参考代码如下：

参考代码实现如下：

以下是实现源文件的代码，即所有函数的实现如下：

x
1
#include "dynamic_stack.h"
2
#define DEFAULT_CAPACITY 8  // 动态栈的默认容量
3
#define THRESHOLD 1024  // 扩容阈值
4

5
// 实现扩容机制
6
static void grow_capacity(DynamicStack *s) {
7
    // 扩容策略: 超过阈值则1.5倍的扩容，否则2倍的扩容
8
    int new_capacity = (s->capacity >= THRESHOLD) ?
9
        (s->capacity + (s->capacity >> 1)) :
10
    (s->capacity << 1);
11

12
    // 使用realloc函数实现扩容，重新分配内存
13
    ElementType *new_arr = realloc(s->elements, new_capacity * sizeof(ElementType));
14
    if (new_arr == NULL) {
15
        printf("Error: realloc failed in grow_capacity\n");
16
        exit(1);
17
    }
18
    // 更新动态数组栈结构体的信息
19
    s->elements = new_arr;
20
    s->capacity = new_capacity;
21
}
22
// 创建一个动态数组栈
23
DynamicStack *stack_create() {
24
    DynamicStack *s = malloc(sizeof(DynamicStack));
25
    if (s == NULL) {
26
        printf("malloc failed in stack_create.\n");
27
        return NULL;
28
    }
29
    // 初始化动态数组  
30
    s->size = 0;
31
    s->capacity = DEFAULT_CAPACITY;
32
    s->elements = malloc(DEFAULT_CAPACITY * sizeof(ElementType));
33
    if (s->elements == NULL) {
34
        free(s);
35
        printf("malloc failed in stack_create.\n");
36
        return NULL;
37
    }
38
    return s;
39
}
40
// 销毁一个栈
41
void stack_destroy(DynamicStack *s) {
42
    // 先释放动态数组
43
    free(s->elements);
44
    // 再释放栈结构体
45
    free(s);
46
}
47

48
// 将数组末尾视为栈顶，将size属性作为新插入结点的下标，这就是入栈
49
void stack_push(DynamicStack *s, ElementType val) {
50
    if (s->capacity == s->size) {
51
        // 栈满了,需要扩容
52
        grow_capacity(s);
53
    }
54

55
    // 可以直接把size作为入栈出栈的操作索引
56
    s->elements[s->size] = val;
57
    s->size++;
58
    // 上面的两行代码可以合并成一行
59
    // s->elements[s->size++] = val;
60
}
61

62
// 将数组末尾视为栈顶，将size属性减1，这就是出栈。元素取值并不用改变
63
ElementType stack_pop(DynamicStack *s) {
64
    if (is_empty(s)) {
65
        printf("Error: stack is empty\n");
66
        exit(1);
67
    }
68
    s->size--;
69
    return s->elements[s->size];
70

71
    // 上面的两行代码可以合并成一行
72
    // return s->elements[--(s->size)];
73
}
74
// 访问栈顶元素
75
ElementType stack_peek(DynamicStack *s) {
76
    if (is_empty(s)) {
77
        printf("Error: stack is empty\n");
78
        exit(1);
79
    }
80
    return s->elements[s->size - 1];
81
}
82
// 判空
83
bool is_empty(DynamicStack *s) {
84
    return s->size == 0;
85
}

测试用例代码如下：

xxxxxxxxxx
22
1
#include "dynamic_stack.h"
2

3
int main(void) {
4
    DynamicStack *s = stack_create();
5
    // 入队列1000个元素
6
    for (int i = 0; i < 1000; i++) {
7
        stack_push(s, i);
8
    }
9
    // 出队列直到队列为空
10
    while (!is_empty(s)) {
11
        ElementType ele = stack_peek(s);
12
        printf("%d ", ele); // 预期会将999-0倒着输出打印
13
        stack_pop(s);
14
    }
15
    printf("\n");
16
    // 再次尝试出栈, 此时会打印错误提示信息
17
    stack_pop(s);
18
    // 销毁队列
19
    stack_destroy(s);
20

21
    return 0;
22
}

以上。

扩展：手动实现链式队列

_Gn!

基于以下头文件，手动实现一个链式队列：

xxxxxxxxxx
37
1
#ifndef LIST_QUEUE_H
2
#define LIST_QUEUE_H
3

4
#include <stdbool.h>
5
#include <stdio.h>
6
#include <stdlib.h>
7

8
// 定义队列中的元素类型
9
typedef int ElementType;
10

11
// 队列节点的结构
12
typedef struct node_s {
13
    ElementType data;
14
    struct node_s *next;
15
} QueueNode;
16

17
// 队列的结构
18
typedef struct {
19
    QueueNode *front;  // 队头结点指针
20
    QueueNode *rear;   // 队尾结点指针
21
} LinkedListQueue;
22

23
// 函数声明
24
// 创建链式队列
25
LinkedListQueue *create_queue();
26
// 销毁链式队列
27
void destroy_queue(LinkedListQueue *q);
28
// 入队列
29
bool enqueue(LinkedListQueue *q, ElementType element);
30
// 出队列并返回队头元素
31
ElementType dequeue(LinkedListQueue *q);
32
// 访问队头元素
33
ElementType peek_queue(LinkedListQueue *q);
34
// 判空
35
bool is_empty(LinkedListQueue *q);
36

37
#endif // !LIST_QUEUE_H

注意：链式队列显然不具有满的概念，所以也不需要执行判满操作。

参考代码如下：

参考代码实现如下：

以下是实现源文件的代码，即所有函数的实现如下：

xxxxxxxxxx
82
1
#include "list_queue.h"
2

3
// 函数声明
4
LinkedListQueue *create_queue() {
5
    return calloc(1, sizeof(LinkedListQueue));
6
}
7

8
void destroy_queue(LinkedListQueue *q) {
9
    // 从队头开始遍历链表，销毁每一个结点
10
    QueueNode *current = q->front;
11
    while (current != NULL) {
12
        QueueNode *temp = current->next;
13
        free(current);
14
        current = temp;
15
    }
16
    // 销毁队列结构体
17
    free(q);
18
}
19

20
bool is_empty(LinkedListQueue *q) {
21
    // 队头指针是空指针，即表示空队列
22
    return q->front == NULL;
23
}
24

25
// 入队操作: 只能在队尾插入一个结点
26
// 由于已存在尾指针，所以这里的操作就是链表尾插
27
bool enqueue(LinkedListQueue *q, ElementType element) {
28
    QueueNode *new_node = malloc(sizeof(QueueNode));
29
    if (new_node == NULL) {
30
        printf("Error: malloc failed in enqueue.\n");
31
        return false;
32
    }
33
    // 初始化新结点
34
    new_node->data = element;
35
    new_node->next = NULL;
36

37
    // 开始进行尾插法插入一个结点
38
    // 分两种情况：如果尾插插入的是第一个结点需要同步更新头指针，否则仅需要更新尾指针
39
    if (q->front == NULL) {
40
        // 插入的是第一个结点
41
        q->front = new_node;
42
        q->rear = new_node;
43
    }
44
    else {
45
        // 插入的不是第一个结点
46
        q->rear->next = new_node;
47
        q->rear = new_node;
48
    }
49
    return true;
50
}
51

52
// 出队，在队头删除一个结点。也就是在删除链表的第一个结点
53
ElementType dequeue(LinkedListQueue *q) {
54
    if (is_empty(q)) {
55
        printf("Error: queue is empty.\n");
56
        exit(1);
57
    }
58

59
    QueueNode *tmp = q->front;
60
    // 将出队的结点数据保存
61
    ElementType remove_data = tmp->data;
62

63
    // 更新队头指针
64
    q->front = tmp->next;
65
    if (q->front == NULL) {
66
        // 如果队头更新后,队列为空,说明出队的就是最后一个元素
67
        // 于是同步更新队尾指针
68
        q->rear = NULL;
69
    }
70

71
    free(tmp);
72
    return remove_data;
73
}
74

75
// 访问队头元素但不出队
76
ElementType peek_queue(LinkedListQueue *q) {
77
    if (is_empty(q)) {
78
        printf("Error: queue is empty.\n");
79
        exit(1);
80
    }
81
    return q->front->data;
82
}

测试用例代码如下：

xxxxxxxxxx
22
1
#define _CRT_SECURE_NO_WARNINGS
2
#include "list_queue.h"
3
#include <stdio.h>
4

5
int main(void) {
6
    LinkedListQueue *q = create_queue();
7
    // 逐一入队列
8
    enqueue(q, 1);
9
    enqueue(q, 2);
10
    enqueue(q, 3);
11
    enqueue(q, 4);
12
    enqueue(q, 5);
13
    enqueue(q, 6);
14
    // 先进先出，出队列全部元素直到队列为空
15
    while (!is_empty(q)) {
16
        int val = peek_queue(q);
17
        printf("%d ", val); // 预期出队列顺序:1 2 3 4 5 6
18
        dequeue(q);
19
    }
20
    printf("\n");
21
    return 0;
22
}

以上。

The End