༺ 个人主页 · 纪念229 ༻
༺世上本没有路，走的人多了自然就有了༻
这篇文章讲述的是用顺序表实现栈、用单链表实现队列，本文主要讲述栈和队列的定义，希望对大家有所帮助！
文章目录
- 1.Stack.h
- 2.Stack.c
-
- 2.1 STackDesTroy(ST* ps)
- 2.2STackPush(ST* ps, STDataType x)
- 2.3 STackEmpty(ST* ps)
- 2.4 STackPop(ST* ps)
- 2.5 STacksize(ST* ps)
- 3.Queue.h
- 4.Queue.c
-
- 4.1QueueInit(Queue* pq)
- 4.3QueuePush(Queue* pq, QDataType x)
- 4.4QueueTmpty(Queue* pq)
- 4.5 QueuePop(Queue* pq)
- 4.6QueueFront(Queue* pq)
- 4.7 QueueBack(Queue* pq)
- 4.8QueueSize(Queue* pq)
1.Stack.h
栈的头文件，讲述程序的功能
代码展示
点我展开
1#pragma once 2#include<stdio.h> 3#include<stdlib.h> 4#include<assert.h> 5#include<stdbool.h> 6 7//定义栈的结构 8typedef int STDataType; 9typedef struct Stack 10{ 11 STDataType* arr; 12 int top; 13 int capacity; 14}ST; 15 16//初始化 17void STackInit(ST* ps); 18//销毁 19void STackDesTroy(ST* ps); 20 21//入栈---栈顶 22void STackPush(ST* ps,STDataType x); 23//出栈---栈顶 24void STackPop(ST* ps); 25//取栈顶元素 26STDataType STackTop(ST* ps); 27 28//获取栈中有效元素个数 29int STacksize(ST* ps); 30//栈是否为空 31bool STackEmpty(ST* ps); 32
2.Stack.c
说一下有些函数没有断言，主要讲述重要的地方
2.1 STackDesTroy(ST* ps)
功能：把栈清空
代码展示
1//销毁 2void STackDesTroy(ST* ps) 3{ 4 if(ps->arr) 5 free(ps->arr); 6 ps->arr =NULL; 7 ps->capacity = ps->top = 0; 8} 9
我们需要判断栈里是否为空，才能free里的内容
2.2STackPush(ST* ps, STDataType x)
功能：入栈
代码展示
1//入栈---栈顶 2void STackPush(ST* ps, STDataType x) 3{ 4 assert(ps); 5 if (ps->capacity == ps->top) 6 { 7 //增容 8 int newcapacity = ps->arr == NULL ? 4 : 2 * ps->capacity; 9 //扩容用realloc,用malloc前面的会消失 10 STDataType* tmp = (STDataType*)realloc(ps->arr,sizeof(STDataType)* newcapacity); 11 if (tmp == NULL) { 12 perror("malloc fial"); 13 exit(1); 14 } 15 ps->arr = tmp; 16 ps->capacity =newcapacity; 17 } 18 ps->arr[ps->top++] = x; 19} 20
增容：判断栈是否为空，为空返回4字节否则返回2倍原字节
扩容用realloc不用malloc
原因：malloc是重新启用空间会把原来栈的数据清空
然后给栈赋值，记得更新栈顶和容量
2.3 STackEmpty(ST* ps)
功能：判断栈是否为空
代码展示
1bool STackEmpty(ST* ps) 2{ 3 assert(ps); 4 //用top判断栈是否为空 5 return ps->top == 0; 6} 7
要判断一个东西建议用bool类型的函数
判断栈为空就是判断栈顶top是否为0
2.4 STackPop(ST* ps)
功能：出栈
1//出栈---栈顶 2 void STackPop(ST* ps) 3 { 4 //判断栈是否为空 5 assert(!STackEmpty(ps)); 6 --ps->top; 7} 8要出栈要判断栈是否为空 9出栈实际上是给栈顶减减 10 11## 2.5 STackTop(ST* ps) 12功能：得到栈顶的元素 13```c 14//取栈顶元素 15 STDataType STackTop(ST* ps) 16 { 17 //判断栈是否为空 18 assert(!STackEmpty(ps)); 19 //取的是ps->arr[ps->top - 1]（栈顶的元素）而不是栈顶数 20 return ps->arr[ps->top - 1]; 21} 22
既然要取栈顶元素就要判断栈是否为空
直接返回栈顶元素即可（返回的下标是top - 1）
2.5 STacksize(ST* ps)
功能：获取栈中存储的有效个数
代码展示
1//获取栈中有效元素个数 2 int STacksize(ST* ps) 3 { 4 assert(ps); 5 return ps->top; 6} 7
栈中的有效个数就是栈顶的值
3.Queue.h
展示函数功能
代码展示
点我展开
1#pragma once 2#include<stdio.h> 3#include<stdlib.h> 4#include<assert.h> 5#include<stdbool.h> 6 7typedef int QDataType; 8//队列节点的结构 9typedef struct queueNode 10{ 11 QDataType val; 12 struct queueNode* next; 13 // 14}QueueNode; 15//队列的结构 16typedef struct queue 17{ 18 QueueNode* phead; 19 QueueNode* ptail; 20 //int size;//队列中有效数据的个数 21}Queue; 22 23//初始化 24void QueueInit(Queue* pq); 25//销毁队列 26void QueueDesTroy(Queue* pq); 27 28//入队——队尾 29void QueuePush(Queue* pq, QDataType x); 30 31 32//出队——队头 33void QueuePop(Queue* pq); 34//队列判空 35bool QueueTmpty(Queue* pq); 36//队列有效元素个数 37int QueueSize(Queue* pq); 38 39//取队头数据 40QDataType QueueFront(Queue* pq); 41//取队尾数据 42QDataType QueueBack(Queue* pq); 43
>队列是由两个指针组成的结构体,包括头phead和尾ptail >队列里是单链表组成的 ```
4.Queue.c
实现队列功能
4.1QueueInit(Queue* pq)
功能：初始化队列
代码展示
1 2//初始化 3void QueueInit(Queue* pq) 4{ 5 assert(pq); 6 pq->phead = pq->ptail = NULL; 7} 8 9 10把头尾指针置空 11 12## 4.2QueueDesTroy(Queue* pq) 13 14功能：销毁队列里的数据 15代码展示 16```c 17//销毁队列 18void QueueDesTroy(Queue* pq) 19{ 20 assert(pq); 21 QueueNode* pcur = pq->phead; 22 while (pcur) 23 { 24 QueueNode* next = pcur->next; 25 free(pcur); 26 pcur = next; 27 } 28 pq->phead = pq->ptail = NULL; 29} 30
给个next保存下一位的地址完成节点的销毁
最后给头指针和尾指针置空
4.3QueuePush(Queue* pq, QDataType x)
功能：入队（尾入队）
代码展示
1//入队——队尾 2void QueuePush(Queue* pq, QDataType x) 3{ 4 assert(pq); 5 QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode)); 6 if (newnode == NULL) 7 { 8 perror("malloc fial"); 9 exit(1); 10 } 11 newnode->val = x; 12 newnode->next = NULL; 13 //队列为空 14 if (pq->phead == NULL) { 15 pq->phead = pq->ptail = newnode; 16 } 17 else { 18 pq->ptail->next = newnode; 19 pq->ptail = newnode; 20 } 21 //ps->size++; 22} 23
每次入队都创建一个节点把val赋好next指向NULL
如果队列为空就把头指针(phead)和尾指针（ptail）被赋值为newnode指针,若不是就把尾指针指向newnode再把ptail赋值为newnode指针
4.4QueueTmpty(Queue* pq)
功能：判断队列是否为空
代码展示
1//队列判空 2bool QueueTmpty(Queue* pq) 3{ 4 assert(pq); 5 return pq->phead == NULL; 6} 7
判断队列为空就是看头指针是否等于NULL
4.5 QueuePop(Queue* pq)
功能：出队（头指针chu队列）
代码展示
1//出队——队头 2void QueuePop(Queue* pq) 3{ 4 assert(!QueueTmpty(pq)); 5 //只有一个节点，phead-ptai都置为空 6 if (pq->phead == pq->ptail) 7 { 8 free(pq->phead); 9 pq->phead = pq->ptail = NULL; 10 } 11 else { 12 QueueNode* next = pq->phead->next; 13 free(pq->phead); 14 pq->phead = next; 15 } 16 //pq->size--; 17} 18
要出队列先判断队列是否为空
如果只有一个节点就free头结点后置空
不是则给个next指针（找到新的头结点）然后free(phead),把phead赋值为next
4.6QueueFront(Queue* pq)
功能：获取队头信息
代码展示
1//取对头数据 2QDataType QueueFront(Queue* pq) 3{ 4//队列判空 5 assert(!QueueTmpty(pq)); 6 return pq->phead->val; 7} 8
判断队列是否为空，然后返回对头数据
4.7 QueueBack(Queue* pq)
功能：获取队尾信息
代码展示
1//取队尾数据 2QDataType QueueBack(Queue* pq) 3{ 4//队列判空 5 assert(!QueueTmpty(pq)); 6 return pq->ptail->val; 7} 8
判断队列是否为空，返回队尾数据
4.8QueueSize(Queue* pq)
功能：获取队列有多少有效数据
方案1.
把队列多加int size,当出队入队是加加减减（前面代码有注释）
具体代码在方案2中也有注释
方案2.
遍历队列返回有效个数
代码展示
1//队列有效元素个数 2int QueueSize(Queue* pq) 3{ 4 assert(pq); 5 //第一种方案遍历链表——适用于不会频繁调用队列有效个数的场景 6 QueueNode* pcur = pq->phead; 7 int size = 0; 8 while (pcur) 9 { 10 ++size; 11 pcur = pcur->next; 12 } 13 return size; 14 15 //第二种方式：遍历链表——适用于频繁调用有效数据的场景 16 //return pq->size; 17} 18
方案1适用于不常调用有效个数的情况
方案2适用于常调用有效个数的情况
这篇文章在这里就结束了，希望对你有所帮助！
