数据结构体栈和队列的实现
前言:
关于c语言的学习已经差不多更新完毕,如果发现个别知识点,我还会继续更新,但目前已经准备往c 和数据结构的重心挪动,这篇文章就是向大家讲述数据结构中栈和队列的实现。
你来人间一趟,你要看看太阳!!!!
目录
一、数据结构体栈
1.1栈的概念及结构:
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
~~~~记住一个原则,先进的后出,后进的先出。~~~~
1.2栈的实现:
栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。我们保证首先插入的后面出来就行。
1.2.1栈的定义:
-
typedef int STDataType; //重定义int
-
typedef struct Stack{
-
STDataType* a;
-
STDataType top; //栈顶
-
STDataType capicity;
-
-
}ST;
1.2.2栈的初始化:
-
void StackInit(ST*ps)
-
{
-
assert(ps);
-
ps->a=NULL; //先指向空指针
-
ps->top=ps->capicity=0; 初始化都为零
-
}
1.2.3栈的销毁:
-
void StackDestroy(ST*ps)
-
{
-
assert(ps); //断言一下防止空指针
-
free(ps); //进行释放因为我申请的是动态内存
-
ps=NULL;
-
ps->top=0;
-
ps->capicity=0;
-
}
1.2.4判断栈是否为空:
-
bool StackEmpty(ST*ps)
-
{
-
assert(ps);
-
return ps->top==0; //如果top等于0则证明栈为空,返回true
-
}
1.2.5栈的压栈(push):
-
void StackPush(ST*ps,STDataType x)
-
{
-
assert(ps); //断言一下
-
if(ps->top==ps->capicity) //如果top(栈顶)=capacity则证明容量已经满了需要扩容一下
-
{
-
int newcapicity=ps->capicity==0?4:(ps->capicity)*2; //和顺序表扩容一样
-
STDataType* ptr = (STDataType*)realloc(ps->a, newcapicity*sizeof(STDataType)); //进行动态扩容
-
if(ptr==NULL) //防止扩容失败
-
{
-
perror("StackPush");
-
exit(-1);
-
}
-
ps->a=ptr; //把扩容成功的地址传给a
-
ps->capicity=newcapicity; //把扩容后的新newcapicity给capacity
-
}
-
ps->a[ps->top]=x; // 插入元素x
-
ps->top; //top进行
-
}
1.2.6栈的出栈(Pop):
-
void StackPop(ST*ps)
-
{
-
assert(ps);
-
assert(!StackEmpty(ps)); //这里判断是否为空栈如果为空栈就不能在进行出栈了
-
--ps->top; //只需要让top减一个就行了
-
}
1.2.7栈顶的元素查看:
-
STDataType StackTop(ST* ps)
-
{
-
assert(ps);
-
assert(!StackEmpty(ps));
-
-
return ps->a[ps->top - 1]; //因为进行push后top 了一下,所以栈顶需要top-1
-
}
1.2.7栈的元素个数:
-
int StackSize(ST* ps)
-
{
-
assert(ps);
-
-
return ps->top;
-
}
栈还是比较容易实现的,如果熟练掌握顺序表我相信大家还是很容易就能把栈写出来。
1.3栈实现的全部代码:
1.3.1 .c
-
-
void StackInit(ST*ps)
-
{
-
assert(ps);
-
ps->a=NULL;
-
ps->top=ps->capicity=0;
-
}
-
void StackDestroy(ST*ps)
-
{
-
assert(ps);
-
free(ps);
-
ps=NULL;
-
ps->top=0;
-
ps->capicity=0;
-
}
-
void StackPush(ST*ps,STDataType x)
-
{
-
assert(ps);
-
-
-
if(ps->top==ps->capicity)
-
{
-
int newcapicity=ps->capicity==0?4:(ps->capicity)*2;
-
STDataType* ptr = (STDataType*)realloc(ps->a, newcapicity*sizeof(STDataType));
-
if(ptr==NULL)
-
{
-
perror("StackPush");
-
exit(-1);
-
}
-
ps->a=ptr;
-
ps->capicity=newcapicity;
-
}
-
ps->a[ps->top]=x;
-
ps->top;
-
}
-
bool StackEmpty(ST*ps)
-
{
-
assert(ps);
-
return ps->top==0;
-
}
-
void StackPop(ST*ps)
-
{
-
assert(ps);
-
assert(!StackEmpty(ps));
-
--ps->top;
-
}
-
STDataType StackTop(ST* ps)
-
{
-
assert(ps);
-
assert(!StackEmpty(ps));
-
-
return ps->a[ps->top - 1];
-
}
-
int StackSize(ST* ps)
-
{
-
assert(ps);
-
-
return ps->top;
-
}
1.3.2 .h
-
-
-
-
-
-
-
-
typedef int STDataType;
-
typedef struct Stack{
-
STDataType* a;
-
STDataType top;
-
STDataType capicity;
-
-
}ST;
-
void StackInit(ST*ps);
-
void StackDestroy(ST*ps);
-
void StackPush(ST*ps,STDataType x);
-
void StackPop(ST*ps);
-
bool StackEmpty(ST*ps);
-
STDataType StackTop(ST* ps);
-
int StackSize(ST* ps);
-
-
1.3.3 test
测试我这里是随便测试了一下,大家可以自己进行不同的测试就行不必和我一样
-
-
void TestStack()
-
{
-
ST st;
-
StackInit(&st);
-
StackPush(&st, 1);
-
StackPush(&st, 2);
-
StackPush(&st, 3);
-
printf("%d ", StackTop(&st));
-
printf("%d ",StackSize(&st));
-
StackPop(&st);
-
//printf("%d ", StackTop(&st));
-
StackPop(&st);
-
-
StackPush(&st, 4);
-
StackPush(&st, 5);
-
-
while (!StackEmpty(&st))
-
{
-
printf("%d ", StackTop(&st));
-
StackPop(&st);
-
}
-
printf("\n");
-
}
-
-
int main()
-
{
-
TestStack();
-
return 0;
-
}
二、数据结构队列:
2.1数列的概念和结构:
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出 FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头。 队列和栈的区别就是先进的后出,就和排队买东西一样,先排队的先买,说白了就是先到先得。
2.2队列的实现:
队列要用到头删,因为第一个进入的要第一个删除,这样用数组就不太合适,因为数组的头删是0(n),时间复杂度比较大,这里我们用链表就是比较合适的选择。
2.2.1队列的定义:
-
typedef int QDataType;
-
typedef struct QueueNode
-
{
-
struct QueueNode*next;
-
QDataType data;
-
}QNode;
-
typedef struct Queue
-
{
-
QNode* head; //队列要有一个头
-
QNode* rear; //队列要有一个尾
-
int size;
-
}Queue;
2.2.2队列的初始化:
-
void QueueInit(Queue*pq)
-
{
-
assert(pq); //断言防止传入空指针
-
pq->head=NULL;
-
pq->rear=NULL;
-
pq->size=0;
-
}
2.2.3队列的销毁:
-
void QueueDestroy(Queue*pq)
-
{
-
assert(pq);
-
QNode *cur=pq->head; //定一个节点进行遍历一个个销毁
-
while(cur)
-
{
-
QNode *del=cur;
-
free(cur);
-
cur=del->next;
-
}
-
pq->head=NULL;
-
pq->rear=NULL;
-
}
2.2.4队列判断是否为空:
-
bool QueueEmpty(Queue* pq)
-
{
-
assert(pq);
-
return pq->head == NULL && pq->rear == NULL;
-
}
2.2.5队列插入(push):
-
void QueuePush(Queue* pq, QDataType x)
-
{
-
assert(pq);
-
QNode*newnode=(QNode*)malloc(sizeof(QNode)); //插入前先创建一个节点
-
if(newnode==NULL) //这是判断是否申请成功
-
{
-
perror("newnode");
-
exit(-1);
-
}
-
else
-
{
-
newnode->data=x;
-
newnode->next=NULL;
-
}
-
if(pq->rear==NULL) //两种情况这是尾节点位空的时候
-
{
-
pq->rear=pq->head=newnode;
-
}
-
else //这是尾节点不为空的时候
-
{
-
pq->rear->next=newnode;
-
pq->rear=newnode;
-
}
-
pq->size ;
-
}
2.2.6队列出队(Pop):
-
void QueuePop(Queue* pq)
-
{
-
assert(pq);
-
assert(!QueueEmpty(pq)); //判断队列是否为空
-
if(pq->head->next==NULL) //如果只有一个头节点情况
-
{
-
free(pq->head);
-
pq->head=pq->rear=NULL;
-
}
-
else //不止只有头节点的情况
-
{
-
QNode* del;
-
del=pq->head;
-
pq->head=pq->head->next;
-
free(del);
-
del=NULL;
-
}
-
pq->size--;
-
}
2.2.7队头元素:
-
QDataType QueueFront(Queue* pq)
-
{
-
assert(pq);
-
assert(!QueueEmpty(pq));
-
-
return pq->head->data;
-
}
2.2.8队尾元素:
-
QDataType QueueBack(Queue* pq)
-
{
-
assert(pq);
-
assert(!QueueEmpty(pq));
-
return pq->rear->data;
-
}
2.2.9队的人员个数:
-
int QueueSize(Queue* pq)
-
{
-
assert(pq);
-
return pq->size;
-
}
2.3队列实现的全部代码:
2.3.1 .c
-
-
void QueueInit(Queue*pq)
-
{
-
assert(pq);
-
pq->head=NULL;
-
pq->rear=NULL;
-
pq->size=0;
-
}
-
void QueueDestroy(Queue*pq)
-
{
-
assert(pq);
-
-
QNode *cur=pq->head;
-
while(cur)
-
{
-
QNode *del=cur;
-
free(cur);
-
cur=del->next;
-
}
-
pq->head=NULL;
-
pq->rear=NULL;
-
}
-
void QueuePush(Queue* pq, QDataType x)
-
{
-
assert(pq);
-
QNode*newnode=(QNode*)malloc(sizeof(QNode));
-
if(newnode==NULL)
-
{
-
perror("newnode");
-
exit(-1);
-
}
-
else
-
{
-
newnode->data=x;
-
newnode->next=NULL;
-
}
-
if(pq->rear==NULL)
-
{
-
pq->rear=pq->head=newnode;
-
}
-
else
-
{
-
pq->rear->next=newnode;
-
pq->rear=newnode;
-
}
-
pq->size ;
-
}
-
void QueuePop(Queue* pq)
-
{
-
assert(pq);
-
assert(!QueueEmpty(pq));
-
if(pq->head->next==NULL)
-
{
-
free(pq->head);
-
pq->head=pq->rear=NULL;
-
}
-
else{
-
QNode* del;
-
del=pq->head;
-
pq->head=pq->head->next;
-
free(del);
-
del=NULL;
-
}
-
pq->size--;
-
}
-
bool QueueEmpty(Queue* pq)
-
{
-
assert(pq);
-
return pq->head == NULL && pq->rear == NULL;
-
}
-
QDataType QueueFront(Queue* pq)
-
{
-
assert(pq);
-
assert(!QueueEmpty(pq));
-
-
return pq->head->data;
-
}
-
-
QDataType QueueBack(Queue* pq)
-
{
-
assert(pq);
-
assert(!QueueEmpty(pq));
-
return pq->rear->data;
-
}
-
int QueueSize(Queue* pq)
-
{
-
assert(pq);
-
return pq->size;
-
}
2.3.2 .h
-
-
-
-
-
-
-
-
-
typedef int QDataType;
-
typedef struct QueueNode
-
{
-
struct QueueNode*next;
-
QDataType data;
-
}QNode;
-
typedef struct Queue
-
{
-
QNode* head;
-
QNode* rear;
-
int size;
-
}Queue;
-
void QueueInit(Queue*pq);
-
void QueueDestroy(Queue*pq);
-
void QueuePush(Queue* pq, QDataType x);
-
void QueuePop(Queue* pq);
-
bool QueueEmpty(Queue* pq);
-
QDataType QueueFront(Queue* pq);
-
QDataType QueueBack(Queue* pq);
-
int QueueSize(Queue* pq);
-
-
-
-
2.3.3 test
-
-
void test()
-
{
-
Queue q;
-
QueuePush(&q,1);
-
QueuePush(&q,2);
-
QueuePush(&q,3);
-
QueuePush(&q,4);
-
QueuePush(&q,5);
-
printf("%d \n",QueueSize(&q));
-
printf("%d ",QueueFront(&q));
-
QueuePop(&q);
-
printf("%d ",QueueFront(&q));
-
QueuePop(&q);
-
printf("%d ",QueueFront(&q));
-
printf("%d ",QueueBack(&q));
-
-
QueueDestroy(&q);
-
-
}
-
int main()
-
{
-
test();
-
return 0;
-
}
3、总结:
关于栈和队列是数据结构中比较重要的一点,这篇博客我把栈和队列的实现全部写出来了,同时最后有他全部的代码,但我的建议是大家可以尝试一下自己去完成栈和队列的代码实现,在实现过程中也就是我们的学习过程!!!!!!!
最后小马码文不易,如果觉得有帮助就多多支持哈!!!^ _ ^
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgfakic
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
怎样阻止微信小程序自动打开
PHP中文网 06-13 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01