C语言：栈和队列-洪萨配资

文章目录

- 前言
1. 栈
- 1.1 栈的概念及结构
- 1.2 栈的实现
- 1.3 栈的C语言实现
- - 1.3.1 stack.h
  - 1.3.2 stack.c
  - 1.3.3 test.c
2. 队列
- 2.1 队列的概念及结构
- 2.2 队列的实现
- - 2.2.1 Queue.h
  - 2.2.2 Queue.c
  - 2.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#include<stdio.h>#include<stdlib.h>#include<stdbool.h>#include<assert.h>typedefintSTDataType;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

代码实现：

#include"stack.h"voidSTInit(ST*pst){assert(pst);pst->a=NULL;pst->capacity=0;//top指向栈顶下一个元素pst->top=0;}voidSTDestroy(ST*pst){assert(pst);free(pst->a);pst->a=NULL;pst->capacity=pst->top=0;}//插入,入栈voidSTPush(ST*pst,STDataType x){assert(pst);if(pst->top==pst->capacity){intnewcapacity=pst->capacity==0?4:pst->capacity*2;STDataType*tmp=(STDataType*)realloc(pst->a,newcapacity*sizeof(STDataType));if(tmp==NULL){perror("realloc fail");return;}pst->a=tmp;pst->capacity=newcapacity;}pst->a[pst->top]=x;pst->top++;}//删除，出栈voidSTPop(ST*pst){assert(pst);pst->top--;}//获取栈顶数据STDataTypeSTTop(ST*pst){assert(pst);assert(pst->top>0);returnpst->a[pst->top-1];}//判空boolSTEmpty(ST*pst){assert(pst);returnpst->top==0;}//intSTSize(ST*pst){assert(pst);returnpst->top;}

这里较为复杂的是入栈void STPush(ST* pst, STDataType x)，需判断内存够不够，再按需扩容！

1.3.3 test.c

#include"stack.h"intmain(){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#include<stdbool.h>#include<stdio.h>#include<stdlib.h>#include<assert.h>typedefintQDataType;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#include"Queue.h"voidQueueInit(Queue*q){assert(q);q->phead=NULL;q->ptail=NULL;q->size=0;}// 队尾入队列voidQueuePush(Queue*q,QDataType data){QNode*node=(QNode*)malloc(sizeof(QNode));if(node==NULL){perror("malloc fail");return;}node->next=NULL;node->data=data;if(q->phead==NULL){q->phead=node;q->ptail=node;}else{q->ptail->next=node;q->ptail=node;}q->size++;}// 队头出队列voidQueuePop(Queue*q){assert(q);assert(q->size!=0);QNode*m=q->phead->next;if(q->phead==q->ptail)q->ptail=NULL;free(q->phead);q->phead=m;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*node=q->phead;while(node){QNode*next=node->next;free(node);node=next;}q->phead=q->ptail=NULL;q->size=0;}

2.2.3 test.c

#include"Queue.h"intmain(){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;}