1.栈

1.1栈的概念和结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。

Queue.h

#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<stdbool.h>typedefintQDataType;typedefstructQueueNode{structQueueNode*next;QDataType data;}QNode;typedefstructQueue{QNode*head;QNode*tail;intsize;}Que;voidQueueInit(Que*pq);voidQueueDestroy(Que*pq);voidQueuePush(Que*pq,QDataType x);voidQueuePop(Que*pq);QDataType QueueFront(Que*pq);QDataType QueueBack(Que*pq);bool QueueEmpty(Que*pq);intQueueSize(Que*pq);

Queue.c

#include"Queue.h"//初始化voidQueueInit(Que*pq){assert(pq);pq->head =pq->tail =NULL;pq->size =0;}//销毁voidQueueDestroy(Que*pq){assert(pq);QNode*cur =pq->head;while(cur){QNode*next =cur->next;free(cur);cur =cur->next;}pq->head =pq->tail =NULL;pq->size =0;}//入队voidQueuePush(Que*pq,QDateType x){assert(pq);QNode*newnode =(QNode*)malloc(sizeof(QNode));if(newnode ==NULL){perror("malloc fail");exit(-1);}newnode->date =x;newnode->next =NULL;if(pq->tail ==NULL){pq->head =pq->tail =newnode;}else{pq->tail->next =newnode;pq->tail =newnode;}pq->size++;}//出队voidQueuePop(Que*pq){assert(pq);assert(!QueueEmpty(pq));if(pq->head->next ==NULL){pq->head =pq->tail =NULL;}else{QNode*next =pq->head->next;free(pq->head);pq->head =next;}pq->size--;}//队头QDateType QueueFront(Que*pq){assert(pq);assert(!QueueEmpty(pq));returnpq->head->date;}//队尾QDateType QueueBack(Que*pq){assert(pq);assert(!QueueEmpty);returnpq->tail->date;}//判断是否为空bool QueueEmpty(Que*pq){assert(pq);returnpq->head ==NULL;}//计算intQueueSize(Que*pq){assert(pq);returnpq->size;}

test.c

#include"Queue.h"voidQueueTest(){Que pq;QueueInit(&pq);QueuePush(&pq,1);QueuePush(&pq,2);QueuePush(&pq,3);QueuePush(&pq,4);while(!QueueEmpty(&pq)){printf("%d ",QueueFront(&pq));QueuePop(&pq);}printf("\n");QueueDestroy(&pq);}intmain(){QueueTest();return0;}

3.栈和队列面试题

3.1括号匹配问题
OJ

#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<stdbool.h>//有效括号typedefcharSTDateType;typedefstructStack{STDateType*a;inttop;intcapacity;}ST;//初始化voidSTInit(ST*ps);//销毁voidSTDestroy(ST*ps);//入栈voidSTPush(ST*ps,STDateType x);//出栈voidSTPop(ST*ps);//栈顶STDateType SLTTop(ST*ps);//计算大小intSTSize(ST*ps);//判断是否为空bool STEmpty(ST*ps);//初始化voidSTInit(ST*ps){assert(ps);ps->capacity =NULL;ps->a =0;ps->top =0;}//销毁voidSTDestroy(ST*ps){assert(ps);free(ps->a);ps->a =NULL;ps->capacity =ps->top =0;}//入栈voidSTPush(ST*ps,STDateType x){assert(ps);if(ps->top ==ps->capacity){intNewCapacity =ps->capacity ==0?4:ps->capacity *2;STDateType*tmp =(STDateType*)realloc(ps->a,sizeof(STDateType)*NewCapacity);if(tmp ==NULL){perror("realloc fail");exit(-1);}ps->a =tmp;ps->capacity =NewCapacity;}ps->a[ps->top]=x;ps->top++;}//出栈voidSTPop(ST*ps){assert(ps);assert(ps->a >0);--ps->top;}//栈顶STDateType STTop(ST*ps){assert(ps);assert(ps->a >0);returnps->a[ps->top -1];}//计算intSTSize(ST*ps){assert(ps);returnps->top;}//判断是否为空bool STEmpty(ST*ps){assert(ps);returnps->top ==NULL;}bool isValid(char*s){ST st;STInit(&st);chartopVal;while(*s){//数量不匹配if(*s =='('||*s =='['||*s =='{'){STPush(&st,*s);}else{if(STEmpty(&st)){STDestroy(&st);returnfalse;}topVal =STTop(&st);STPop(&st);if((*s ==')'&&topVal !='(')||(*s ==']'&&topVal !='[')||(*s ==' }'&&topVal !='{')){STDestroy(&st);returnfalse;}}s++;}//栈不为空，false,说明数量不匹配bool ret =STEmpty(&st);STDestroy(&st);returnret;}intmain(){isValid("[(({})}]");#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<stdbool.h>typedefintSTDateType;typedefstructStack{STDateType*a;inttop;intcapacity;}ST;//初始化voidSTInit(ST*ps);//销毁voidSTDestroy(ST*ps);//入栈voidSTPush(ST*ps,STDateType x);//出栈voidSTPop(ST*ps);//栈顶STDateType SLTTop(ST*ps);//计算大小intSTSize(ST*ps);//判断是否为空bool STEmpty(ST*ps);//初始化voidSTInit(ST*ps){assert(ps);ps->capacity =NULL;ps->a =0;ps->top =0;}//销毁voidSTDestroy(ST*ps){assert(ps);free(ps->a);ps->a =NULL;ps->capacity =ps->top =0;}//入栈voidSTPush(ST*ps,STDateType x){assert(ps);if(ps->top ==ps->capacity){intNewCapacity =ps->capacity ==0?4:ps->capacity *2;STDateType*tmp =(STDateType*)realloc(ps->a,sizeof(STDateType)*NewCapacity);if(tmp ==NULL){perror("realloc fail");exit(-1);}ps->a =tmp;ps->capacity =NewCapacity;}ps->a[ps->top]=x;ps->top++;}//出栈voidSTPop(ST*ps){assert(ps);assert(ps->a >0);--ps->top;}//栈顶STDateType STTop(ST*ps){assert(ps);assert(ps->a >0);returnps->a[ps->top -1];}//计算intSTSize(ST*ps){assert(ps);returnps->top;}//判断是否为空bool STEmpty(ST*ps){assert(ps);returnps->top ==NULL;}typedefstruct{ST pushst;ST popst;}MyQueue;MyQueue*myQueueCreate(){MyQueue*obj =(MyQueue*)malloc(sizeof(MyQueue));STInit(&obj->popst);STInit(&obj->pushst);returnobj;}voidmyQueuePush(MyQueue*obj,intx){STPush(&obj->pushst,x);}intmyQueuePeek(MyQueue*obj){if(STEmpty(&obj->popst)){while(!STEmpty(&obj->pushst)){STPush(&obj->popst,STTop(&obj->pushst));STPop(&obj->pushst);}}returnSTTop(&obj->popst);}intmyQueuePop(MyQueue*obj){intfront =myQueuePeek(obj);STPop(&obj->popst);returnfront;}bool myQueueEmpty(MyQueue*obj){returnSTEmpty(&obj->popst)&&STEmpty(&obj->pushst);}voidmyQueueFree(MyQueue*obj){STDestroy(&obj->popst);STDestroy(&obj->pushst);free(obj);}}

3.2用队列实现栈
OJ

3.3用栈实现队列
OJ

#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<stdbool.h>typedefintSTDateType;typedefstructStack{STDateType*a;inttop;intcapacity;}ST;//初始化voidSTInit(ST*ps);//销毁voidSTDestroy(ST*ps);//入栈voidSTPush(ST*ps,STDateType x);//出栈voidSTPop(ST*ps);//栈顶STDateType SLTTop(ST*ps);//计算大小intSTSize(ST*ps);//判断是否为空bool STEmpty(ST*ps);//初始化voidSTInit(ST*ps){assert(ps);ps->capacity =NULL;ps->a =0;ps->top =0;}//销毁voidSTDestroy(ST*ps){assert(ps);free(ps->a);ps->a =NULL;ps->capacity =ps->top =0;}//入栈voidSTPush(ST*ps,STDateType x){assert(ps);if(ps->top ==ps->capacity){intNewCapacity =ps->capacity ==0?4:ps->capacity *2;STDateType*tmp =(STDateType*)realloc(ps->a,sizeof(STDateType)*NewCapacity);if(tmp ==NULL){perror("realloc fail");exit(-1);}ps->a =tmp;ps->capacity =NewCapacity;}ps->a[ps->top]=x;ps->top++;}//出栈voidSTPop(ST*ps){assert(ps);assert(ps->a >0);--ps->top;}//栈顶STDateType STTop(ST*ps){assert(ps);assert(ps->a >0);returnps->a[ps->top -1];}//计算intSTSize(ST*ps){assert(ps);returnps->top;}//判断是否为空bool STEmpty(ST*ps){assert(ps);returnps->top ==NULL;}typedefstruct{ST pushst;ST popst;}MyQueue;MyQueue*myQueueCreate(){MyQueue*obj =(MyQueue*)malloc(sizeof(MyQueue));STInit(&obj->popst);STInit(&obj->pushst);returnobj;}voidmyQueuePush(MyQueue*obj,intx){STPush(&obj->pushst,x);}intmyQueuePeek(MyQueue*obj){if(STEmpty(&obj->popst)){while(!STEmpty(&obj->pushst)){STPush(&obj->popst,STTop(&obj->pushst));STPop(&obj->pushst);}}returnSTTop(&obj->popst);}intmyQueuePop(MyQueue*obj){intfront =myQueuePeek(obj);STPop(&obj->popst);returnfront;}bool myQueueEmpty(MyQueue*obj){returnSTEmpty(&obj->popst)&&STEmpty(&obj->pushst);}voidmyQueueFree(MyQueue*obj){STDestroy(&obj->popst);STDestroy(&obj->pushst);free(obj);}

3.4设计循环队列
OJ

#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<stdbool.h>//计循环队列typedefstruct{int*a;intfront;intrear;intk;}MyCircularQueue;MyCircularQueue*myCircularQueueCreate(intk){MyCircularQueue*obj =(MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->a =(int*)malloc(sizeof(int)*(k +1));obj->front =obj->rear =0;obj->k =k;returnobj;}bool myCircularQueueIsEmpty(MyCircularQueue*obj){returnobj->front ==obj->rear;}bool myCircularQueueIsFull(MyCircularQueue*obj){return(obj->rear +1)%(obj->k +1)==obj->front;}bool myCircularQueueEnQueue(MyCircularQueue*obj,intvalue){if(myCircularQueueIsFull(obj))returnfalse;obj->a[obj->rear]=value;obj->rear++;obj->rear %=(obj->k +1);returntrue;}bool myCircularQueueDeQueue(MyCircularQueue*obj){if(myCircularQueueIsEmpty(obj))returnfalse;obj->front++;obj->front %=(obj->k +1);returntrue;}intmyCircularQueueFront(MyCircularQueue*obj){if(myCircularQueueIsEmpty(obj))return-1;returnobj->a[obj->front];}intmyCircularQueueRear(MyCircularQueue*obj){if(myCircularQueueIsEmpty(obj))return-1;returnobj->a[(obj->rear +obj->k)%(obj->k +1)];}voidmyCircularQueueFree(MyCircularQueue*obj){free(obj->a);free(obj);}

💘不知不觉，【数据结构初阶】栈和队列以告一段落。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

1.2栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。