目录一、栈的概念二、栈的实现2.1 栈的初始化2.2 栈的销毁2.3 栈的插入2.4 栈的出栈2.5 取栈顶2.6 取栈中有效元素个数2.7 判断栈是否为空三、队列的概念四、队列的实现4.1 队列结构体定义4.2 队列的初始化4.3 队列的销毁4.4 入队列4.5 出队列4.6 取队头数据4.7 取队尾数据4.8 队列判空4.9 队列中有效元素个数五、总结与反思优缺点以及用法一、栈的概念⼀种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进⾏数据插⼊和删除操作的⼀端称为栈顶另⼀端称为栈底。归根结底就是先进后出。底层结构是数组也可以是链表但是方便访问和节约空间这里选择数组。因此选择数组的物理结构和逻辑结构都是线性的。二、栈的实现2.1 栈的初始化定义一个栈结构//栈结构 typedef char STDataType; typedef struct Stack { STDataType* arr; int top; int capacity; }ST;//初始化 void StackInit(ST* Stack) { Stack-arr NULL; Stack-capacity Stack-top 0; }2.2 栈的销毁//销毁栈 void StackDestory(ST* Stack) { if (Stack-arr) free(Stack-arr); Stack-arr NULL; Stack-capacity Stack-top 0; }2.3 栈的插入//入栈 void StackPush(ST* Stack, STDataType x) { assert(Stack); //空间不够 if (Stack-capacity Stack-top) { //扩容 int newcapacity Stack-capacity 0 ? 4 : 2 * Stack-capacity; STDataType* tmp (STDataType*)realloc(Stack-arr, newcapacity * sizeof(STDataType)); if (tmp NULL) { perror(realloc); exit(1); } Stack-arr tmp; Stack-capacity newcapacity; } //空间够 Stack-arr[Stack-top] x; }2.4 栈的出栈//出栈 void StackPop(ST* Stack) { assert(!StackEmpty(Stack)); --Stack-top; }2.5 取栈顶//获取栈顶元素 STDataType StackTop(ST* Stack) { assert(!StackEmpty(Stack)); return Stack-arr[Stack-top - 1]; }2.6 取栈中有效元素个数//获取栈中元素个数 int StackSize(ST* Stack) { assert(!StackEmpty(Stack)); return Stack-top; }2.7 判断栈是否为空//判断 bool StackEmpty(ST* Stack) { assert(Stack); return Stack-arrNULL; }三、队列的概念只允许在⼀端进性插入数据操作在另⼀端进行删除数据操作的特殊线性表。队列满足先进先出就行它底层既可以用数组也可以用链表各有各的优缺点链表的尾删和尾插这些时间复杂度是oN但是这些缺点可以通过一些列办法弥补回来所以这里队列底层是用的链表。四、队列的实现4.1 队列结构体定义为了弥补链表尾删和尾插时间复杂度为o(N)这一缺陷这里可以定义2个结构体一个结构体用来结点内元素的结构体另一个结构体是用来标记头结点这里没有头结点只是为了理解设置的头结点里面有数据。ps头结点没有数据和尾结点用于保存尾节点方便访问和插入删除尾结点。//结点结构 typedef struct QueueNode { QDataType data; struct QueueNode* next; }QueueNode; //队列结构 typedef struct Queue { QueueNode* phead; QueueNode* ptail; //int size; }Queue;4.2 队列的初始化//初始化 void QueueInit(Queue* pq) { assert(pq); pq-phead pq-ptail NULL; //pq-size 0; }4.3 队列的销毁//销毁 void QueueDestroy(Queue* pq) { assert(pq); QueueNode* pcur pq-phead; while (pcur) { QueueNode* next pcur-next; free(pcur); pcur next; } pq-phead pq-ptail NULL; //pq-size 0; }4.4 入队列//入队 void QueuePush(Queue* pq,QDataType x) { assert(pq); //创建结点 QueueNode* newnode (QueueNode*)malloc(sizeof(QueueNode)); if (newnode NULL) { perror(malloc); exit(1); } newnode-data x; newnode-next NULL; if (pq-phead NULL) { pq-phead pq-ptail newnode; } else { pq-ptail-next newnode; pq-ptail newnode; } //pq-size; }4.5 出队列//出队 void QueuePop(Queue* pq) { assert(!QueueEmpty(pq)); if (pq-phead pq-ptail) { free(pq-phead); pq-phead pq-ptail NULL; } else { QueueNode* next pq-phead-next; free(pq-phead); pq-phead next; } //pq-size--; }4.6 取队头数据//取队头元素 QDataType QueueFront(Queue* pq) { assert(!QueueEmpty(pq)); return pq-phead-data; }4.7 取队尾数据//取队尾元素 QDataType QueueBack(Queue* pq) { assert(!QueueEmpty(pq)); return pq-ptail-data; }4.8 队列判空//判空 bool QueueEmpty(Queue* pq) { assert(pq); return pq-phead NULL; }4.9 队列中有效元素个数//队列元素个数 int QueueSize(Queue* pq) { assert(!QueueEmpty(pq)); int size 0; while (pq-phead) { pq-phead pq-phead-next; size; } return size; //return pq-size; }五、总结与反思优缺点以及用法栈优点缺点操作简单插入删除这些时间复杂度都是o1内存浪费需要向内存动态申请空间内存管理方便避免插入和删除移动数据局限性只能访问栈顶数据无法访问其他数据适用于递归栈在递归函数调用中非常有用因为每次函数调用都会在栈中创建新的栈帧函数返回时会自动释放 空间限制空间不够还需要用编程手段开辟空间使用应用场景括号匹配使用栈可以有效地解决括号匹配问题有效的括号数据结构oj题力口20-CSDN博客表达式求值栈可以用于将中缀表达式转换为后缀表达式并进行求值递归调用栈在递归函数调用中用于存储函数的局部变量和返回地址队列优点缺点顺序处理队列能够按顺序处理数据非常适合需要按顺序处理任务的场景如任务调度、打印队列等访问限制只能在一段添加元素在另一端移除元素无法访问中间元素实现代码简单用的链表动态调整内存方面链表可以动态调整大小不受固定容量限制应用场景广度优先搜索在图的遍历中广度优先搜索使用队列来存储待访问的节点。任务调度操作系统中的任务调度器使用队列来管理待执行的任务。消息队列在分布式系统中消息队列用于在不同服务之间传递消息。