4. 栈
4.2. 链式栈
4.2.1. 特性
逻辑结构：线性结构
存储结构：链式存储结构
操作：创建，入栈，出栈，清空，获取
4.2.2. 代码实现
头文件 LinkStack.h
#ifndef __LINKSTACK_H__ #define __LINKSTACK_H__ typedef int datatype; typedef struct linkstack {datatype data;struct linkstack *next; } linkstack_t; //1.创建一个空的栈 void createEmptyLinkStack(linkstack_t **ptop); //2.入栈,ptop是传入的栈针的地址，data是入栈的数据 int pushLinkStack(linkstack_t **ptop, datatype data); //3.判断栈是否为空 int isEmptyLinkStack(linkstack_t *top); //4.出栈 datatype popLinkStack(linkstack_t **ptop); //5.清空栈 void clearLinkStack(linkstack_t **ptop); //6.求栈的长度 int lengthLinkStack(linkstack_t *top); //7.获取栈顶数据,不是出栈,不需要移动main函数中的top，所以用一级指针 datatype getTopLinkStack(linkstack_t *top); #endif
1.创建一个空的栈
void createEmptyLinkStack(linkstack_t **ptop) {*ptop = NULL; }
- 入栈
int pushLinkStack(linkstack_t **ptop, datatype data) {// 定义一个指针pnew，指向新节点linkstack_t *pnew = (linkstack_t *)malloc(sizeof(linkstack_t));if(pnew == NULL){printf("New Node Creation Failed!!\n");return -1;}// 初始化pnew->data = data;pnew->next = *ptop; // 新节点的指针域，指向旧节点的地址// 栈针移动到最新的节点*ptop = pnew; }
- 判断栈是否为空
int isEmptyLinkStack(linkstack_t *top) {// 栈针指向NULL时，栈为空return top == NULL; }
- 出栈
datatype popLinkStack(linkstack_t **ptop) {// 容错判断if (isEmptyLinkStack){printf("Stack is empty!!\n");return NULL;}// 定义指针pdel，指向出栈节点linkstack_t* pdel = NULL;// 定义中间变量，暂存出栈数据datatype data = 0;// pdel指向出栈节点pdel = *ptop;// data暂存出栈数据data = pdel->data;// 栈针移动，释放出栈节点*ptop = (*ptop)->next;free(pdel);pdel = NULL;// 返回出栈数据return data; }
- 清空栈
void clearLinkStack(linkstack_t **ptop) {while(!isEmptyLinkStack(*ptop)){popLinkStack(ptop);} }
- 求栈的长度
int lengthLinkStack(linkstack_t *top) {// 定义一个变量，作为长度的计数int len = 0;// 链式栈长度的计算实际上是无头单向链表的遍历问题while(top = NULL){len ++; // 累计计数top = top->next; // 栈针移动} }
- 获取栈顶数据
datatype getTopLinkStack(linkstack_t *top) {// 容错判断if (!isEmptyLinkStack(top)){printf("Stack is empty\n");return -1;}// 返回栈顶数据return top->data; }
5. 队列
5.1. 特性
- 一端只能输入，称为队尾；另一端只能输出，称为队头
- 先进先出：FIFO
- 存在假溢出现象：
1）当数据存满后，有数据从队头出列后，应该可以存入新的数据，但是因为数据在队列里面不移动，所以队尾不存在空位，新数据无法入列，但是队列未满，如下图
2）解决方法：顺序队列
5.2. 顺序队列（循环队列）
需要实现头和尾都可以走完最后一位之后再走回来，比如4->5->0->1。
方法一：
if(i==N)i = 0;
elsei++;
方法二：
i = (i+1)%N;
5.2.1. 代码实现
头文件 sequeue.h
#ifndef __SEQUEUE_H__ #define __SEQUEUE_H__ #define N 6 typedef int datatype; typedef struct {datatype data[N];//循环队列的数组int rear;//存数据端 rear 后面int front;//取数据端 front 前面 }sequeue_t;// 1. 创建一个空的队列 sequeue_t *createEmptySequeue(); // 2. 判断队列是否为满 int isFullSequeue(sequeue_t *p); // 3. 入列 data代表入列的数据 int inSequeue(sequeue_t *p,datatype data); // 4. 判断队列是否为空 int isEmptySequeue(sequeue_t *p); // 5. 出列 datatype outSequeue(sequeue_t *p); // 6. 求队列的长度 int lengthSequeue(sequeue_t *p); // 7. 清空队列函数 void clearSequeue(sequeue_t *p); #endif
- 创建一个空队列
sequeue_t *createEmptySequeue() {// 申请空间存放队列结构sequeue_t *p = (sequeue_t *)malloc(sizeof(sequeue_t));if(p == NULL){printf("Space opening failure !!\n");return NULL;}// 初始化p->rear = 0;p->front = 0;return p; }
- 判断是否为满
int isFullSequeue(sequeue_t *p) {// 循环队列的判满公式return p->front == (p->rear + 1) % N; }
- 入列
int inSequeue(sequeue_t *p, datatype data) {// 容错判断if( isFullSequeue(p) ){printf("Space is Full !!\n");return -1;}// 入列p->data[p->rear] = data;// 队尾向后移动一个数据单位p->rear = (p->rear + 1) % N;return 0; }
- 判断是否为空
int isEmptySequeue(sequeue_t *p) {// 空返回1，非空返回0return p->rear == p->front; }
- 出列
datatype outSequeue(sequeue_t *p) {// 容错判断if ( isEmptySequeue(p) ){printf("Space is empty !!\n");return -1;}// 出列// 1）定义一个变量，暂存出列数据datatype data = p->data[p->front];// 2）队头移动p->front = (p->front + 1) % N;return data; }
- 求队列的长度
int lengthSequeue(sequeue_t *p) {// 队尾可以大于队头，也可以小于队头// rear >= front, rear - front 是长度// rear < front, rear + N -front ,这种情况相当于，队尾套了队头一圈// 两种情况综合之后得到公式 ( rear + N - front ) % Nreturn ( p->rear - p->front + N ) % N; }+N 之后 %N 对结果来说，相当于没操作
- 清空队列函数
void clearSequeue(sequeue_t *p) {// p->front = p->rear; // 不返回数据while(!isEmptySequeue(p))outSequeue(p); // 可以返回出列数据， 看需求 }
