目录

• 栈
• 数组实现
• 标题全部代码
• Stack_array.c
• Stack_array.h
• 初始化数组栈
• 满栈后扩容
• 是否为空栈
• 压栈和退栈
• 链表实现
• stack_chain.h
• stack_chain.c
• 整个压栈流程
• 整个弹栈流程
• 出栈情况
• 队列
• 队列的实现
• queue_chain.h
• queue_chain.c
• 一个结构体类型用于维护这个队列
• 概念流程图
• 入队列的实现
• 出队列的实现
• 是否空队

栈 栈是一种以后进先出为顺序对对象进行添加或删除的数据结构
对栈进行形象记忆就像是桌子上的一堆书或一堆盘。对盘子取或者存盘子，都只能对最上面的书或者盘子进行操作。

文章图片

对于栈而言，只有弹栈才能获取其数据。
当我们用C语言实现栈这个数据结构。
其实有三种方法实现
1，数组
2，单链表
3，双向链表
但是，对于双向链表，实现栈而言过于复杂。
可以选择数组或者单链表。

数组实现

标题全部代码

Stack_array.c

#include "Stack_array.h"void InitStack(STstack* st)//栈的初始化{ st->top = 0; st->arr = (STData*)malloc(CAP*sizeof(STData)); st->capacity = CAP; }void StackPush(STstack* st, STData n)//元素入栈{ if (st->top == st->capacity)//判断是否需要扩容 {StackExpansion(st); } st->arr[st->top++] = n; }STData StackPop(STstack* st)//元素退栈{ assert(st); assert(!StackEmpty(st)); //判断是否为空栈 return st->arr[--st->top]; }int StackEmpty(STstack* st)//判断栈是否为空{ if (st->top == 0)return 1; return 0; }void StackDestory(STstack* st)//销毁栈，防止内存泄漏{ free(st->arr); st->arr = NULL; }void StackExpansion(STstack* st)//扩容{ STData* tmp = (STData*)realloc((STData*)st->arr, sizeof(STData) * (st->capacity) * 2); if (tmp == NULL) {printf("Exparsion Error\n"); exit(-1); } st->arr = tmp; st->capacity *= 2; }void StackPrint(STstack* st)//打印栈的元素，但前提是要退栈才能得到元素{ while(st->top) {STData ret = StackPop(st); printf("%d ", ret); }}

Stack_array.h

#pragma once#define _CRT_SECURE_NO_WARNINGS#include #include #include #define CAP 4typedef int STData; typedef struct Stack//结构体用于维护栈{ int top; //栈顶标记 STData* arr; //栈的指针 int capacity; //栈的容量}STstack; void InitStack(STstack* st); //栈的初始化void StackPush(STstack* st, STData n); //元素入栈STData StackPop(STstack* st); //元素退栈void StackExpansion(STstack* st); //扩容int StackEmpty(STstack* st); //判断栈是否为空void StackDestory(STstack* st); //销毁栈，防止内存泄漏void StackPrint(STstack* st); //打印栈的元素，但前提是要退栈才能得到元素

对于数组实现而言。创建一个结构体用于维护整个栈。而其中有一个用于链接创建的数组。

typedef int STData; typedef struct Stack//结构体用于维护栈{ int top; //栈顶标记 STData* arr; //栈的指针 int capacity; //栈的容量}STstack;

作为数组栈，需要一个动态的数组。则这就需要一个Capacity作为衡量是否需要扩容的标准。而top需要作为入栈元素的位置。
当top的值等于Capacity时就意味着栈已经满了。因为数组是从0开始的

文章图片


初始化数组栈 在初始化时，要先动态开辟一个数组空间，且，未压栈压入数据元素，其top要设为0.要保证当需要压栈时有明确指定的空间。同时，top的位置要为最后压入数据的下一个下标。

void InitStack(STstack* st)//栈的初始化{ st->top = 0; st->arr = (STData*)malloc(CAP*sizeof(STData)); st->capacity = CAP; }

满栈后扩容 其Capacity要作为判断是否满栈的标准。且，满栈后要进行扩容（因为是动态数组）。

void StackExpansion(STstack* st)//扩容{ STData* tmp = (STData*)realloc((STData*)st->arr, sizeof(STData) * (st->capacity) * 2); if (tmp == NULL) {printf("Exparsion Error\n"); exit(-1); } st->arr = tmp; st->capacity *= 2; }

同时，还要每次更改栈的容量，为下一次是否满栈作为标准。

是否为空栈

int StackEmpty(STstack* st)//判断栈是否为空{ if (st->top == 0)return 1; return 0; }

其是否为空。也就是top的位置在数组的0下标位。

压栈和退栈

void StackPush(STstack* st, STData n)//元素入栈{ if (st->top == st->capacity)//判断是否需要扩容 {StackExpansion(st); } st->arr[st->top++] = n; }STData StackPop(STstack* st)//元素退栈{ assert(st); assert(!StackEmpty(st)); //判断是否为空栈 return st->arr[--st->top]; }

压栈
每次压栈，都需要判断是否满栈，并决定是否扩容。
同时，当在原先top位置的数位置进行赋值。并之后要将top向后移动一个位置。保证下一次压栈。
退栈
退栈返回top的上一个位置的元素。同时top向前移动一个位置，不需要free，下次压栈会自动覆盖。

链表实现
stack_chain.h

#include #include #define N 3typedef struct stackele{ int n; int* point; }sta; sta* top; void initstack(sta* a); //初始化栈void pushstack(sta* a,int num); //入栈//void printstack(sta* a); //打印栈//void fullstack(sta* a); //检查是否满栈的情况void emptystack(sta* a); //检查是否空栈的情况int popstack(sta*a); //出栈

stack_chain.c

#include "stack_chain.h"void initstack(sta* a)//初始化栈{ top= NULL; }void pushstack(sta* a, int num)//入栈{ sta* p = (sta*)malloc(sizeof(sta)); p->n = num; //新节点赋值 p->point = top; top = p; }int popstack(sta* a)//出栈{ emptystack(a); //检查是否空栈的情况 int date; sta* des = top; top = top->point; date = des->n; free(des); des = NULL; return date; }void emptystack(sta* a)//检查是否空栈的情况{ if (top == NULL) {printf("Stack empty"); exit(0); }}

对于链表实现栈而言，和数组其实差不多。只不够，每次压栈都需要重新动态开辟一个新节点，并且链入栈中。但是，这并不是普通的直接链入。而是需要头插入栈。

文章图片

这样头插入栈，可以方便退栈的时候，可以找到上一个元素。而压栈是不需要什么顺序。每一个压栈节点就是top节点。

整个压栈流程

文章图片

void pushstack(sta* a, int num)//入栈{ sta* p = (sta*)malloc(sizeof(sta)); p->n = num; //新节点赋值 p->point = top; top = p; }

整个弹栈流程

文章图片

int popstack(sta* a)//出栈{ emptystack(a); //检查是否空栈的情况 int date; sta* des = top; top = top->point; date = des->n; free(des); des = NULL; return date; }

出栈情况
尤其要把握一个条件：空栈
由于不是数组，且链式结构的特性，是不需要扩容的。即不需要判断满栈的情况。
只考虑空栈的条件

void emptystack(sta* a)//检查是否空栈的情况{ if (top == NULL) {printf("Stack empty"); exit(0); }}

这里空栈的条件是top指针指向NULL时也就是

文章图片

为什么呢？
因为每次弹栈的时候，都会free掉top指向的空间然后让top指向下一个节点。就这样不断移动。但是我设计初始化的时候是top= NULL; 而且每次压栈都是p->point = top; 这就会有一个标准来限定空栈的情况。
对于栈而言，其更像是一个递归的具象化。

队列
文章图片

这种数据结构就像是银行柜台的取号机，
先取号的先去柜台。
始终满足先入先出的概念

队列的实现

queue_chain.h

#define _CRT_SECURE_NO_WARNINGS#include #include #include typedef int QUData; typedef struct queue{ QUData data; struct queue* next; }queue; typedef struct Queue//结构体用于维护队列{ queue* Dequeue; //队头指针 queue* Enqueue; //队尾指针}QUqueue; void InitQueue(QUqueue* qu); //栈的初始化void QueuePush(QUqueue* qu, QUData n); //元素入队QUData QueuePop(QUqueue* qu); //元素出队int QueueEmpty(QUqueue* qu); //判断队列是否为空void QueueDestory(QUqueue* qu); //销毁队，防止内存泄漏void QueuePrint(QUqueue* qu); //打印队列中的元素，但前提是要出队才能得到元素

queue_chain.c

#include "queue_chain.h"void InitQueue(QUqueue* qu)//队列的初始化{ qu->Dequeue = qu->Enqueue = NULL; }void QueuePush(QUqueue* qu, QUData n)//元素入队{ queue* newcell = (QUData*)malloc(sizeof(QUData)); newcell->data = https://www.it610.com/article/n; newcell->next = NULL; if (qu->Dequeue == NULL) {qu->Enqueue = qu->Dequeue = newcell; } else {qu->Enqueue->next = newcell; qu->Enqueue = newcell; }}QUData QueuePop(QUqueue* qu)//元素出队{ if (QueueEmpty(qu)) {printf("Queue Is Empty"); exit(-1); } QUData ret = qu->Dequeue->data; qu->Dequeue = qu->Dequeue->next; return ret; }int QueueEmpty(QUqueue* qu)//判断队列是否为空{ if (qu->Dequeue == qu->Enqueue)return 1; return 0; }void QueueDestory(QUqueue* qu)//销毁队，防止内存泄漏{ queue* cur = qu->Dequeue; while (cur) {queue* pnext = cur->next; free(cur); cur = pnext; } qu->Dequeue = qu->Enqueue = NULL; }void QueuePrint(QUqueue* qu)//打印队列中的元素，但前提是要出队才能得到元素{ queue* cur = qu->Dequeue; while (cur) {printf("%d ", cur->data); cur = cur->next; }}

队 毕竟是先入先出的数据结构。
所以要两个指针，
qu->Dequeue 指向队头，
qu->Enqueue 指向队尾，
不然每次都去找队尾是相当浪费时间的。

一个结构体类型用于维护这个队列

typedef int QUData; typedef struct queue//描述每个队的元素{ QUData data; struct queue* next; }queue; typedef struct Queue//结构体用于维护队列{ queue* Dequeue; //队头指针 queue* Enqueue; //队尾指针}QUqueue;

队头指针负责出队，
队尾指针负责入队。

概念流程图
入队

文章图片


文章图片


文章图片


文章图片


入队列的实现

void QueuePush(QUqueue* qu, QUData n)//元素入队{ queue* newcell = (QUData*)malloc(sizeof(QUData)); newcell->data = https://www.it610.com/article/n; newcell->next = NULL; if (qu->Dequeue == NULL) {qu->Enqueue = qu->Dequeue = newcell; } else {qu->Enqueue->next = newcell; qu->Enqueue = newcell; }}

**当然，入队列在刚开始的时候，头尾指针还是一起指向NULL。
当入第一个元素时，那个元素即是第一个元素也是最后一个元素。要独立判断。**这是一个特殊情况。
出队

文章图片


文章图片


文章图片


出队列的实现

QUData QueuePop(QUqueue* qu)//元素出队{ if (QueueEmpty(qu)) {printf("Queue Is Empty"); exit(-1); } QUData ret = qu->Dequeue->data; qu->Dequeue = qu->Dequeue->next; return ret; }

但是每次出队列都需要判断是否为空队。如果是空队还继续出队会相当于NULL->next ,这是直接报错的。
所以还要一个函数判断是否空队。

是否空队

int QueueEmpty(QUqueue* qu)//判断队列是否为空{ if (qu->Dequeue == qu->Enqueue)return 1; return 0; }

空队就是相当于回到了初始化的情形

qu->Dequeue = qu->Enqueue = NULL;

也就是两者都指向同一处，也就是NULL。
以上就是C语言编程数据结构的栈和队列的详细内容，更多关于C语言数据结构的资料请关注脚本之家其它相关文章！
【C语言编程数据结构的栈和队列】感谢观看~

推荐阅读

• 

  岩鹿乳康片儿的功效与作用,请问岩鹿乳康胶囊的作用是什么？
• 

  qq小世界关闭教程
• 

  有些人看恐怖片的时候总是想笑是什么原因？
• 

  惊蛰时节养生粥及饮食注意事项 惊蛰吃什么粥
• 

  林内采暖炉代码10故障原因和解决方法,并不是那么的高深莫测
• 

  qqny是啥意思衣服 qqny是啥意思什么东西
• 

  灌篮高手里面人物是以NBA的人物为原型吗？
• 

  谨记在心，夏季喝酒五条法则，条条都在保护你的健康
• 

  西瓜英语怎么读
• 

  鲜榨果汁怎么储存 鲜榨果汁储存方法
• 

  课堂ppt怎么导入，ppt课程导入
• 

  流感疫苗能预防普通感冒吗？
• 

  遇到西门子的冰箱怎么门关不紧怎么办,本文告诉你原因
• 

  内蒙有哪些特产特产内蒙特产有哪些
• 

  Win10系统升级后如何释放C盘空间
• 

  公众号文章如何提升阅读量（一）——好的文章应该具有哪些特征
• 

  牛油果怎么吃减肥
• 

  武隆向60岁以上老年人免费发放健康包 武隆向60岁以上老年人免费发放健康包
• 

  冒死尝试几个用于ALC▲TEL OT355的PHILIPS秘籍
• 

  衡阳市在湖南的排名如何？

• 热闹中的孤独
• JAVA（抽象类与接口的区别&重载与重写&内存泄漏）
• 放屁有这三个特征的，请注意啦！这说明你的身体毒素太多
• 一个人的旅行，三亚
• 布丽吉特，人生绝对的赢家
• 慢慢的美丽
• 尽力
• 一个小故事，我的思考。
• 家乡的那条小河
• 《真与假的困惑》???|《真与假的困惑》??? ——致良知是一种伟大的力量