1. 前言🥇
这一节要分享的是一个全新的结构–栈和队列,栈和队列总是会一起出现,因为它们的存储方式刚好相反,一个先进先出一个先进后出,接下来我就来分享一下什么是栈和队列以及栈和队列的具体实现
2. 什么是栈?🥇
栈：一种特殊的线性表， 其只允许在固定的一端进行插入和删除元素操作。 进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则.
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶
出栈：栈的删除操作叫做出栈。出数据也在栈顶
我们画一个图理解一下:
3. 栈的实现🥇
之前我们学了数组结构和链式结构,那么这个地方实现栈是用数组结构还是用链式结构呢?答案是数组结构更优,因为数组在尾上插入数据的代价比较小。
并且这里我们还是不采用定长数组的方式来表示栈,我们采用动态长度的数组来表示
3.1 初始化结构🥈
有了之前实现顺序表的基础,这里我们直接上代码再解释
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h>//返回布尔值要包含的头文件 typedef int STDataType; typedef struct Stack { STDataType* a;//结构体中定义一个数组 int top;//栈顶,出数据和入数据都要从栈顶开始 int capacity;//数组的容量(容量不足需要扩容) }ST;
和顺序表不同的是,定义栈的结构体我们用的是top而不是size,因为事实上这里top是栈顶也是有效数据个数
3.2 初始化函数🥈
上代码!
void StackInit(ST* ps) { assert(ps); ps->a = NULL; ps->top = 0;//top定义为0指向栈顶数据的下一位,top定义为-1指向栈顶数据 ps->capacity = 0; }
top你可以任意定义为0或者1,具体为什么指向栈顶为什么指向栈顶下一个可以参考下图 :
写好初始化函数之后,可以在test.c文件中定义一个结构体并且初始化一下,方便我们后期检查
ST st;//定义结构体 StackInit(&st);//初始化 1
3.3 插入数据🥈
这里的插入数据与之前的顺序表和链表不同,因为栈这个结构有规定只允许一遍插入数据,所以这个地方不存在什么头插尾插,只有一个插入方式
void StackPush(ST* ps, STDataType x) { assert(ps); if (ps->top == ps->capacity)//当top与capacity相同代表空间已满或者没有空间 { int newcapacity = ps->capacity == 0 ? 4 : 2 * (ps->capacity);//这里的方法和顺序表一样 STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType)*newcapacity); ps->capacity = newcapacity; ps->a = tmp; } ps->a[ps->top] = x; ps->top++;//将top指向下一份空间 }
这里的插入和顺序表的尾插基本上是一样的,这里就不再做过多的说明,如果你不太明白这里的内容,请点击后面蓝字跳转到顺序表看看详解顺序表详解
3.4 删除数据🥈
void StackPop(ST* ps) { assert(ps); assert(ps->top > 0);//保证栈中存在数据 ps->top--; }
这里的删除数据和顺序表的删除不能说很相似,只能说完全一样🕶,但是这个地方关于栈的删除也是有要求的,那就是要从栈顶删除,满足我们先进先出的关系.
3.5 取栈顶数据🥈
这个函数是我们顺序表和链表没有的,是因为这个函数对于栈来说比较常用,假如我们想打印栈中所有的数据,这个时候取栈顶数据函数就可以排上用场了,我们后面写完打印函数后在test.c文件中实际操作一下
STDataType StackTop(ST* ps) { assert(ps); assert(ps->top > 0);//保证栈中数据不为空 return ps->a[ps->top-1];//top是栈顶下一个位置,top-1才是栈顶 }
注意这里函数的返回类型是STDataType,我们栈中存储什么类型的数据就返回什么类型
3.6 判断是否为空🥈
bool StackEmpty(ST* ps) { assert(ps); if (ps->top <= 0) { return true; } else { return false; } }
这里可能是我们第一次接触到bool(布尔类型),它的意思就是返回真(true)或假(false),它需要包含的头文件是stdbool.h, 这里栈为空就返回true,栈不为空就返回false
3.7 打印函数🥈
void StackPrint(ST* ps) { assert(ps); while (ps->top >0)//不能等于0,等于0后面再减一就是负数了 { printf("%d ", ps->a[ps->top - 1]); ps->top--; } printf("\n");
我们写完打印函数后就可以根据前面实现的插入删除,取栈顶等操作来玩一玩:(解释在代码中)
ST st; StackInit(&st); StackPush(&st, 2);//插入2 3 4 5 StackPush(&st, 3);//实际上出数据要从5开始出 StackPush(&st, 4); StackPush(&st, 5); while (!StackEmpty(&st))//当栈不为空时进入while循环 { printf("%d ", StackTop(&st));//打印栈顶的数据 StackPop(&st);//再删除栈顶的数据,打印一个删除一个 }
3.8 栈的数据个数🥈
int StackSize(ST* ps) { assert(ps); return ps->top;//top等于2有a[0]和a[1]两个数据 }
注意这里返回的是数据个数而不是数据本身,所以我们用 int 类型.
3.9 销毁栈🥈
void StackDestroy(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = 0; ps->capacity = 0; }
每次用完栈后要记得销毁,下次再次使用时又重新定义结构体.
4. 什么是队列🥇
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) :
入队列：进行插入操作的一端称为队尾
出队列：进行删除操作的一端称为队头
满足先进先出
5. 队列的实现🥇
和栈一样,实现队列的时候也有两种结构选择:数组结构和链式结构. 这里使用链式结构更优一些 因为如果使用数组的结构，出队列在数组头上出数据，要将后面所有数据向前挪动,效率会比较低。
5.1 初始化结构🥈
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int QDataType; typedef struct QueueNode//定义链式结构 { struct QueueNode* next; QDataType data; }QN; typedef struct Queue//定义一个结构体,结构体中有两个指针.一个指向队头一个指向队尾 { QN* head;//其中,head是链式结构的指针,head中有data和next(如head->data) QN* tail;//tail也是定义的链式结构指针. }Queue;
这里和我们之前定义的链表有所不同,我们的链表只定义了一个指针指向,而我们的队列定义了两个指针指向并且把这两个指针放在了一个结构体当中,这是因为链表中定义两个指针的用处不大,也就是如果它定义两个指针有一个指针不常用,然而队列这个地方删除是队头,插入是队尾,所以这里定义两个指针很有必要.
它其实就是一种套娃结构:
5.2 插入数据🥈
void QueuePush(Queue* pq,QDataType x) { assert(pq); QN* newnode = (QN*)malloc(sizeof(QN)); newnode->data = x; newnode->next = NULL; if (pq->head == NULL)//head为空的情况 { pq->head = pq->tail = newnode; } else { pq->tail->next = newnode;//队尾插入新的数据 pq->tail = newnode;//再把新节点给上队尾 } }
之前说过,链式结构只要是插入数据就要重新向内存申请一块空间,并且当我们的队列为空时要特殊处理(实际上就是尾插)
5.3 删除数据🥈
void QueuePop(Queue* pq)//实际上是头删 { assert(pq); assert(pq->head != NULL);//保证队列中还存在数据 QN* cur = pq->head; QN* next = cur->next;//定义一个next指针,不然free掉cur后就找不到下一个节点了 free(cur); cur = NULL; pq->head = next;//再把next给上新头 if (pq->head == NULL)//当删除到最后一个数据时,要把tail一起置空,否则下次再插入数据会出问题 { pq->tail = NULL; } }
这个地方要注意的有两点:
删除数据前要判断队列中还有没有数据.
当删除到最后一个数据时,要把尾指针给置空,否则我们的尾指针还是指向原先的位置,下一次插入数据的时候,tail的指向会出现问题
5.4 取队头和队尾数据🥈
队列与栈不同的是队列有两个口子可以操作,一个进一个出,而栈只有一个,所以这里取数据比栈要多一个
QDataType QueueFront(Queue* pq)//取队头数据,也就是即将出队列的数据 { assert(pq); assert(pq->head);//保证队列中有数据 QN* cur = pq->head; return cur->data; } QDataType QueueBack(Queue* pq)取队尾数据,也就是最后一个出队列的数据 { assert(pq); assert(pq->head);//保证队列中有数据 QN* cur = pq->tail; return cur->data; }
5.5 队列中数据个数🥈
size_t QueueSize(Queue* pq) { assert(pq); int count = 0; QN* cur = pq->head; while (cur) { count++; cur = cur->next; } return count; }
我们之前说过 size_t 就是无符号整型的意思,这里是返回数据个数而不是数据本身,所以是整型类型
5.6 判断队列是否为空🥈
bool QueueEmpty(Queue* pq) { assert(pq); if (pq->head == NULL) { return true; } else { return false; } }
2
这里返回的是布尔值,我们之前已经提到过一次.队列为空就返回true,为假就返回false
5.7 打印函数🥈
void QueeuPrint(Queue* pq) { assert(pq); QN* cur = pq->head; while (cur != NULL) { printf("%d ", cur->data); cur = cur->next; } printf("\n"); }
因为队列是队头先出数据,所以打印数据时要从队头开始往后走
这里我们写完打印函数就可以在test.c文件中测试运行一下了:
#include"Queue.h" Queue q;//定义一个结构体,结构体中有head和tail两个指针指向 QueueInit(&q);//初始化 QueuePush(&q, 1); QueuePush(&q, 3);//依次插入1 3 5 7 QueuePush(&q, 5); QueuePush(&q, 7); while (!QueueEmpty(&q))//当队列不为空就进入while循环 { QDataType front = QueueFront(&q);//取队头数据 printf("%d ", front);//打印队头数据 QueuePop(&q);//打印队列,一边打印一边删除 }
6. 栈和队列题目分享🥇
现学现用 ! 我现在给出几道题,非常的经典 ! 大家可以取尝试一下,我会在下周以内出肝出一篇这几个OJ题的详解,敬请期待:
括号匹配问题 : OJ题链接🏆
用队列实现栈 :OJ题链接🏆
用栈实现队列 : OJ题链接🏆
7. 总结🥇
这一章介绍了两个全新的数据结构:栈和队列,它们总是容易搞混,栈是先进先出,队列是先进后出,栈是用数组实现其结构,队列是用链表实现其结构.这个地方讲完小编会停止更新数据结构一段时间去深度学习一下后面的内容:二叉树和堆,以便给大家做更详细的讲解.(C语言学习分享和刷题思路分享不停更💞💞
