一文彻底搞清楚数据结构之栈与队列：从定义到实战解析
🔥承渊政道：个人主页
❄️个人专栏: 《C语言基础语法知识》《数据结构与算法初阶》
✨逆境不吐心中苦,顺境不忘来时路!🎬 博主简介:
前言:前面我通过介绍了一些链表的算法题的解题思路和双向链表的相关知识,相信你一定有所感悟和体会!至此关于链表的内容小编就告一段落了,接下来我要介绍一种特殊的线性表—>栈和队列.它们又有什么作用和用途呢?废话不多说,下面跟着小编的节奏🎵一起学习吧！
目录
1.栈的定义
栈是一种只允许在表的一端进行插入和删除的线性表.通常将表中允许进行插入、删除操作的一端称为栈顶,另一端称为栈底.栈的插入操作称为进栈或入栈,删除操作为出栈或退栈.当栈中没有元素时称为空栈.由于插入和删除操作都是在栈顶中进行,故栈顶元素的位置是动态变化的,它是由一个称为栈顶指针的位置指示器指示.每次进栈道元素都被放在原栈顶元素之上称为新的栈顶,而每次出栈的元素都是当前的栈顶元素,即最后进栈的元素.换句话说,最先入栈的元素最后出栈,即元素的进栈和出栈是按照"后进先出"(Last In First Out,LIFO)的原则进行的.
压栈:栈的插⼊操作叫做进栈/压栈/⼊栈,⼊数据在栈顶.
出栈:栈的删除操作叫做出栈.出数据也在栈顶.
2.栈的结构
1️⃣栈的顺序存储结构:在内存中用一组地址连续的存储单元依次存放自栈底到栈顶顶数据元素同时设置一个指针top指示栈顶元素的当前位置.可以用一个一维数组来描述.
2️⃣栈的链式存储结构:栈中的每一个数据元素用一个结点来表示,同时设置一个指针top指示栈顶元素的当前位置.
⭐️栈底层结构选型:
栈的实现⼀般可以使⽤数组或者链表实现,相对⽽⾔数组的结构实现更优⼀些.因为数组在尾上插⼊数据的代价⽐较⼩.
3.多栈共享空间
栈的应用非常广泛,经常会出现一个程序中需要同时使用多个栈的情况.由于各个栈的实际大小在使用过程中会发生变化,故其所需空间大小难以准确估计.为了避免出现有的栈溢出有的栈空闲的情况,可以让多个栈共享一个足够大的数组空间,使空间充分利用.
以最常用的两栈共享空间为例:
栈满的条件是:top1=top2+1;栈空的条件是:top1=0或top2=M-1.
两栈共享空间比两个栈分别申请M/2的空间利用率要高.
4.栈的实现
stack.c
#include"Stack.h"voidStackInit(ST* ps){ ps->arr =NULL; ps->top = ps->capacity =0;}//销毁voidStackDestroy(ST* ps){if(ps->arr)free(ps->arr); ps->arr =NULL; ps->top = ps->capacity =0;}//入栈---栈顶voidStackPush(ST* ps, STDataType x){assert(ps);if(ps->top == ps->capacity){//增容int newCapacity = ps->capacity ==0?4:2* ps->capacity; STDataType* tmp =(STDataType*)realloc(ps->arr, newCapacity *sizeof(STDataType));if(tmp ==NULL){perror("realloc fail!");exit(1);} ps->arr = tmp; ps->capacity = newCapacity;} ps->arr[ps->top++]= x;}//栈是否为空boolStackEmpty(ST* ps){assert(ps);return ps->top ==0;}//出栈——栈顶voidStackPop(ST* ps){assert(!StackEmpty(ps));--ps->top;}//取栈顶元素 STDataType StackTop(ST* ps){assert(!StackEmpty(ps));return ps->arr[ps->top -1];}//获取栈中有效元素个数intStackSize(ST* ps){return ps->top;}stack.h
#pragmaonce#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<stdbool.h>//定义栈的结构typedefint STDataType;typedefstructStack{ STDataType* arr;int top;//指向栈顶的位置int capacity;//栈的容量}ST;//初始化voidStackInit(ST* ps);//销毁voidStackDestroy(ST* ps);//入栈---栈顶voidStackPush(ST* ps, STDataType x);//出栈——栈顶voidStackPop(ST* ps);//取栈顶元素 STDataType StackTop(ST* ps);//获取栈中有效元素个数intStackSize(ST* ps);//栈是否为空boolStackEmpty(ST* ps);test.c
#include"Stack.h"voidtest01(){ ST st;StackInit(&st);StackPush(&st,1);StackPush(&st,2);StackPush(&st,3);StackPush(&st,4);StackPush(&st,5);StackPop(&st);StackPop(&st);StackPop(&st);StackPop(&st);StackPop(&st);while(!StackEmpty(&st)){int top =StackTop(&st);printf("%d ", top);StackPop(&st);}int size =StackSize(&st);printf("size:%d\n", size);StackDestroy(&st);}intmain(){test01();return0;}5.队列的定义
队列它只允许在表的一端进行插入操作,而在另一端进行删除操作.队列中允许进行插入操作的一端称为队尾,允许进行删除操作的一端称为队头.队列的插入操作称为进队,队列的删除操作称为出队.没有元素的队列称为空队.队列的结构与现实生活中排队的规则是一致的,后来的成员总是加入到队尾,每次离开队列的总是队头上的成员.也就是说,队列中的元素按照"先进先出(First in Frist Out,FIFO)"的原则进行的.
⼊队列:进⾏插⼊操作的⼀端称为队尾.
出队列:进⾏删除操作的⼀端称为队头.
6.队列的结构
1️⃣队列的顺序存储结构:在内存中用一组地址连续的存储单元依次存放从队头到队尾的数据元素,同时设置两个指针front和rear分别指示队头元素和队尾元素的位置.
2️⃣队列的链式存储结构:队列中每一个元素对应链表中的一个结点,并设置两个分别指示队头和队尾的指针.
⭐️队列底层结构选型:队列也可以数组和链表的结构实现,使⽤链表的结构实现更优⼀些,因为如果使⽤数组的结构,出队列在数组头上出数据,效率会⽐较低.
7.队列的实现
Queue.c
#include"Queue.h"//初始化voidQueueInit(Queue* pq){assert(pq); pq->phead = pq->ptail =NULL;//pq->size = 0;}//销毁队列voidQueueDestroy(Queue* pq){assert(pq); QueueNode* pcur = pq->phead;while(pcur){ QueueNode* next = pcur->next;free(pcur); pcur = next;} pq->phead = pq->ptail =NULL;//pq->size = 0;}//入队——队尾voidQueuePush(Queue* pq, QDataType x){assert(pq); QueueNode* newnode =(QueueNode*)malloc(sizeof(QueueNode));if(newnode ==NULL){perror("malloc fail");exit(1);} newnode->data = x; newnode->next =NULL;//队列为空if(pq->phead ==NULL){ pq->phead = pq->ptail = newnode;}else{//队列非空 pq->ptail->next = newnode; pq->ptail = pq->ptail->next;}//pq->size++;}//队列判空boolQueueEmpty(Queue* pq){assert(pq);return pq->phead ==NULL;}//出队——队头voidQueuePop(Queue* pq){assert(!QueueEmpty(pq));//只有一个节点，phead和ptail都套置为空if(pq->phead == pq->ptail){free(pq->phead); pq->phead = pq->ptail =NULL;}else{ QueueNode* next = pq->phead->next;free(pq->phead); pq->phead = next;}//pq->size--;}//取队头数据 QDataType QueueFront(Queue* pq){assert(!QueueEmpty(pq));return pq->phead->data;}//取队尾数据 QDataType QueueBack(Queue* pq){assert(!QueueEmpty(pq));return pq->ptail->data;}//队列有效元素个数intQueueSize(Queue* pq){assert(pq);//第一种方式：遍历链表——适用于不会频繁调用队列有效数据个数的场景 QueueNode* pcur = pq->phead;int size =0;while(pcur){ size++; pcur = pcur->next;}return size;//第二种方式：遍历链表——适用于频繁调用队列有效数据个数的场景//return pq->size;}Queue.h
#pragmaonce#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<stdbool.h>typedefint QDataType;//队列结点的结构typedefstructQueueNode{ QDataType data;structQueueNode* next;}QueueNode;//队列的结构typedefstructQueue{ QueueNode* phead; QueueNode* ptail;//int size; //队列中有效数据个数}Queue;//初始化voidQueueInit(Queue* pq);//销毁队列voidQueueDestroy(Queue* pq);//入队——队尾voidQueuePush(Queue* pq, QDataType x);//出队——队头voidQueuePop(Queue* pq);//队列判空boolQueueEmpty(Queue* pq);//队列有效元素个数intQueueSize(Queue* pq);//取队头数据 QDataType QueueFront(Queue* pq);//取队尾数据 QDataType QueueBack(Queue* pq);test.c
#include"Queue.h"voidtest01(){ Queue q;QueueInit(&q);QueuePush(&q,1);QueuePush(&q,2);QueuePush(&q,3);QueuePop(&q);int front =QueueFront(&q);int rear =QueueBack(&q);printf("front:%d\n", front);printf("rear:%d\n", rear);printf("size:%d",QueueSize(&q));QueueDestroy(&q);}intmain(){test01();return0;}8.栈和队列的算法题
1.有效括号
//定义栈的结构typedefchar STDataType;typedefstructStack{ STDataType* arr;int top;//指向栈顶的位置int capacity;//栈的容量}ST;voidStackInit(ST* ps){ ps->arr =NULL; ps->top = ps->capacity =0;}//销毁voidStackDestroy(ST* ps){if(ps->arr)free(ps->arr); ps->arr =NULL; ps->top = ps->capacity =0;}//入栈---栈顶voidStackPush(ST* ps, STDataType x){assert(ps);if(ps->top == ps->capacity){//增容int newCapacity = ps->capacity ==0?4:2* ps->capacity; STDataType* tmp =(STDataType*)realloc(ps->arr, newCapacity *sizeof(STDataType));if(tmp ==NULL){perror("realloc fail!");exit(1);} ps->arr = tmp; ps->capacity = newCapacity;} ps->arr[ps->top++]= x;}//栈是否为空boolStackEmpty(ST* ps){assert(ps);return ps->top ==0;}//出栈——栈顶voidStackPop(ST* ps){assert(!StackEmpty(ps));--ps->top;}//取栈顶元素 STDataType StackTop(ST* ps){assert(!StackEmpty(ps));return ps->arr[ps->top -1];}//获取栈中有效元素个数intStackSize(ST* ps){return ps->top;}//栈的实现代码boolisValid(char* s){ ST st;StackInit(&st);char*pi =s;while(*pi !='\0'){//左括号入栈if(*pi=='('||*pi =='['||*pi =='{'){StackPush(&st,*pi);}else{//判断栈为空的情况if(StackEmpty(&st)){StackDestroy(&st);returnfalse;}//右括号--取栈顶跟*pi进行匹配char top =StackTop(&st);if((top =='('&&*pi !=')')||(top =='['&&*pi !=']')||(top =='{'&&*pi !='}')){StackDestroy(&st);returnfalse;}StackPop(&st);} pi++;}bool ret =StackEmpty(&st)?true:false;StackDestroy(&st);return ret;}2.用队列实现栈
typedefint QDataType;//队列结点的结构typedefstructQueueNode{ QDataType data;structQueueNode* next;}QueueNode;//队列的结构typedefstructQueue{ QueueNode* phead; QueueNode* ptail;//int size; //队列中有效数据个数}Queue;//初始化voidQueueInit(Queue* pq){assert(pq); pq->phead = pq->ptail =NULL;//pq->size = 0;}//销毁队列voidQueueDestroy(Queue* pq){assert(pq); QueueNode* pcur = pq->phead;while(pcur){ QueueNode* next = pcur->next;free(pcur); pcur = next;} pq->phead = pq->ptail =NULL;//pq->size = 0;}//入队——队尾voidQueuePush(Queue* pq, QDataType x){assert(pq); QueueNode* newnode =(QueueNode*)malloc(sizeof(QueueNode));if(newnode ==NULL){perror("malloc fail");exit(1);} newnode->data = x; newnode->next =NULL;//队列为空if(pq->phead ==NULL){ pq->phead = pq->ptail = newnode;}else{//队列非空 pq->ptail->next = newnode; pq->ptail = pq->ptail->next;}//pq->size++;}//队列判空boolQueueEmpty(Queue* pq){assert(pq);return pq->phead ==NULL;}//出队——队头voidQueuePop(Queue* pq){assert(!QueueEmpty(pq));//只有一个节点，phead和ptail都套置为空if(pq->phead == pq->ptail){free(pq->phead); pq->phead = pq->ptail =NULL;}else{ QueueNode* next = pq->phead->next;free(pq->phead); pq->phead = next;}//pq->size--;}//取队头数据 QDataType QueueFront(Queue* pq){assert(!QueueEmpty(pq));return pq->phead->data;}//取队尾数据 QDataType QueueBack(Queue* pq){assert(!QueueEmpty(pq));return pq->ptail->data;}//队列有效元素个数intQueueSize(Queue* pq){assert(pq);//第一种方式：遍历链表——适用于不会频繁调用队列有效数据个数的场景 QueueNode* pcur = pq->phead;int size =0;while(pcur){ size++; pcur = pcur->next;}return size;//第二种方式：遍历链表——适用于频繁调用队列有效数据个数的场景//return pq->size;}//以上是队列结构和方法的实现typedefstruct{ Queue q1; Queue q2;} MyStack;//初始化 MyStack*myStackCreate(){ MyStack* pst =(MyStack*)malloc(sizeof(MyStack));QueueInit(&pst->q1);QueueInit(&pst->q2);return pst;}voidmyStackPush(MyStack* obj,int x){//往不为空的队列中插入数据if(!QueueEmpty(&obj->q1)){QueuePush(&obj->q1,x);}else{QueuePush(&obj->q2,x);}}//将不为空队列中前size-1个数据挪到另一个队列中//再将最后一个数据出队列intmyStackPop(MyStack* obj){ Queue* emp =&obj->q1; Queue* noneEmp =&obj->q2;if(QueueEmpty(&obj->q2)){ emp =&obj->q2; noneEmp =&obj->q1;}while(QueueSize(noneEmp)>1){QueuePush(emp,QueueFront(noneEmp));QueuePop(noneEmp);}int top =QueueFront(noneEmp);QueuePop(noneEmp);return top;}//取栈顶intmyStackTop(MyStack* obj){//找不为空队列中的队尾数据if(!QueueEmpty(&obj->q1)){returnQueueBack(&obj->q1);}else{returnQueueBack(&obj->q2);}}boolmyStackEmpty(MyStack* obj){returnQueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);}//销毁voidmyStackFree(MyStack* obj){QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj); obj =NULL;}3.用栈实现队列
//定义栈的结构typedefint STDataType;typedefstructStack{ STDataType* arr;int top;//指向栈顶的位置int capacity;//栈的容量}ST;voidStackInit(ST* ps){ ps->arr =NULL; ps->top = ps->capacity =0;}//销毁voidStackDestroy(ST* ps){if(ps->arr)free(ps->arr); ps->arr =NULL; ps->top = ps->capacity =0;}//入栈---栈顶voidStackPush(ST* ps, STDataType x){assert(ps);if(ps->top == ps->capacity){//增容int newCapacity = ps->capacity ==0?4:2* ps->capacity; STDataType* tmp =(STDataType*)realloc(ps->arr, newCapacity *sizeof(STDataType));if(tmp ==NULL){perror("realloc fail!");exit(1);} ps->arr = tmp; ps->capacity = newCapacity;} ps->arr[ps->top++]= x;}//栈是否为空boolStackEmpty(ST* ps){assert(ps);return ps->top ==0;}//出栈——栈顶voidStackPop(ST* ps){assert(!StackEmpty(ps));--ps->top;}//取栈顶元素 STDataType StackTop(ST* ps){assert(!StackEmpty(ps));return ps->arr[ps->top -1];}//获取栈中有效元素个数intStackSize(ST* ps){return ps->top;}//以上是栈结构和方法的实现typedefstruct{ ST pushST; ST popST;} MyQueue; MyQueue*myQueueCreate(){ MyQueue* pq =(MyQueue*)malloc(sizeof(MyQueue));StackInit(&pq->pushST);StackInit(&pq->popST);return pq;}voidmyQueuePush(MyQueue* obj,int x){//往pushST中插入数据StackPush(&obj->pushST,x);}//检查popST是否为空//1）不为空，直接出popST栈顶//2)为空，pushST数据导入到popST中，再出popST栈顶intmyQueuePop(MyQueue* obj){if(StackEmpty(&obj->popST)){//导数据while(!StackEmpty(&obj->pushST)){StackPush(&obj->popST,StackTop(&obj->pushST));StackPop(&obj->pushST);}}int top =StackTop(&obj->popST);StackPop(&obj->popST);return top;}intmyQueuePeek(MyQueue* obj){if(StackEmpty(&obj->popST)){//导数据while(!StackEmpty(&obj->pushST)){StackPush(&obj->popST,StackTop(&obj->pushST));StackPop(&obj->pushST);}}returnStackTop(&obj->popST);}boolmyQueueEmpty(MyQueue* obj){returnStackEmpty(&obj->pushST)&&StackEmpty(&obj->popST);}voidmyQueueFree(MyQueue* obj){StackDestroy(&obj->pushST);StackDestroy(&obj->popST);free(obj); obj =NULL;}9.循环队列的定义
将队列的存储空间看成一个环状的空间,即将队列的首、尾位置连接起来形成的结构称为循环队列.
循环队列中的元素变化与头、尾指针的关系如图所示.循环队列初始化时,front=rear;a1~a5依次进队后,队头元素是a1,队尾元素是a5;然后,a1和a2相继出队,a6～a10依次进队后,则队列空间被占满,此时,front=rear.
在循环队列中,指针front和rear在到达数组末尾后将自动回到数组开始的位置,即它们是由0～MAXSIZE之间循环变化的.
队列为空的判断:front==rear
队列为满的判断:(rear+1)%MAXSIZE=front
10.循环队列的算法题
设计循环队列
typedefstruct{int*arr;int front;//队头int rear;//队尾int capacity;//循环队列的空间大小} MyCircularQueue; MyCircularQueue*myCircularQueueCreate(int k){ MyCircularQueue* pq =(MyCircularQueue*)malloc(sizeof(MyCircularQueue));//申请k+1个空间 pq->arr=(int*)malloc(sizeof(int)*(k+1)); pq->front=pq->rear=0; pq->capacity= k;return pq;}boolmyCircularQueueIsEmpty(MyCircularQueue* obj){return obj->front == obj->rear;}boolmyCircularQueueIsFull(MyCircularQueue* obj){return(obj->rear+1)%(obj->capacity +1)== obj->front;}//向循环队列插入一个元素boolmyCircularQueueEnQueue(MyCircularQueue* obj,int value){//先判断是否满了if(myCircularQueueIsFull(obj)){returnfalse;}//没有满 obj->arr[obj->rear++]= value; obj->rear %= obj->capacity +1;returntrue;}//从循环队列中删除一个元素boolmyCircularQueueDeQueue(MyCircularQueue* obj){if(myCircularQueueIsEmpty(obj)){returnfalse;}//非空++obj->front; obj->front %= obj->capacity+1;returntrue;}//从队首获取元素intmyCircularQueueFront(MyCircularQueue* obj){if(myCircularQueueIsEmpty(obj)){return-1;}return obj->arr[obj->front];}//获取队尾元素intmyCircularQueueRear(MyCircularQueue* obj){if(myCircularQueueIsEmpty(obj)){return-1;}int prev =obj->rear-1;if(obj->rear ==0){ prev =obj->capacity;}return obj->arr[prev];}voidmyCircularQueueFree(MyCircularQueue* obj){if(obj->arr){free(obj->arr);free(obj); obj=NULL;}}敬请期待下一篇文章内容:数据结构之堆!
以上就是今天的博客内容了，希望能够帮助到读者朋友们！
我们一起继续加油努力💪！一键三连🙏！！！
本篇完结，点赞收藏加关注，找到小编不迷路，感谢大家🙏🤝！
