做网站 就上凡科建站,网站管理系统安装,网络营销具有哪些特点,docker run wordpress前言#xff1a;前面我们学习了单链表并且模拟了它的实现#xff0c;今天我们来进一步学习#xff0c;来学习栈和队列吧#xff01;一起加油各位#xff0c;后面的路只会越来越难走需要我们一步一个脚印#xff01; #x1f496; 博主CSDN主页:卫卫卫的个人主页 #x…前言前面我们学习了单链表并且模拟了它的实现今天我们来进一步学习来学习栈和队列吧一起加油各位后面的路只会越来越难走需要我们一步一个脚印 博主CSDN主页:卫卫卫的个人主页 专栏分类:数据结构 代码仓库:卫卫周大胖的学习日记 关注博主和博主一起学习!一起努力 什么是栈
栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出的原则如下图所示。 压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。 出栈栈的删除操作叫做出栈。出数据也在栈顶。 如何实现栈
栈的实现一般可以使用数组或者链表实现相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。所以我们今天通过使用动态数组来模拟实现栈。 栈的基本结构
我们已经确定了通过动态数组来模拟实现栈那么我们要实现哪些功能呢
栈的初始化栈的销毁入栈出栈获取栈顶元素检测栈是否为空获取栈中有效元素个数
首先我们需要考虑如何记录栈顶元素的位置我们用top来记录但是top是不是应该是0还是什么数据呢如果top指向的是0那么我top是0的时候栈中到底是一个元素还是没有元素这是十分具有歧义的所以我们这里用负一来表示top当有元素进入时就让top加加即可(如下图)。
具体结构如下:
typedef struct Stack
{STDataType* a;int top; //标识顶部int capacity;
}ST;栈的基本功能
#pragma once
#includestdio.h
#includeassert.h
#includestdlib.h
#includestdbool.htypedef int STDataType;typedef struct Stack
{STDataType* a;int top; //标识顶部int capacity;
}ST;//栈的初始化
void STInit(ST* pst);//栈的销毁
void STDestroy(ST* pst);//栈顶插入删除//入栈
void STPush(ST* pst, STDataType x);//出栈
void STPop(ST* pst);// 获取栈顶元素
STDataType STTop(ST* pst);// 检测栈是否为空如果为空返回非零结果如果不为空返回0
bool STEmpty(ST* pst);// 获取栈中有效元素个数
int STSize(ST* pst);
栈的初始化
思路导读:前面我们讲到过用top来记录栈顶的位置之所以让它从负一开始就是为了方便我们访问栈顶数据也是为了防止歧义如下图所示。我们初始化也只需要将开辟的空间指向空指针空间容量为0即可。代码实现:
void STInit(ST* pst)//栈的初始化
{assert(pst);pst-top -1;//表示top指向栈顶元素的下一个位置pst-a NULL;pst-capacity 0;
}栈的销毁
思路导读:我们只需要找到a开辟的空间将它释放掉并将他置为空指针即可然后其它值Top处理为-1空间容量置为0即可 代码实现
void STDestroy(ST* pst)//栈的销毁
{assert(pst);free(pst-a);pst-a NULL;pst-top -1;pst-capacity 0;
} 入栈
思路导读我们入栈首先就是得开辟一块空间存放即将要入栈的值然后将这块空间传给a即可然后再把栈顶元素赋值即可完成入栈。如果这块地方有不懂的友友可以去看我之前的博客有详细讲解动态顺序表 代码实现:
void STPush(ST* pst, STDataType x)//入栈
{assert(pst);if (pst-top 1 pst-capacity)//判断是否有空间{int newcapacity pst-capacity 0 ? 4 : pst-capacity * 2;STDataType* tmp (STDataType*)realloc(pst-a, sizeof(STDataType) * newcapacity);//防止开辟失败俩个空间都丢失if (tmp NULL){perror(realloc fail);return;}pst-a tmp;pst-capacity newcapacity;}pst-top;//top加一pst-a[pst-top] x;//栈顶赋值
}出栈
思路导读:关于出栈我们要知道他是先进后出在前面的图中我们都有详细的讲解出去一个元素我们让top往下走一个即可。 代码实现
void STPop(ST* pst)//出栈
{assert(pst);//判断是不是空assert(pst-top 0);//判断有没有元素pst-top--;//top减减即可
}获取栈顶元素
思路导读:首先我们还是得判断传来的数据是否为空里面是否有元素然后我们直接访问栈顶元素即可。
STDataType STTop(ST* pst)// 获取栈顶元素
{assert(pst);assert(pst-top 0);return pst-a[pst-top];
}函数测试与效果图:
void Test2()
{ST sl;STInit(sl);STPush(sl, 0);printf(%d , STTop(sl));STPush(sl, 9);printf(%d , STTop(sl));STPush(sl, 2);printf(%d , STTop(sl));STPush(sl, 2);printf(%d , STTop(sl));printf(上面是入栈后\n);printf(下面是出栈后栈顶元素\n);STPop(sl);printf(%d , STTop(sl));STPop(sl);printf(%d , STTop(sl));STPop(sl);printf(%d , STTop(sl));STPop(sl);
}检测栈是否为空
思路导读:首先判断传来的是否有这个结构体我们只需要判断top是否是负一如果是说明这个为真则返回0不是则返回非0的结果 代码实现:
bool STEmpty(ST* pst)// 检测栈是否为空如果为空返回非零结果如果不为空返回0
{assert(pst);return pst-top -1;//如果是-1则是空返回true,如果不是返回false
}获取栈中有效元素个数
思路导读我们只需要将top加一即为元素个数因为top指向的栈顶元素。
int STSize(ST* pst)// 获取栈中有效元素个数
{assert(pst);return pst-top 1;
}整体函数测试
void Test3()
{ST sl;STInit(sl);STPush(sl, 1);STPush(sl, 3);STPush(sl, 0);STPush(sl, 9);STPush(sl, 2);STPush(sl, 8);printf(入栈后元素的个数:%d\n, STSize(sl));printf(下面是入栈元素\n);while (!STEmpty(sl)){ printf(%d , STTop(sl));STPop(sl);//出栈}STDestroy(sl);
}
int main()
{//Test1();//Test2();Test3();return 0;
}具体效果图: 到这里关于栈的实现我们都已经讲完了接下来我们开始队列的学习 什么是队列
队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出我们可以通俗的理解成一头进一头出先进去的先出去。 入队列进行插入操作的一端称为队尾。 出队列进行删除操作的一端称为队头。 具体如下图 如何实现队列
由于队列的特殊性只能一头进一头出且先进的先出在实现它的时候我们只需要考虑尾插和头删即可在尾插和头删上效率较高的应该就是单链表了但我们应当用一个tail的尾指针来记录防止尾增的时候再次遍历链表。故我们通过单链表来实现队列。 队列的基本功能与结构
关于下面为什么会在用一个结构体来记录头指针和尾指针是因为如果我们补定义一个结构体来记录我们就会在入队列和出队列的时候需要传一个二级指针来修改队列中的值为了防止这样的麻烦我们就直接定义一个结构体来记录即可。 typedef int QDataType;typedef struct QueueNode
{QDataType val;struct QueueNode* next;
}QNode;typedef struct Queue//记录头指针和尾指针
{QNode* phead;QNode* ptail;int size;//记录元素个数
}Queue;// 初始化队列
void QueueInit(Queue* pq);//销毁队列
void QueueDestory(Queue* pq);// 队尾入队列
void QueuePush(Queue* pq, QDataType x);// 队头出队列
void QueuePop(Queue* pq);// 获取队列头部元素
QDataType QueueFront(Queue* pq);// 获取队列队尾元素
QDataType QueueBack(Queue* pq);// 检测队列是否为空如果为空返回非零结果如果非空返回0
bool QueueEmpty(Queue* pq);// 获取队列中有效元素个数
int QueueSize(Queue* pq);队列的初始化
思路导读关于队列的初始化我们只需要将头指针和尾指针置为空即可然后将里面的元素置为0。 代码实现:
void QueueInit(Queue* pq)//队列的初始化
{assert(pq);pq-phead pq-ptail NULL;pq-size 0;
}队尾入队列
思路导读首先我们得分两种情况一种是该队列为空第一次入队列一种是该队列不为空不是第一次入队列但无论如何都要开辟一块空间存放新开辟的值。当为第一次入队列的时候我们只需要将头节点和尾节点全部指向这块新开辟的空间即可。当不是第一次入的时候我们需要找到尾结点将它指向新开辟的这块空间即可完成入队列,且每当进入一个元素我们让size加加即可知道队列中的元素个数。如下图所示: 代码实现:
void QueuePush(Queue* pq, QDataType x)//队尾入队列
{assert(pq);QNode* newnode malloc(sizeof(QNode));if (newnode NULL){perror(malloc fail);return;}newnode-val x;newnode-next NULL;//判断是不是第一次if (pq-ptail NULL){pq-phead pq-ptail newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;//记录元素} 队头出队列
思路导读:首先我们得分为两种情况一种是队列中只有一个元素的情况一种是队列中有多个元素的情况。当队列中有多个元素的时候我们需要一个指针来保留头节点并找到头节点的下个位置让它成为新的节点并将原来的头节点释放掉即可完成出队列。但当队列中只有一个元素时候我们需要将头节点释放的同时也要将尾节点置为空指针不然就会出现野指针的情况。 代码实现
void QueuePop(Queue* pq)// 队头出队列
{assert(pq);assert(pq-phead);Queue* tmp pq-phead;//记录头指针方便释放空间pq-phead pq-phead-next;//让头指针指向下一个元素free(tmp);//释放头指针if (pq-phead NULL)//如果队列中只有一个元素将尾指针也置为空指针{pq-ptail NULL;}pq-size--;
}获取队列头部元素
思路导读:我们只需要找到头节点指向的val的值将它返回即可。 代码实现
QDataType QueueFront(Queue* pq)// 获取队列头部元素
{assert(pq);assert(pq-phead);assert(pq-ptail);return pq-phead-val;
} 获取队列队尾元素
思路导读:我们在这之前一直记录了一个尾部节点因此获取队尾元素的时候我们不需要重新在遍历队列只需要返回尾节点的值即可。 代码实现
QDataType QueueBack(Queue* pq)// 获取队列队尾元素
{assert(pq);assert(pq-phead);assert(pq-ptail);return pq-ptail-val;
} 检测队列是否为空
思路导读:我们只需要判断之前存储数据个数的size是否为空即可。 代码实现
bool QueueEmpty(Queue* pq)// 检测队列是否为空如果为空返回非零结果如果非空返回0
{assert(pq);return pq-size 0;
}获取队列中有效元素个数
思路导读我们直接返回记录元素个数的size即可获取队列中有效元素的个数。
int QueueSize(Queue* pq)// 获取队列中有效元素个数
{assert(pq);return pq-size;
}销毁队列
思路导读:我们要把队列中的每一个结点都释放掉我们需要一个指针dl记录头指针原本的位置让头指针往后走遍历队列依次释放经过的位置具体如下图 代码实现:
void QueueDestory(Queue* pq)//销毁队列
{assert(pq);Queue* dl NULL;while (pq-phead){dl pq-phead;pq-phead pq-phead-next;free(dl);}pq-ptail NULL;pq-size 0;pq-phead NULL;
}整体函数测试
void Test2()
{Queue s;QueueInit(s);QueuePush(s, 1);QueuePush(s, 2);QueuePush(s, 3);QueuePush(s, 4);QueuePush(s, 5);printf(%d , QueueFront(s)); printf(%d , QueueBack(s));printf(%d\n, QueueSize(s));QueuePop(s);QueuePop(s);printf(%d , QueueFront(s));printf(%d\n, QueueSize(s));if (!QueueEmpty(s)){QueuePop(s);printf(%d , QueueFront(s));printf(%d\n, QueueSize(s));}printf(%d\n, QueueSize(s));QueueDestory(s);
}int main()
{//Test1();Test2();return 0;
}运行结果: 整体代码
#pragma once
#includestdio.h
#includeassert.h
#includestdlib.h
#includestdbool.htypedef int QDataType;// 队列的结构
typedef struct QueueNode
{QDataType val;struct QueueNode* next;
}QNode;typedef struct Queue//记录头指针和尾指针
{QNode* phead;QNode* ptail;int size;//记录元素个数
}Queue;// 初始化队列
void QueueInit(Queue* pq);//销毁队列
void QueueDestory(Queue* pq);// 队尾入队列
void QueuePush(Queue* pq, QDataType x);// 队头出队列
void QueuePop(Queue* pq);// 获取队列头部元素
QDataType QueueFront(Queue* pq);// 获取队列队尾元素
QDataType QueueBack(Queue* pq);// 检测队列是否为空如果为空返回非零结果如果非空返回0
bool QueueEmpty(Queue* pq);// 获取队列中有效元素个数
int QueueSize(Queue* pq);
#includeQueen.hvoid QueueInit(Queue* pq)//队列的初始化
{assert(pq);pq-phead pq-ptail NULL;pq-size 0;
}void QueuePush(Queue* pq, QDataType x)//队尾入队列
{assert(pq);QNode* newnode malloc(sizeof(QNode));//开辟新空间if (newnode NULL){perror(malloc fail);return;}//赋值newnode-val x;newnode-next NULL;//判断是不是第一次if (pq-ptail NULL){pq-phead pq-ptail newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;//记录元素}void QueuePop(Queue* pq)// 队头出队列
{assert(pq);assert(pq-phead);Queue* tmp pq-phead;//记录头指针方便释放空间pq-phead pq-phead-next;//让头指针指向下一个元素free(tmp);//释放头指针if (pq-phead NULL)//如果队列中只有一个元素将尾指针也置为空指针{pq-ptail NULL;}pq-size--;
}QDataType QueueFront(Queue* pq)// 获取队列头部元素
{assert(pq);assert(pq-phead);assert(pq-ptail);return pq-phead-val;
}QDataType QueueBack(Queue* pq)// 获取队列队尾元素
{assert(pq);assert(pq-phead);assert(pq-ptail);return pq-ptail-val;
}bool QueueEmpty(Queue* pq)// 检测队列是否为空如果为空返回非零结果如果非空返回0
{assert(pq);return pq-size 0;
}int QueueSize(Queue* pq)// 获取队列中有效元素个数
{assert(pq);return pq-size;
}void QueueDestory(Queue* pq)//销毁队列
{assert(pq);Queue* dl NULL;while (pq-phead){dl pq-phead;pq-phead pq-phead-next;free(dl);}pq-ptail NULL;pq-size 0;pq-phead NULL;
}#define _CRT_SECURE_NO_WARNINGS 1
#includeQueen.hvoid Test1()
{Queue sl;QueueInit(sl);QueuePush(sl, 1);//printf(%d\n, QueueFront(sl));QueuePush(sl, 9);//printf(%d\n,QueueFront(sl));//QueuePop(sl);QueuePush(sl, 2);QueuePush(sl, 10);printf(%d\n, QueueFront(sl));printf(%d\n,QueueBack(sl));
}void Test2()
{Queue s;QueueInit(s);QueuePush(s, 1);QueuePush(s, 2);QueuePush(s, 3);QueuePush(s, 4);QueuePush(s, 5);printf(%d , QueueFront(s)); printf(%d , QueueBack(s));printf(%d\n, QueueSize(s));QueuePop(s);QueuePop(s);printf(%d , QueueFront(s));printf(%d\n, QueueSize(s));if (!QueueEmpty(s)){QueuePop(s);printf(%d , QueueFront(s));printf(%d\n, QueueSize(s));}printf(%d\n, QueueSize(s));QueueDestory(s);
}int main()
{//Test1();Test2();return 0;
}结语今天的内容就到这里吧谢谢各位的观看如果有讲的不好的地方也请各位多多指出作者每一条评论都会读的谢谢各位。 祝各位接下来好运连连
