C语言：栈和队列

文章目录前言1. 栈1.1 栈的概念及结构1.2 栈的实现1.3 栈的C语言实现1.3.1 stack.h1.3.2 stack.c1.3.3 test.c2. 队列2.1 队列的概念及结构2.2 队列的实现2.2.1 Queue.h2.2.2 Queue.c2.2.3 test.c前言栈先进后出和队列先进先出是逻辑结构描述数据的组织和操作规则他们可以用顺序表数组、链表等存储结构描述数据在内存中的存储方式实现。1. 栈这里我将说明什么是栈和如何用C语言表示栈1.1 栈的概念及结构接下来引用两张图片1.2 栈的实现1.3 栈的C语言实现最主要的还是如何用C语言实现栈我们将代码分别分为stack.h , stack.c , 和 test.c 这里用动态顺序表实现。1.3.1 stack.h代码展示#pragmaonce#includestdio.h#includestdlib.h#includestdbool.h#includeassert.htypedefintSTDataType;typedefstructStack{STDataType*a;inttop;intcapacity;}ST//初始化和销毁voidSTInit(ST*pst);voidSTDestroy(ST*pst);//插入,入栈voidSTPush(ST*pst,STDataType x);//删除出栈voidSTPop(ST*pst);//获取栈顶数据STDataTypeSTTop(ST*pst);//判空boolSTEmpty(ST*pst);//intSTSize(ST*pst);STDataType* a动态数组的 “容器”存储栈的实际数据区别于静态栈的固定数组int top栈的 “位置标记”记录栈顶的位置是入栈 / 出栈的核心依据注意初始值定义int capacity栈的 “容量上限”跟踪动态数组的总大小用于判断是否需要扩容避免越界1.3.2 stack.c代码实现#includestack.hvoidSTInit(ST*pst){assert(pst);pst-aNULL;pst-capacity0;//top指向栈顶下一个元素pst-top0;}voidSTDestroy(ST*pst){assert(pst);free(pst-a);pst-aNULL;pst-capacitypst-top0;}//插入,入栈voidSTPush(ST*pst,STDataType x){assert(pst);if(pst-toppst-capacity){intnewcapacitypst-capacity0?4:pst-capacity*2;STDataType*tmp(STDataType*)realloc(pst-a,newcapacity*sizeof(STDataType));if(tmpNULL){perror(realloc fail);return;}pst-atmp;pst-capacitynewcapacity;}pst-a[pst-top]x;pst-top;}//删除出栈voidSTPop(ST*pst){assert(pst);pst-top--;}//获取栈顶数据STDataTypeSTTop(ST*pst){assert(pst);assert(pst-top0);returnpst-a[pst-top-1];}//判空boolSTEmpty(ST*pst){assert(pst);returnpst-top0;}//intSTSize(ST*pst){assert(pst);returnpst-top;}这里较为复杂的是入栈void STPush(ST* pst, STDataType x)需判断内存够不够再按需扩容1.3.3 test.c#includestack.hintmain(){ST s;STInit(s);STPush(s,1);STPush(s,2);STPush(s,3);while(!STEmpty(s)){printf(%d\n,STTop(s));STPop(s);}STDestroy(s);return0;}这里我只是随便测试一下大家可以按自己的想法测试。2. 队列2.1 队列的概念及结构2.2 队列的实现这里依旧把代码分为Queue.h , Queue.c , test.c 三部分。2.2.1 Queue.h#pragmaonce#define_CRT_SECURE_NO_WARNINGS// 链式结构表示队列#pragmaonce#includestdbool.h#includestdio.h#includestdlib.h#includeassert.htypedefintQDataType;typedefstructQListNode{structQListNode*next;QDataType data;}QNode;// 队列的结构typedefstructQueue{QNode*phead;QNode*ptail;intsize;}Queue;// 初始化队列voidQueueInit(Queue*q);// 队尾入队列voidQueuePush(Queue*q,QDataType data);// 队头出队列voidQueuePop(Queue*q);// 获取队列头部元素QDataTypeQueueFront(Queue*q);// 获取队列队尾元素QDataTypeQueueBack(Queue*q);// 获取队列中有效元素个数intQueueSize(Queue*q);// 检测队列是否为空如果为空返回非零结果如果非空返回0intQueueEmpty(Queue*q);// 销毁队列voidQueueDestroy(Queue*q);QNode是链式队列的数据载体每个节点存一个数据 下一个节点的指针串联成链表Queue是链式队列的管理核心phead/ptail直接定位头尾保证入队 / 出队O(1)效率size快速统计节点数链式队列的优势动态扩容无容量上限、无 “假溢出”区别于顺序队列的循环数组是实际开发中队列的主流实现方式。size可直接计算链表结点个数2.2.2 Queue.c#define_CRT_SECURE_NO_WARNINGS#includeQueue.hvoidQueueInit(Queue*q){assert(q);q-pheadNULL;q-ptailNULL;q-size0;}// 队尾入队列voidQueuePush(Queue*q,QDataType data){QNode*node(QNode*)malloc(sizeof(QNode));if(nodeNULL){perror(malloc fail);return;}node-nextNULL;node-datadata;if(q-pheadNULL){q-pheadnode;q-ptailnode;}else{q-ptail-nextnode;q-ptailnode;}q-size;}// 队头出队列voidQueuePop(Queue*q){assert(q);assert(q-size!0);QNode*mq-phead-next;if(q-pheadq-ptail)q-ptailNULL;free(q-phead);q-pheadm;q-size--;}//// 获取队列头部元素QDataTypeQueueFront(Queue*q){assert(q);returnq-phead-data;}//// 获取队列队尾元素QDataTypeQueueBack(Queue*q){assert(q);returnq-ptail-data;}//// 获取队列中有效元素个数intQueueSize(Queue*q){returnq-size;}//// 检测队列是否为空如果为空返回非零结果如果非空返回0intQueueEmpty(Queue*q){if(q-phead!NULL){return0;}return1;}//// 销毁队列voidQueueDestroy(Queue*q){assert(q);QNode*nodeq-phead;while(node){QNode*nextnode-next;free(node);nodenext;}q-pheadq-ptailNULL;q-size0;}2.2.3 test.c#includeQueue.hintmain(){Queue q;QueueInit(q);QueuePush(q,1);QueuePush(q,2);QueuePush(q,3);QueuePush(q,4);while(!QueueEmpty(q)){printf(%d ,QueueFront(q));QueuePop(q);}return0;}大家可刷题熟悉这两种逻辑结构