上海做壁画的网站,2345网址导航手机版下载安装,深圳牌匾制作,网站建设策划目的及过程也是好久没写博客了#xff0c;那今天就回归一下#xff0c;写一篇数据结构的博客吧。今天要写的是栈和队列#xff0c;也是数据结构中比较基础的知识。那么下面开始今天要写的博客了。
目录
栈#xff08;Stack#xff09;
队列#xff08;Queue#xff09; 喜欢就点…也是好久没写博客了那今天就回归一下写一篇数据结构的博客吧。今天要写的是栈和队列也是数据结构中比较基础的知识。那么下面开始今天要写的博客了。
目录
栈Stack
队列Queue 喜欢就点个赞吧。 栈Stack
栈一种特殊的线性表其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除 操作的一端称为栈顶另一端称为栈底。栈中的数据元素遵守后进先出LIFOLast In First Out 的原则。 压栈栈的插入操作叫做进栈/压栈/入栈入数据在栈顶。
出栈栈的删除操作叫做出栈。出数据也在栈顶。
简单描述栈的特点栈数据的增删都是在一头进行即在栈顶 那栈又该如何创建与使用呢他的原理又是怎样的这里我们就用C语言实现一下。
我们这里就要想这个栈是要用数组来实现还是用链表来实现呢其实我们可以从其功能开始思考这两者哪个更好去实现栈的功能而且效率较高其实说到这里很多人可能已经有了结果其实要说简洁与效率数组更适合来做栈。那么我们下面就来完成一下这个代码完成一个栈。
这里先给头文件因为其中有typedef来命名的类型以免各位佬看得迷惑。
头文件
这里解释一下DataType是各位做栈时储存数据的类型需要改变时只需要在头文件里改动一下即可例如你想变成char类型的数据即可将typedef int DataType; 改为 typedef char DataType; 然后栈的结构体我们就用ST来简化方便写代码。
然后top为栈的数据个数capacity就表示栈的容量
#pragma once
#include stdio.h
#include stdbool.h
#include assert.h
#include stdlib.h
typedef int DataType;typedef struct Stack
{DataType* a;int top;int capacity;}ST;void StackInit(ST* ps);
void StackDestory(ST* ps);
// 入栈
void StackPush(ST* ps, DataType x);
// 出栈
void StackPop(ST* ps);
DataType StackTop(ST* ps);int StackSize(ST* ps);
bool StackEmpty(ST* ps); 栈的格式化
void StackInit(ST* ps)
{assret(ps);ps-a (DataType)mallco(4 * (sizeof(DataType)));if (ps-a NULL){printf(malloc fail\n);exit(-1);}ps-capacity 4;ps-top 0;}
先将数组a mallco出四个数据的大小然后将容量capacity改为4. 栈的销毁
void StackDestory(ST* ps){assert(ps);free(ps-a);ps-a NULL;ps-top ps-capacity 0;}使用完栈后进行销毁得函数防止内存泄露。 及时free掉然后将a指向NULL。 入栈
void StackPush(ST* ps, DataType x)
{assert(ps);if (ps-top ps-capacity){DataType* tem (DataType*)recalloc(ps-a, 2*ps-capacity*sizeof(DataType));if (tem NULL){printf(racallco fail\n);}else{ps-a tem;ps-capacity 2 * ps-capacity;}}ps-a[ps-top] x;ps-top;}
第一个if先判断数组a是否还有空间入栈如果满了就进行recallco增容即可增容我们现在时增容两倍较为合适recallco的用法在前面动态内存创建的文章已经讲过了。所以现在就不多解释了。入栈后记得将top一下 。 出栈
void StackPop(ST* ps)
{assert(ps);assert(ps-top 0);ps-top--;
}
这里就比较简单粗暴将top--即可将原本栈顶得书局给屏蔽即可。 求栈的长度和判断栈是否为空
int StackSize(ST* ps)
{assert(ps);return ps-top;
}bool StackEmpty(ST* ps)
{assert(ps);return ps-top 0;
} 接下来我们就来看看队列 队列Queue
队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先 进先出FIFO(First In First Out) 队列的特点队列与栈的不同是他是在一头进行增数据一头删数据而栈数据的增删都是在一头。 然后我们思考一下队列的功能实现是要数组好还是链表好呢这么一想是不是马上就发现了如果们还是用数组来实现的话那么其出队列的时间复杂度为ON那么效率太低了而链表实现的话则是O1显而易队列还是用链表实现较好。 下面就是队列函数的实现了。
还是先给大家看看头文件
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
#include stdbool.h
#include assert.h
#include stdlib.htypedef int Type;typedef struct Queuenode
{Type* date;struct Queue* next;}Node;typedef struct Queue
{Node* head;Node* tail;
}Queue;void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);// 队尾入
void QueuePush(Queue* pq, Type x);
// 队头出
void QueuePop(Queue* pq);
这里解释一下为什么创建了两个结构体 因为其中一个作为链表的节点而另一个队列结构体。队列的结构体我们只需要要一个队头和队尾。 队列的格式化 void QueueInit(Queue* pq)
{assert(pq);pq-head NULL;pq-tail NULL;}很简单将队头和队尾指向空NULL即可。 队列的销毁 void QueueDestory(Queue* pq)
{assert(pq);Node* cur pq-head;while (cur){Node* next cur-next;free(cur);cur next;}pq-head pq-tail NULL;} 这里我们运用一个while循环创建一个辅助指针来保存节点的下一个。不断free 掉即可。
注意要将队头和队尾指空NULL。 进队 void QueuePush(Queue* pq, Type x)
{assert(pq);Node* new (Node*)mallco(sizeof(Node));if (new NULL){printf(mallco fail\n);}new-date x;new-next NULL;if (pq-tail NULL){pq-tail new;pq-head new;}else{pq-tail-next new;pq-tail new;}}我们mallco一个空间作为进队的一个节点然后对节点进行赋值然后对链表进行尾插就完成了一半了。
需要注意的是记得把原来的tail的next 指向新节点也要把tail改为 新节点因为尾插后new就为最后的节点也就是尾了。注意当前有没有节点那将head和tail至为new即可。 出队
void QueuePop(Queue* pq)
{assert(pq);assert(pq-head);if (pq-head-next NULL){free(pq-head);pq-head NULL;pq-tail NULL;}Node* next pq-head-next;free(pq-head);pq-head next;} 这里也是根据队列的删数据特点这里的出队就是头删了我们先把head的next保存住然后free掉head再然后让next作为新的头。 今天就结束了希望您能喜欢这篇文章。
