热门标签
热门文章
- 1电脑技巧：分享8个Win11系统必备小技巧_window11使用技巧
- 2【LSTM时间序列预测】基于matlab麻雀算法优化LSTM时间序列预测（含前后对比）【含Matlab源码 2029期】_麻雀优化lstm收敛曲线
- 3QLEXpress语法分析和计算的入口类详细分析--Expressrunner(一)
- 4TextExtract(3)NLP Token Name Finder
- 5python 堆与栈_python中的堆和栈
- 6PowerDesigner -介绍_powerdesigner平时用的多吗
- 7蚁剑、哥斯拉、菜刀、冰蝎（3.0/4.0）流量特征_冰蝎4.0流量特征
- 8【2024最新华为OD-C/D卷试题汇总】[支持在线评测] 异国客人的幸运数字 (100分) - 三语言AC题解(Python/Java/Cpp)
- 9WireGuard 组网教程：快速构建安全高效的私密网络并实现内网穿透_wire guard_wire-guard
- 10The Rust Programming Language - 第6章 枚举和模式匹配 - 6.1 定义枚举
当前位置: article > 正文
【数据结构】栈和队列--＞理解和实现（赋源码)
作者：我家小花儿 | 2024-06-12 08:59:36
赞
踩
【数据结构】栈和队列--＞理解和实现（赋源码)
前面介绍了顺序表、单链表、双向循环链表，基本上已经结束了链表的讲解，今天谈一下栈、队列。可以简单的说是前面学习的一特殊化实现，但是总体是相似的。
前言
栈是一种特殊的线性表，它只允许在一端进行插入和删除操作。这一端被称为栈顶，另一端被称为栈底。栈的特点是后进先出（LIFO），即最后进入的元素最先被移除。
队列是另一种特殊的线性表，它允许在一端进行插入操作，在另一端进行删除操作。插入操作的一端称为队尾，删除操作的一端称为队头。队列的特点是先进先出（FIFO），即最先进入的元素最先被移除。
栈和队列有各自的特点，严格讲用顺序表还是链表的实现都可以。但我们根据结构特点选择一个更加适合的结构进行是实现。
一、栈和队列的理解
对于栈的理解：
栈如同这个图一样，要是想拿出数据，必须从上面一个一个往下面拿。这也正是 LIFO 的体现。
对于队列的理解：
队列如同这个图一样，要是想拿出数据，必须前面一个一个往向后面拿。这也正是 FIFO 的体现。
二、栈的实现（顺组表）
2.1 栈的功能
//初始化 void STInit(ST* ps); //压栈 void STpush(ST* ps, STDataType x); //删除 void STPop(ST* ps); //大小 int STSize(ST* ps); //判空 bool STEmpty(ST* ps); //出栈 STDataType STTop(ST* ps); //检查容量 void CheckCapacity(ST* ps); //销毁 void STDestroy(ST* ps);
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
2.2 栈结构体的定义及其初始化
结构体的定义
typedef int STDataType;
typedef struct stack
{
STDataType* a;
int top;
int capacity;
}ST;
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
初始化（开辟空间）
void STInit(ST* ps)
{
assert(ps);
ps->a = (STDataType*)malloc(sizeof(STDataType)*4);
if (ps->a == NULL)
{
perror("malloc fail");
return;
}
ps->capacity = 4;
ps->top = 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
2.3 压栈（存储数据）
//压栈
void STpush(ST* ps,STDataType x)
{
assert(ps);
ps->a[ps->top] = x;
ps->top++;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
2,4 删除数据
在这里面删除数据是配合，栈顶出栈。每次拿出一个数据，就要减少一个数据。
void STPop(ST* ps)
{
assert(ps);
assert(!STEmpty(ps));
ps->top--;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
2.5 计算栈内元个数
//大小
int STSize(ST* ps)
{
assert(ps);
return ps->top;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
2.6 判断栈内是否为空
这里运用 bool 类型直接返回，比较方便。
bool STEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
2.7 出栈
//出栈
STDataType STTop(ST* ps)
{
assert(ps);
return ps->a[ps->top-1];
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
2.8 增加容量
//检查容量 void CheckCapacity(ST*ps) { assert(ps); if (ps->top == ps->capacity) { ST* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * (ps->capacity) * 2); if (tmp == NULL) { perror("malloc fail"); return; } ps->capacity *= 2; ps->a = tmp; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
2.9 销毁栈
//销毁
void STDestroy(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
三、队列的实现（单链表）
3.1 队列的功能
//初始化 void QueueInit(Queue* ps); //销毁 void QueueDestroy(Queue* ps); //入队 void QueuePush(Queue* ps, QDataType x); //删除 void QueuePop(Queue* ps); //大小 int QueueSize(Queue* ps); //判空队 bool QueueEmpty(Queue* ps); //出队头 QDataType QueueTop(Queue* ps); //出队尾 QDataType QueueBack(Queue* ps);
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
3.2 队列的结构体定义以及初始化
结构体定义
定义两个结构体，第一个为存放数据，第二个结构体为两个指针，分别指向头和尾
typedef int QDataType; typedef struct QNode { struct QNode* next; QDataType data; }QNode; typedef struct Queue { QNode*head; QNode*tail; int szie; }Queue;
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
初始化
//初始化
void QueueInit(Queue* ps)
{
assert(ps);
ps->head = ps->tail = NULL;
ps->szie = 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
3.3 队列销毁
//销毁
void QueueDestroy(Queue* ps)
{
assert(ps);
QNode* cur = ps->head;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
ps->head = ps->tail = NULL;
ps->szie = 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
3.4 入队（插入数据）
//入队 void QueuePush(Queue* ps,QDataType x) { assert(ps); QNode* newcode = (QNode*)malloc(sizeof(QNode)); if (newcode == NULL) { perror("malloc fail"); return ; } newcode->next = NULL; newcode->data = x; if (ps->head == NULL) { ps->head = ps->tail = newcode; } else { ps->tail->next = newcode; ps->tail = newcode; } ps->szie++; }
- 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
3.5 删除数据（头删）
//删除 void QueuePop(Queue* ps) { assert(ps); assert(ps->head != NULL); assert(!QueueEmpty(ps)); if (ps->head->next == NULL) { free(ps->head); ps->head = ps->tail = NULL; } else { QNode* next = ps->head->next; free(ps->head); ps->head = next; } ps->szie--; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
3.6 计算队列元素个数
//大小
int QueueSize(Queue* ps)
{
assert(ps);
return ps->szie;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
3.7 判断是否队列为空
//判空队
bool QueueEmpty(Queue* ps)
{
assert(ps);
return ps->szie == 0;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
3.8 出队（头）
//出队头
QDataType QueueTop(Queue* ps)
{
assert(ps);
assert(!QueueEmpty(ps));
return ps->head->data;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
3.9 出队（尾）
//出队尾
QDataType QueueBack(Queue* ps)
{
assert(ps);
return ps->tail->data;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
四、栈和队列的源码
栈
Stack.h
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int STDataType; typedef struct stack { STDataType* a; int top; int capacity; }ST; //初始化 void STInit(ST* ps); //压栈 void STpush(ST* ps, STDataType x); //删除 void STPop(ST* ps); //大小 int STSize(ST* ps); //判空 bool STEmpty(ST* ps); //出栈 STDataType STTop(ST* ps); //检查容量 void CheckCapacity(ST* ps); //销毁 void STDestroy(ST* ps);
- 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
Stack.c
#define _CRT_SECURE_NO_WARNINGS #include "stack.h" //初始化 void STInit(ST* ps) { assert(ps); ps->a = (STDataType*)malloc(sizeof(STDataType*)*4); if (ps->a == NULL) { perror("malloc fail"); return; } ps->capacity = 4; ps->top = 0; } //销毁 void STDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->capacity = 0; ps->top = 0; } //检查容量 void CheckCapacity(ST*ps) { assert(ps); if (ps->top == ps->capacity) { ST* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * (ps->capacity) * 2); if (tmp == NULL) { perror("malloc fail"); return; } ps->capacity *= 2; ps->a = tmp; } } //压栈 void STpush(ST* ps,STDataType x) { assert(ps); ps->a[ps->top] = x; ps->top++; } //删除 void STPop(ST* ps) { assert(ps); assert(!STEmpty(ps)); ps->top--; } //判空 bool STEmpty(ST* ps) { assert(ps); return ps->top == 0; } //出栈 STDataType STTop(ST* ps) { assert(ps); return ps->a[ps->top-1]; } //大小 int STSize(ST* ps) { assert(ps); return ps->top; }
- 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
test.c
#define _CRT_SECURE_NO_WARNINGS #include "stack.h" void teststack() { ST st; STInit(&st); STpush(&st, 1); STpush(&st, 2); STpush(&st, 3); STpush(&st, 4); STpush(&st, 5); printf("%d", STSize(&st)); printf("\n"); while (!STEmpty(&st)) { printf("%d ", STTop(&st)); STPop(&st); } printf("\n"); printf("%d", STSize(&st)); STDestroy(&st); } int main() { teststack(); 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
队列
Queue.h
#pragma once #include <stdio.h> #include <assert.h> #include <stdlib.h> #include <stdbool.h> typedef int QDataType; typedef struct QNode { struct QNode* next; QDataType data; }QNode; typedef struct Queue { QNode*head; QNode*tail; int szie; }Queue; //单链表的实现，FIFO //初始化 void QueueInit(Queue* ps); //销毁 void QueueDestroy(Queue* ps); //入队 void QueuePush(Queue* ps, QDataType x); //删除 void QueuePop(Queue* ps); //大小 int QueueSize(Queue* ps); //判空队 bool QueueEmpty(Queue* ps); //出队头 QDataType QueueTop(Queue* ps); //出队尾 QDataType QueueBack(Queue* ps);
- 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
Queue.c
#define _CRT_SECURE_NO_WARNINGS #include "queue.h" //初始化 void QueueInit(Queue* ps) { assert(ps); ps->head = ps->tail = NULL; ps->szie = 0; } //销毁 void QueueDestroy(Queue* ps) { assert(ps); QNode* cur = ps->head; while (cur) { QNode* next = cur->next; free(cur); cur = next; } ps->head = ps->tail = NULL; ps->szie = 0; } //入队 void QueuePush(Queue* ps,QDataType x) { assert(ps); QNode* newcode = (QNode*)malloc(sizeof(QNode)); if (newcode == NULL) { perror("malloc fail"); return ; } newcode->next = NULL; newcode->data = x; if (ps->head == NULL) { ps->head = ps->tail = newcode; } else { ps->tail->next = newcode; ps->tail = newcode; } ps->szie++; } //删除 void QueuePop(Queue* ps) { assert(ps); assert(ps->head != NULL); assert(!QueueEmpty(ps)); if (ps->head->next == NULL) { free(ps->head); ps->head = ps->tail = NULL; } else { QNode* next = ps->head->next; free(ps->head); ps->head = next; } ps->szie--; } //大小 int QueueSize(Queue* ps) { assert(ps); return ps->szie; } //判空队 bool QueueEmpty(Queue* ps) { assert(ps); return ps->szie == 0; } //出队头 QDataType QueueTop(Queue* ps) { assert(ps); assert(!QueueEmpty(ps)); return ps->head->data; } //出队尾 QDataType QueueBack(Queue* ps) { assert(ps); return ps->tail->data; }
- 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
test.c
#define _CRT_SECURE_NO_WARNINGS #include "queue.h" void testQueue() { Queue s; QueueInit(&s); QueuePush(&s, 1); QueuePush(&s, 2); QueuePush(&s, 3); QueuePush(&s, 4); //printf("%d ", QueueTop(&s)); //QueuePop(&s); //printf("%d ", QueueTop(&s)); //QueuePop(&s); //printf("%d ", QueueTop(&s)); //QueuePop(&s); //printf("%d ", QueueTop(&s)); //QueuePop(&s); //printf("\n"); while (!(QueueEmpty(&s))) { printf("%d ", QueueTop(&s)); QueuePop(&s); } QueueDestroy(&s); } int main() { testQueue(); 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
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家小花儿/article/detail/707414
推荐阅读
- 线性表的顺序存储 ...
赞
踩
相关标签
