-
第2章 数据结构中栈与队列的概念
文档配套视频讲解链接地址
- 腾讯课堂视频链接地址 : 14_栈与队列_顺序栈
- 腾讯课堂视频链接地址 : 15_栈与队列_链式栈
- 腾讯课堂视频链接地址 : 16_栈与队列_循环队列
- 腾讯课堂视频链接地址 : 17_栈与队列_链式队列
- 腾讯课堂视频链接地址 : 18_栈与队列_顺序双栈一队列
- 腾讯课堂视频链接地址 : 19_栈与队列_顺序双队列一栈
- 腾讯课堂视频链接地址 : 20_栈与队列_链式双栈一队列
- 腾讯课堂视频链接地址 : 21_栈与队列_链式双栈一队列
第02 章 栈与队列
2.1 栈与队列的框图
2.2 栈
1. 栈的概念
栈是限制在一端进行插入操作和删除操作的线性表（俗称堆栈），允许进行操作的一端称为“栈顶”，另一固定端称为“栈底”，当栈中没有元素时称为“空栈”。
- 特点 ：后进先出（LIFO）Last In First Out
- 类比事物 , 弹夹
2. 顺序栈
- 它是顺序表的一种，具有顺序表同样的存储结构，由数组定义，配合用数组下标表示的栈顶指针top（相对指针）完成各种操作。
3. 实例11 顺序栈
- 源文件
04-ds/11-seqstack.c- 1
- 源代码
#include#include #include #include // sequeue stack #define N 32 typedef struct { int data[N]; // 数组的空间 int index ; // 是数组下标的索引 }seqstack_t; seqstack_t * create_empty_seqstack() { seqstack_t * s = (seqstack_t *)malloc(sizeof(seqstack_t)); memset(s->data,0,sizeof(s->data)) ; // 把数组中的内容清为0 s->index = -1 ; // 表示栈为空 return s ; } int seqstack_is_empty(seqstack_t * s) { return (s->index == -1 ); } int seqstack_is_full(seqstack_t *s) { return (s->index == N-1) ; } // 入栈 , 压栈 int seqstack_push(seqstack_t *s, int value) { if(seqstack_is_full(s)) { printf("栈已满"); return -1 ; } s->index ++ ; s->data[s->index] = value ; return 0 ; } int seqstack_pop(seqstack_t * s, int *pvalue) { if(seqstack_is_empty(s)) { printf("栈已空"); return -1 ; } *pvalue = s->data[s->index] ; s->index -- ; return 0 ; } int main(int argc, char const *argv[]) { seqstack_t * S = create_empty_seqstack(); printf("入栈顺序:"); for(int i=0;i<33;i++) { printf("%d ",i+1); seqstack_push(S,i+1); } printf("\n"); printf("出栈顺序:"); for(int i=0,value;i<33;i++) { seqstack_pop(S,&value); printf("%d ",value); } printf("\n"); return 0; } - 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
- 运行结果
入栈顺序: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 栈已满 出栈顺序:32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 栈已空1- 1
- 2
4. 实例12 链式栈
- 源文件
04-ds/12-linkstack.c- 1
- 源代码
#include#include #include #include // link stack typedef struct node { int data; struct node *next; } linklist_t; linklist_t *create_empty_linkstack() { linklist_t *s = (linklist_t *)malloc(sizeof(linklist_t)); s->data = 0; s->next = NULL; return s; } // 链表没有满 , 有空的概念 int linkstack_is_empty(linklist_t *s) { return (s->next == NULL); } // 头部插入法 int linkstack_push(linklist_t *s, int value) { linklist_t *p = (linklist_t *)malloc(sizeof(linklist_t)); p->data = value; p->next = s->next; s->next = p; return 0; } // 头部删除法 int linkstack_pop(linklist_t *s, int *pvalue) { linklist_t *p = s->next; // p 指向s的下一个节点 if(linkstack_is_empty(s)) { printf("栈已空"); return -1 ; } // s->next 不为空 s->next = p->next; // 接链表 *pvalue = p->data ; // 读取数据 free(p); return 0; } int main(int argc, char const *argv[]) { linklist_t *S = create_empty_linkstack(); printf("入栈顺序:"); for(int i=0;i<33;i++) { if( linkstack_push(S,i+1) == 0 ) // 表示成功 { printf("%d ",i+1); } } printf("\n"); printf("出栈顺序:"); for(int i=0,value;i<34;i++) { if(linkstack_pop(S,&value) == 0 ) { printf("%d ",value); } } printf("\n"); return 0; } - 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
- 运行结果
入栈顺序: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 出栈顺序:33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 栈已空- 1
- 2
2.3 队列
1. 队列的概念
- 队列是限制在两端进行插入操作和删除操作的线性表，允许进行存入操作的一端称为“队尾”，允许进行删除操作的一端称为“队头”。当线性表中没有元素时，称为“空队”。
- 特点 ：先进先出（FIFO） First In First Out 。
2. 顺序队列
- 它是顺序表的一种，具有顺序表同样的储存结构，由数组定义，配合用数组下标表示的队头指针和队尾指针完成各种操作。
3. 实例13 顺序队列
- 源文件
04-ds/13-sequeue.c- 1
- 源代码
#include#include #include // sequence queue #define N 32 typedef struct { int data[N]; int front; // 队列的头 , 数组的下标 int rear; // 队列的尾 , 数组的下标 } sequeue_t; // 空队列的概念是 : 队头等于队尾 // 为了区分空队 和满队 , 队列元素个数要比数组元素少一个 // 满队+1 等于空队 // 1 2 3 4 5 // f f // r sequeue_t *create_empty_sequeue() { sequeue_t *q = (sequeue_t *)malloc(sizeof(sequeue_t)); memset(q->data, 0, sizeof(q->data)); q->front = q->rear = N - 1; //指向数组最后一个元素 return q; } int sequeue_is_empty(sequeue_t *q) { return (q->front == q->rear); } int sequeue_is_full(sequeue_t *q) { // 队尾 +1 == 队头 , 就是满队 // 任何一个一个数对N求余 , 这个数的范围是 0 - N-1 return ((q->rear + 1) % N == q->front); } int sequeue_enqueue(sequeue_t *q, int value) { if (sequeue_is_full(q)) { printf("队列已满"); return -1; } q->rear = (q->rear + 1) % N; // 防止数组越界 q->data[q->rear] = value; return 0; } int sequeue_dequeue(sequeue_t *q, int *pvalue) { if (sequeue_is_empty(q)) { printf("队列已空"); return -1; } q->front = (q->front + 1) % N; // 防止数组越界 *pvalue = q->data[q->front]; return 0; } int main(int argc, char const *argv[]) { sequeue_t *Q = create_empty_sequeue(); // 这个队列, 最多可以存放 31 个元素 printf("入队顺序为:"); for (int i = 0; i < 32; i++) { if (sequeue_enqueue(Q, i + 1) == 0) { printf("%d ", i + 1); } } printf("\n"); printf("出队顺序为:"); for (int i = 0,value; i < 32; i++) { if (sequeue_dequeue(Q, &value) == 0) { printf("%d ", value); } } printf("\n"); return 0; } - 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
- 运行结果
入队顺序为: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 队列已满 出队顺序为: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 队列已空- 1
- 2
4. 链式队列
链式队列的尾部插入
5. 实例14 链式队列
- 源文件
04-ds/14-linkqueue.c- 1
- 源代码
#include#include #include // sequence queue typedef struct node { int data; struct node *next; } linklist_t; typedef struct { linklist_t *front; // 队头 linklist_t *rear; // 队尾 } linkqueue_t; // 空队列的概念是 : 队头等于队尾 // 为了区分空队 和满队 , 队列元素个数要比数组元素少一个 // 满队+1 等于空队 // 1 2 3 4 5 // f f // r linkqueue_t *create_empty_linkqueue() { linklist_t *h = (linklist_t *)malloc(sizeof(linklist_t)); linkqueue_t *q = (linkqueue_t *)malloc(sizeof(linkqueue_t)); q->front = q->rear = h; q->front->data = 0; return q; } int linkqueue_is_empty(linkqueue_t *q) { return (q->front == q->rear); } // 链式队列没有满的概念 // int linkqueue_is_full(linkqueue_t *q) // { // } // 入队 队尾加 int linkqueue_enqueue(linkqueue_t *q, int value) { linklist_t *p = (linklist_t *)malloc(sizeof(linklist_t)); p->data = value; p->next = q->rear->next; // 尾部插入第1步 q->rear->next = p; // 尾部插入第2步 q->rear = p; // 尾部插入第3步 return 0; } // 头部出队列 , 头部删除法 int linkqueue_dequeue(linkqueue_t *q, int *pvalue) { linklist_t *p; if (linkqueue_is_empty(q)) { printf("队列为空"); return -1; } p = q->front->next; // 头节点的下一个节点 , p是要删除的节点 q->front->next = p->next; // 接上链表 if (q->front->next == NULL) // 此时队列为空 q->rear = q->front; // *pvalue = p->data; free(p); return 0; } int main(int argc, char const *argv[]) { linkqueue_t *Q = create_empty_linkqueue(); // 这个队列, 最多可以存放 31 个元素 printf("入队顺序为:"); for (int i = 0; i < 32; i++) { if (linkqueue_enqueue(Q, i + 1) == 0) { printf("%d ", i + 1); } } printf("\n"); printf("出队顺序为:"); for (int i = 0, value; i < 33; i++) { if (linkqueue_dequeue(Q, &value) == 0) { printf("%d ", value); } } printf("\n"); return 0; } - 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
- 运行结果
入队顺序为: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 出队顺序为: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 队列为空- 1
- 2
2.4 实例15 球钟问题
-
队列与栈应用
-
问题描述：球钟是一个利用球的移动来记录时间的简单装置。它有三个可以容纳若干个球的指示器：分钟指示器，五分钟指示器，小时指示器。若分钟指示器中有2个球，五分钟指示器中有6个球，小时指示器中有5个球，则时间为5:32
-
工作原理：每过一分钟，球钟就会从球队列的队首取出一个球放入分钟指示器，分钟指示器最多可容纳4个球。当放入第五个球时，在分钟指示器的4个球就会按照他们被放入时的相反顺序加入球队列的队尾。而第五个球就会进入五分钟指示器。按此类推，五分钟指示器最多可放11个球，小时指示器最多可放11个球。
-
当小时指示器放入第12个球时，原来的11个球按照他们被放入时的相反顺序加入球队列的队尾，然后第12个球也回到队尾。这时，三个指示器均为空，回到初始状态，从而形成一个循环。因此，该球钟表示时间的范围是从0：00到11：59。
现设初始时球队列的球数为27，球钟的三个指示器初态均为空。问，要经过多久，球队列才能回复到原来的顺序?
Q : 是队列, 队列可以存放27个球
S1: 是栈, 1分钟指示器, 里面可以存放5个球
S5 : 是栈, 表示的5分钟的指示器, 里面可以存放12个球
S60: 是栈, 表示小时指示器, 里面可以存放12个球
-
源文件
04-ds/15-ballclock.c- 1
- 源代码
#include#include #include // sequence queue #define N 128 typedef struct { int data[N]; int front; // 队列的头 , 数组的下标 int rear; // 队列的尾 , 数组的下标 } sequeue_t; // 空队列的概念是 : 队头等于队尾 // 为了区分空队 和满队 , 队列元素个数要比数组元素少一个 // 满队+1 等于空队 // 1 2 3 4 5 // f f // r sequeue_t *create_empty_sequeue() { sequeue_t *q = (sequeue_t *)malloc(sizeof(sequeue_t)); memset(q->data, 0, sizeof(q->data)); q->front = q->rear = N - 1; //指向数组最后一个元素 return q; } int sequeue_is_empty(sequeue_t *q) { return (q->front == q->rear); } int sequeue_is_full(sequeue_t *q) { // 队尾 +1 == 队头 , 就是满队 // 任何一个一个数对N求余 , 这个数的范围是 0 - N-1 return ((q->rear + 1) % N == q->front); } int sequeue_is_size(sequeue_t *q) { // 队尾减去队头就是元素的个数 if (q->rear >= q->front) // return (q->rear - q->front); else return (N - q->front + q->rear); } int sequeue_enqueue(sequeue_t *q, int value) { if (sequeue_is_full(q)) { printf("队列已满"); return -1; } q->rear = (q->rear + 1) % N; // 防止数组越界 q->data[q->rear] = value; return 0; } int sequeue_dequeue(sequeue_t *q, int *pvalue) { if (sequeue_is_empty(q)) { printf("队列已空"); return -1; } q->front = (q->front + 1) % N; // 防止数组越界 *pvalue = q->data[q->front]; return 0; } // sequeue stack typedef struct { int data[N]; // 数组的空间 int index; // 是数组下标的索引 } seqstack_t; seqstack_t *create_empty_seqstack() { seqstack_t *s = (seqstack_t *)malloc(sizeof(seqstack_t)); memset(s->data, 0, sizeof(s->data)); // 把数组中的内容清为0 s->index = -1; // 表示栈为空 return s; } int seqstack_is_empty(seqstack_t *s) { return (s->index == -1); } int seqstack_is_full(seqstack_t *s) { return (s->index == N - 1); } int seqstack_is_size(seqstack_t *s) { return (s->index+1); } // 入栈 , 压栈 int seqstack_push(seqstack_t *s, int value) { if (seqstack_is_full(s)) { printf("栈已满"); return -1; } s->index++; s->data[s->index] = value; return 0; } int seqstack_pop(seqstack_t *s, int *pvalue) { if (seqstack_is_empty(s)) { printf("栈已空"); return -1; } *pvalue = s->data[s->index]; s->index--; return 0; } // 检查队列是否是 是否是1,2,3...27 这个顺序 // 是这个顺序 返回真 // 不是这个顺序 返回假 int check_sequeue(sequeue_t * q) { for(int i=1;i<27;i++) { // 正常顺序 1,2,3,4,...27 if(q->data[(q->front+i)%N] > q->data[(q->front+i+1)%N] ) { return 0; // 这个顺序不对 } } return 1; // 所有顺序都对 , 返回真 } int main(int argc, char const *argv[]) { sequeue_t *Q = create_empty_sequeue(); // 创建一个空队列 // 往队列中装入27个元素 for (int i = 0; i < 27; i++) { sequeue_enqueue(Q, i + 1); } seqstack_t *S1 = create_empty_seqstack(); // S1 分钟指示器 seqstack_t *S5 = create_empty_seqstack(); // S5 5分钟指示器 seqstack_t *S60 = create_empty_seqstack(); // S60 5小时指示器 int count =0 ; // 用来记录工作的分钟数 int value = 0 ,t12; while(1) { count ++ ; // 计算累计时间的 sequeue_dequeue(Q,&value) ; // 从球队列中取出一个球 seqstack_push(S1,value); // 放入分钟指示器中 /*************************************************************/ // 分钟指示器的工作原理 if(seqstack_is_size(S1) < 5) continue; seqstack_pop(S1,&value); // 第五个球就会进入五分钟指示器 seqstack_push(S5,value); //在分钟指示器的4个球就会按照他们被放入时的相反顺序加入球队列的队尾 for(int i=0;i<4;i++) { seqstack_pop(S1,&value); sequeue_enqueue(Q,value); } /*************************************************************/ // 5分钟指示器的工作原理 if(seqstack_is_size(S5) < 12) continue; seqstack_pop(S5,&value); // 第12个球就会进入小时指示器 seqstack_push(S60,value); //在5分钟指示器的11个球就会按照他们被放入时的相反顺序加入球队列的队尾 for(int i=0;i<11;i++) { seqstack_pop(S5,&value); sequeue_enqueue(Q,value); } /*************************************************************/ // 小时指示器的工作原理 if(seqstack_is_size(S60) < 12) continue; seqstack_pop(S60,&t12); // 第12个球拿出来 //小时指示器的11个球就会按照他们被放入时的相反顺序加入球队列的队尾 for(int i=0;i<11;i++) { seqstack_pop(S60,&value); sequeue_enqueue(Q,value); } sequeue_enqueue(Q,t12); // 然后第12个球也回到队尾 /*************************************************************/ // 结束条件 if(check_sequeue(Q)) // 为真, 返回 , 为假继续循环 { break; } else { continue; } } // 33120 是标准答案 printf("count = %d\n",count); return 0; } - 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
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
- 205
- 206
- 207
- 208
- 209
- 210
- 211
- 212
- 213
- 214
- 215
- 216
- 217
- 218
- 219
- 220
- 221
- 222
- 223
- 224
- 运行结果
count = 33120- 1
2.5 队列与栈的转换
1. 实例16 顺序的双栈实现一个队列
- 使用双栈实现一个队列
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QpQ8IKRT-1668935067808)(https://gitee.com/embmaker/cloudimage/raw/master/img/%E5%8F%8C%E6%A0%88%E5%AE%9E%E7%8E%B0%E4%B8%80%E9%98%9F%E5%88%97.jpg)]
-
使用顺序的栈实现一个顺序的队列
- 第1步:入栈s1中, 入栈1,2,3,4
- 第2步:把s1中的元素全部出栈到s2中 ,s2中的值:4,3,2,1
- 第3步:从s2中出栈一个元素,这个元素就是1 , 把1出栈
- 第4步:把s2所有的元素再次出栈到s1当中
- 最终s1 内为: 2,3,4
-
源文件
04-ds/16-double_seqstack_one_sequeue.c- 1
- 源代码
#include#include #include #include // sequeue stack #define N 32 typedef struct { int data[N]; // 数组的空间 int index ; // 是数组下标的索引 }seqstack_t; seqstack_t * create_empty_seqstack() { seqstack_t * s = (seqstack_t *)malloc(sizeof(seqstack_t)); memset(s->data,0,sizeof(s->data)) ; // 把数组中的内容清为0 s->index = -1 ; // 表示栈为空 return s ; } int seqstack_is_empty(seqstack_t * s) { return (s->index == -1 ); } int seqstack_is_full(seqstack_t *s) { return (s->index == N-1) ; } // 入栈 , 压栈 int seqstack_push(seqstack_t *s, int value) { if(seqstack_is_full(s)) { printf("栈已满"); return -1 ; } s->index ++ ; s->data[s->index] = value ; return 0 ; } int seqstack_pop(seqstack_t * s, int *pvalue) { if(seqstack_is_empty(s)) { printf("栈已空"); return -1 ; } *pvalue = s->data[s->index] ; s->index -- ; return 0 ; } int sequeue_enqueue(seqstack_t *s1,seqstack_t *s2,int value) { seqstack_push(s1,value); return 0; } int sequeue_dequeue(seqstack_t *s1,seqstack_t *s2,int *pvalue) { int value ; // 1. 把s1中的所有元素倒入到s2中 while(!seqstack_is_empty(s1)) { seqstack_pop(s1,&value); seqstack_push(s2,value); } // 2. 出一个元素 seqstack_pop(s2,pvalue); // 3. 把s2中的所有元素倒入到s1中 while(!seqstack_is_empty(s2)) { seqstack_pop(s2,&value); seqstack_push(s1,value); } return 0 ; } int main(int argc, char const *argv[]) { seqstack_t *S1 = create_empty_seqstack(); seqstack_t *S2 = create_empty_seqstack(); // 这个队列, 最多可以存放 31 个元素 printf("入队顺序为:"); for (int i = 0; i < 32; i++) { if (sequeue_enqueue(S1,S2, i + 1) == 0) { printf("%d ", i + 1); } } printf("\n"); printf("出队顺序为:"); for (int i = 0,value; i < 32; i++) { if (sequeue_dequeue(S1,S2, &value) == 0) { printf("%d ", value); } } printf("\n"); return 0; } - 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
- 运行结果
入队顺序为: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 出队顺序为: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- 1
- 2
2. 实例17 链式的双栈实现一个队列
- 流程如实例16
- 源文件
04-ds/17-double_linkstack_one_linkqueue.c- 1
- 源代码
#include#include #include #include // link stack typedef struct node { int data; struct node *next; } linklist_t; linklist_t *create_empty_linkstack() { linklist_t *s = (linklist_t *)malloc(sizeof(linklist_t)); s->data = 0; s->next = NULL; return s; } // 链表没有满 , 有空的概念 int linkstack_is_empty(linklist_t *s) { return (s->next == NULL); } // 头部插入法 int linkstack_push(linklist_t *s, int value) { linklist_t *p = (linklist_t *)malloc(sizeof(linklist_t)); p->data = value; p->next = s->next; s->next = p; return 0; } // 头部删除法 int linkstack_pop(linklist_t *s, int *pvalue) { linklist_t *p = s->next; // p 指向s的下一个节点 if(linkstack_is_empty(s)) { printf("栈已空"); return -1 ; } // s->next 不为空 s->next = p->next; // 接链表 *pvalue = p->data ; // 读取数据 free(p); return 0; } int linkqueue_enqueue(linklist_t *s1,linklist_t *s2,int value) { linkstack_push(s1,value); return 0; } int linkqueue_dequeue(linklist_t *s1,linklist_t *s2,int *pvalue) { int value ; // 1. 把s1中的所有元素倒入到s2中 while(!linkstack_is_empty(s1)) { linkstack_pop(s1,&value); linkstack_push(s2,value); } // 2. 出一个元素 linkstack_pop(s2,pvalue); // 3. 把s2中的所有元素倒入到s1中 while(!linkstack_is_empty(s2)) { linkstack_pop(s2,&value); linkstack_push(s1,value); } return 0 ; } int main(int argc, char const *argv[]) { linklist_t *S1 = create_empty_linkstack(); linklist_t *S2 = create_empty_linkstack(); // 这个队列, 最多可以存放 31 个元素 printf("入队顺序为:"); for (int i = 0; i < 32; i++) { if (linkqueue_enqueue(S1,S2, i + 1) == 0) { printf("%d ", i + 1); } } printf("\n"); printf("出队顺序为:"); for (int i = 0,value; i < 32; i++) { if (linkqueue_dequeue(S1,S2, &value) == 0) { printf("%d ", value); } } printf("\n"); return 0; } - 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
- 运行结果
入队顺序为: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 出队顺序为: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- 1
- 2
3. 实例18 顺序的双队列实现一个栈
-
初始状态 QueueA 和QueueB都为空
-
第1步: 把QueueA 入队1,2,3,4
-
第2补: 把QueueA 出队1,2,3 到QueueB, 此时QueueA中还剩下一个4
-
第3步: 从QueueA中出队最后一个元素4 , 4就是出栈的元素
-
第4步: 把QueueB中的所有元素再入队到QueueA中, 此时一次出栈完成
-
最后的效果是: QueueA中是 1,2,3 QueueB中空
-
计算队列元素个数
- 源文件
04-ds/18-double_sequeue_one_seqstack.c- 1
- 源代码
#include#include #include // sequence queue #define N 32 typedef struct { int data[N]; int front; // 队列的头 , 数组的下标 int rear; // 队列的尾 , 数组的下标 } sequeue_t; // 空队列的概念是 : 队头等于队尾 // 为了区分空队 和满队 , 队列元素个数要比数组元素少一个 // 满队+1 等于空队 // 1 2 3 4 5 // f f // r sequeue_t *create_empty_sequeue() { sequeue_t *q = (sequeue_t *)malloc(sizeof(sequeue_t)); memset(q->data, 0, sizeof(q->data)); q->front = q->rear = N - 1; //指向数组最后一个元素 return q; } int sequeue_is_empty(sequeue_t *q) { return (q->front == q->rear); } int sequeue_is_full(sequeue_t *q) { // 队尾 +1 == 队头 , 就是满队 // 任何一个一个数对N求余 , 这个数的范围是 0 - N-1 return ((q->rear + 1) % N == q->front); } int sequeue_is_size(sequeue_t *q) { // 队尾减去队头就是元素的个数 if (q->rear >= q->front) // return (q->rear - q->front); else return (N - q->front + q->rear); } int sequeue_enqueue(sequeue_t *q, int value) { if (sequeue_is_full(q)) { printf("队列已满"); return -1; } q->rear = (q->rear + 1) % N; // 防止数组越界 q->data[q->rear] = value; return 0; } int sequeue_dequeue(sequeue_t *q, int *pvalue) { if (sequeue_is_empty(q)) { printf("队列已空"); return -1; } q->front = (q->front + 1) % N; // 防止数组越界 *pvalue = q->data[q->front]; return 0; } int seqstack_push(sequeue_t *q1, sequeue_t *q2, int value) { sequeue_enqueue(q1, value); // 队列不满 return 0; } int seqstack_pop(sequeue_t *q1, sequeue_t *q2, int *pvalue) { int value; // q1 出队列只剩下一个元素 // printf("sequeue_is_size(q1)=%d\n",sequeue_is_size(q1)); while (sequeue_is_size(q1) > 1) { sequeue_dequeue(q1, &value) ; sequeue_enqueue(q2, value); } // 把q1中的元素出队 sequeue_dequeue(q1, pvalue); // 把q2中的所有元素出队到q1 while (sequeue_is_size(q2) > 0) { sequeue_dequeue(q2, &value); sequeue_enqueue(q1, value); } return 0; } int main(int argc, char const *argv[]) { sequeue_t *Q1 = create_empty_sequeue(); sequeue_t *Q2 = create_empty_sequeue(); printf("入栈顺序:"); for (int i = 0; i < 32; i++) { if (seqstack_push(Q1, Q2, i + 1) == 0) // 表示成功 { printf("%d ", i + 1); } } printf("\n"); printf("出栈顺序:"); for (int i = 0, value; i < 32; i++) { if (seqstack_pop(Q1, Q2, &value) == 0) { printf("%d ", value); } } printf("\n"); return 0; } - 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
- 125
- 126
- 运行结果
入栈顺序: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 出栈顺序:31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 队列已空1- 1
- 2
4. 实例19 链式的双队列实现一个栈
- 源文件
04-ds/19-double_linkqueue_one_linkstack.c- 1
- 源代码
#include#include #include // link queue typedef struct node { int data; struct node *next; } linklist_t; typedef struct { linklist_t *front; // 队头 linklist_t *rear; // 队尾 } linkqueue_t; // 空队列的概念是 : 队头等于队尾 // 为了区分空队 和满队 , 队列元素个数要比数组元素少一个 // 满队+1 等于空队 // 1 2 3 4 5 // f f // r linkqueue_t *create_empty_linkqueue() { linklist_t *h = (linklist_t *)malloc(sizeof(linklist_t)); linkqueue_t *q = (linkqueue_t *)malloc(sizeof(linkqueue_t)); q->front = q->rear = h; q->front->data = 0; return q; } int linkqueue_is_empty(linkqueue_t *q) { return (q->front == q->rear); } // 链式队列没有满的概念 // int linkqueue_is_full(linkqueue_t *q) // { // } int linkqueue_is_size(linkqueue_t *q) { int size = 0 ; linklist_t *p = q->front->next; // 指向队列的第1个元素 while(p != NULL) { size ++; p = p->next ; } return size ; } // 入队 队尾加 int linkqueue_enqueue(linkqueue_t *q, int value) { linklist_t *p = (linklist_t *)malloc(sizeof(linklist_t)); p->data = value; p->next = q->rear->next; // 尾部插入第1步 q->rear->next = p; // 尾部插入第2步 q->rear = p; // 尾部插入第3步 return 0; } // 头部出队列 , 头部删除法 int linkqueue_dequeue(linkqueue_t *q, int *pvalue) { linklist_t *p; if (linkqueue_is_empty(q)) { printf("队列为空"); return -1; } p = q->front->next; // 头节点的下一个节点 , p是要删除的节点 q->front->next = p->next; // 接上链表 if (q->front->next == NULL) // 此时队列为空 q->rear = q->front; // *pvalue = p->data; free(p); return 0; } int linkstack_push(linkqueue_t *q1, linkqueue_t *q2, int value) { linkqueue_enqueue(q1, value); // 队列不满 return 0; } int linkstack_pop(linkqueue_t *q1, linkqueue_t *q2, int *pvalue) { int value; // q1 出队列只剩下一个元素 // printf("linkqueue_is_size(q1)=%d\n",linkqueue_is_size(q1)); while (linkqueue_is_size(q1) > 1) { linkqueue_dequeue(q1, &value) ; linkqueue_enqueue(q2, value); } // 把q1中的元素出队 linkqueue_dequeue(q1, pvalue); // 把q2中的所有元素出队到q1 while (linkqueue_is_size(q2) > 0) { linkqueue_dequeue(q2, &value); linkqueue_enqueue(q1, value); } return 0; } int main(int argc, char const *argv[]) { linkqueue_t *Q1 = create_empty_linkqueue(); linkqueue_t *Q2 = create_empty_linkqueue(); printf("入栈顺序:"); for (int i = 0; i < 32; i++) { if (linkstack_push(Q1, Q2, i + 1) == 0) // 表示成功 { printf("%d ", i + 1); } } printf("\n"); printf("出栈顺序:"); for (int i = 0, value; i < 32; i++) { if (linkstack_pop(Q1, Q2, &value) == 0) { printf("%d ", value); } } printf("\n"); return 0; } - 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
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 运行结果
入栈顺序: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 出栈顺序:32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1- 1
- 2
-
相关阅读:
C语言的break、continue、switch、goto语句
Python开发利器之VS Code
spark基础
C高级作业 【使用shell脚本】 实现一个对数组求和的函数，数组通过实参传递给函数+写一个函数输出当前用户的uid和gid，并使用变量接收结果
Nacos本地修改编译源码2.2.3
小程序中用于跳转页面的5个api是什么和区别
AcWing---转圈游戏---快速幂
程序员职场生态：近8成本科毕业生起薪过万，跳槽首选智能汽车行业
【数智化人物展】同方有云联合创始人兼总经理江琦：云计算，引领数智化升级的动能...
golang promethus consul 服务发现
- 原文地址：https://blog.csdn.net/shengli001842/article/details/127951172
