邯郸网站设计怎么注册,logo模板素材,前端做网站商城 购物车怎么做,企业宽带解决方案前言 #x1f493;作者简介#xff1a; 加油#xff0c;旭杏#xff0c;目前大二#xff0c;正在学习C#xff0c;数据结构等#x1f440; #x1f493;作者主页#xff1a;加油#xff0c;旭杏的主页#x1f440; ⏩本文收录在#xff1a;再识C进阶的专栏#x1…前言 作者简介 加油旭杏目前大二正在学习C数据结构等 作者主页加油旭杏的主页 ⏩本文收录在再识C进阶的专栏 代码仓库旭日东升 1 欢迎大家点赞 收藏 ⭐ 加关注哦 学习目标 这一篇博客将学习栈和队列的相关知识栈和队列是两种基础的数据结构在现在一定要打好基础在之后的学习生涯中也常常遇见例如深度优先搜索DFS广度优先搜索BFS……今天要学习栈和队列的模拟实现用数组模拟实现栈用单链表模拟实现队列用数组模拟实现队列。 学习内容
通过上面的学习目标我们可以列出要学习的内容
用数组模拟实现栈用数组模拟实现队列用单链表模拟实现队列 一、栈的相关知识
1.1 栈的概念及结构
下面先来一段大白话在介绍栈的文章中都会出现的。 栈是一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作类似于尾插尾删。我们先来介绍两个概念——栈顶与栈底进行数据插入和删除操作的一端为栈顶而另一端为栈底。高大上一点的叫法是栈中的元素遵守后进先出LIFO(Last In First Out)的原则。
下面我们在来介绍两个操作——圧栈与入栈
压栈栈的插入操作是进栈/压栈/入栈入数据在栈顶出栈栈的删除操作是出栈出数据在栈顶。
1.2 栈的实现 现在我们学习了两个数据结构顺序表与链表到底用哪个数据结构实现栈比较好呢在这里我们选用数组来模拟实现栈。 为什么我们要用数组模拟实现栈会更好一些 栈的两个操作无疑就是尾插与尾删这两个操作在数组中都比较容易实现相对于链表而且数组存储的数据内容比较集中CPU高速缓存命中率高尽可能小地不污染缓存区所以用数组模拟实现比较好一些。 在现实生活中我们一般要实现能够进行动态增长的栈而不是静态的栈比较死板在实际应用中不常见。虽然静态的栈在实际生活中不常见但是在算法题目中还是可以进行使用而且在算法题中我们不用考虑内存泄漏问题hh。下面来实现吧
代码一实现动态的栈 第一步我们先来定义要使用的头文件 #include stdio.h //必须要包含的头文件
#include assert.h //要使用assert进行断言防止出现一下不好的情况发生
#include stdbool.h //在C语言中没有提供bool变量
#include stdlib.h //使用一些申请内存空间的函数第二步我们要让主角登场构造栈的结构体 typedef int StDatatype; // 为了方便以后更改数组中的数据类型
typedef struct stack {StDatatype* a; // 一个动态空间int top; // 表示栈的栈顶int capacity; // 表示栈现在有多少空间
}ST; 第三步我们要定义一些我们要实现栈功能的一些函数栈的初始化定义一个结构一定要初始化成员变量、栈的销毁、栈的插入操作、栈的删除操作、查看栈的栈顶元素、查看栈的大小、查看栈是否为空 //栈的初始化
void stackinit(ST* stk);
//栈的插入操作
void stackpush(ST* stk, StDatatype x);
//栈的删除操作
void stackpop(ST* stk);
//返回栈的栈顶元素
StDatatype stacktop(ST* stk);
//判断栈是否为空
bool stackempty(ST* stk);
//返回栈的大小
int stacksize(ST* stk);
//销毁栈
void stackdestroy(ST* stk); 栈的初始化操作 void stackinit(ST* stk)
{assert(stk); //防止传空指针//有两个方式进行初始化//法1stk-a NULL;stk-capacity 0;stk-top 0; //如果这里指向0top表示的是栈的大小
}//法2
void stackinit(ST* stk)
{assert(stk);stk-a NULL;stk-capacity 0;stk-top -1; //如果这里指向-1top表示的是栈顶元素的下标
} 栈的销毁操作 void stackdestroy(ST* stk)
{assert(stk);free(stk-a);stk-a NULL; // 别忘记置空防止野指针出现free(stk);stk NULL;
}
// 因为栈所使用的是数组所以直接销毁即可 栈的插入操作 void stackpush(ST* stk, StDatatype x)
{assert(stk);//因为我们在这里的栈的空间是没有创建的if (stk-capacity stk-top) {int newcapacity stk-capacity 0 ? 4 : stk-capacity * 2;StDatatype* tmp (StDatatype*)realloc(stk-a, newcapacity * sizeof(StDatatype));if (tmp NULL) {perror(tmp);return;}stk-a tmp;stk-capacity newcapacity;}
//插入操作相当于尾插stk-a[stk-top] x;stk-top; // 别忘了栈顶要加1
} 栈的删除操作 void stackpop(ST* stk)
{assert(stk);assert(stk-top 0);stk-top--;
} 返回栈的栈顶元素 StDatatype stacktop(ST* stk)
{assert(stk);assert(stk-top 0);return stk-a[stk-top - 1]; // top 0//return stk-a[stk-top]; // top -1
} 判断栈是否为空 bool stackempty(ST* stk)
{
// 第一种写法assert(stk);if (stk-top 0){return true;}return false;
// 第二种写法//return stk-top 0;
}返回栈的大小 int stacksize(ST* stk)
{assert(stk);return stk-top; // top 0//return stk-top 1; // top -1
} 代码二实现静态的栈
struct my_stack
{int a[10];int size;int capacity;
}
二、队列的相关知识
2.1 队列的概念及结构 队列在日常生活中无处不在排队就是一种典型的队列。对此我们大致可以得知队列是只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出的性质。和栈一样队列具有两个基本操作——入队和出队
入队进行插入操作的一端称为队尾
出队进行删除操作的一端称为队头。
2.2 队列的实现 与实现栈类似我们先来讨论一下使用哪种数据结构方便一些是使用顺序表呢还是使用链表呢是使用单链表呢还是使用双向链表 分析一下队列的插入和删除操作发现插入操作是尾插而删除操作是头删。在实现顺序表和链表时对于头删操作来说链表更为简单而顺序表需要进行移动数据效率较低。因此我们使用链表来实现操作。
代码一链表实现队列 第一步我们还是先将头文件加上 #include stdio.h
#include stdlib.h
#include stdbool.h
#include assert.h 第二步我们来建立一下队列的数据结构 typedef int QueDatatype;typedef struct queue {QueDatatype x;struct queue* next;
}Queue;//由于要用二级指针并且我们还有多个成员
//然后就用结构体typedef struct Qnode {Queue* phead;Queue* ptail; // 存储链表的尾结点方便于尾插int size;
}Qnode; 第三步我们来定义一下队列的功能队列的初始化队列的销毁队列的插入操作队列的删除操作返回队列的队头元素返回队列的大小检查队列是否为空。 //队列初始化
void queueinit(Qnode* qnd);
//队列销毁
void queuedestroy(Qnode* qnd);
//队列的插入操作
void queuepush(Qnode* qnd, QueDatatype x);
//队列的删除操作
void queuepop(Qnode* qnd);
//队列的对头元素
QueDatatype queuefront(Qnode* qnd);
//队列的大小
int queuesize(Qnode* qnd);
//检查队列是否为空
bool quueueempty(Qnode* qnd); 队列的初始化操作 void queueinit(Qnode* qnd)
{assert(qnd);qnd-phead qnd-ptail NULL;qnd-size 0;
} 队列的销毁操作 void queuedestroy(Qnode* qnd)
{assert(qnd);//销毁是要从头到尾进行销毁的Queue* cur qnd-phead;while (cur){Queue* del cur-next;free(cur);cur del;}
// 只有一个结点的情况会出现一个野指针qnd-phead qnd-ptail NULL;qnd-size 0;
} 队列的插入操作 void queuepush(Qnode* qnd, QueDatatype x)
{assert(qnd);//创建好了结构体然后进行操作Queue* tmp (Queue*)malloc(sizeof(Queue));//防止创建失败if (tmp NULL){perror(tmp);return;}tmp-x x;tmp-next NULL;//将这个新结点链接到链表中if (qnd-phead NULL){qnd-phead qnd-ptail tmp;}else {qnd-ptail-next tmp;qnd-ptail tmp;}qnd-size;
} 队列的删除操作 void queuepop(Qnode* qnd)
{assert(qnd);//头结点不能为空assert(qnd-phead);//其次在只有一个结点的过程中会出现野指针Queue* del qnd-phead;qnd-phead del-next;free(del);del NULL;if (qnd-phead NULL){qnd-ptail NULL;}qnd-size--;
} 返回队列的队头元素 QueDatatype queuefront(Qnode* qnd)
{assert(qnd);//不能队列为空assert(qnd-phead);return qnd-phead-x;
} 返回队列的大小 int queuesize(Qnode* qnd)
{assert(qnd);return qnd-size;
} 检查队列是否为空 bool quueueempty(Qnode* qnd)
{assert(qnd);//if (qnd-phead NULL)//{// return true;//}//return false;return qnd-phead NULL;
} 代码二数组实现队列
int q[N], hh, tt -1;
学习产出
用数组模拟实现栈用数组模拟实现队列用单链表模拟实现队列
