数据结构(四) 栈和队列 超详细讲解（原理 + 完整代码 + 算法题）

数据结构(四) 栈和队列 超详细讲解原理 完整代码 算法题栈和队列是数据结构中最基础、最常用的两种线性结构掌握它们是学习算法、操作系统、编译原理的基础。本文带你从概念 → 结构实现 → 高频算法题一站式吃透。文章目录数据结构(四) 栈和队列 超详细讲解原理 完整代码 算法题一、栈Stack1.1 栈的概念1.2 栈的底层实现1.3 栈的完整 C 语言实现二、队列Queue2.1 队列的概念2.2 队列的底层实现2.3 队列的完整 C 语言实现三、循环队列3.1 循环队列特点3.2 循环队列完整代码LeetCode 622四、高频算法题LeetCode 必刷4.1 有效的括号LeetCode 204.2 用栈实现队列LeetCode 2324.3 用队列实现栈LeetCode 225五、栈 vs 队列 核心对比六、总结一、栈Stack1.1 栈的概念栈是一种**后进先出LIFO, Last In First Out**的线性表。只允许在栈顶插入、删除插入入栈 / 压栈删除出栈 / 弹栈1.2 栈的底层实现数组实现更优尾插尾删效率高链表实现也可以但略复杂1.3 栈的完整 C 语言实现#includestdio.h#includestdlib.h#includestdbool.h// 栈数据类型定义typedefintSTDataType;// 栈结构typedefstructStack{STDataType*a;inttop;// 栈顶下标intcapacity;// 容量}ST;// 初始化栈voidSTInit(ST*ps){ps-aNULL;ps-top0;ps-capacity0;}// 销毁栈voidSTDestroy(ST*ps){free(ps-a);ps-aNULL;ps-topps-capacity0;}// 入栈voidSTPush(ST*ps,STDataType x){if(ps-topps-capacity){intnewCapacityps-capacity0?4:ps-capacity*2;STDataType*tmp(STDataType*)realloc(ps-a,sizeof(STDataType)*newCapacity);if(tmpNULL){perror(realloc fail);exit(-1);}ps-atmp;ps-capacitynewCapacity;}ps-a[ps-top]x;}// 出栈voidSTPop(ST*ps){if(ps-top0){ps-top--;}}// 取栈顶元素STDataTypeSTTop(ST*ps){returnps-a[ps-top-1];}// 获取栈中有效元素个数intSTSize(ST*ps){returnps-top;}// 栈是否为空boolSTEmpty(ST*ps){returnps-top0;}// 测试栈voidTestStack(){ST st;STInit(st);STPush(st,1);STPush(st,2);STPush(st,3);STPush(st,4);while(!STEmpty(st)){printf(%d ,STTop(st));STPop(st);}printf(\n);STDestroy(st);}intmain(){TestStack();return0;}运行结果4 3 2 1二、队列Queue2.1 队列的概念队列是一种**先进先出FIFO, First In First Out**的线性表。队尾入队队头出队2.2 队列的底层实现链表实现更优出队时直接删头结点O(1)数组实现出队需要移动数据效率低2.3 队列的完整 C 语言实现#includestdio.h#includestdlib.h#includestdbool.h// 队列数据类型定义typedefintQDataType;// 队列结点结构typedefstructQueueNode{QDataType val;structQueueNode*next;}QNode;// 队列结构typedefstructQueue{QNode*phead;QNode*ptail;intsize;}Queue;// 初始化队列voidQueueInit(Queue*pq){pq-pheadpq-ptailNULL;pq-size0;}// 销毁队列voidQueueDestroy(Queue*pq){QNode*curpq-phead;while(cur){QNode*nextcur-next;free(cur);curnext;}pq-pheadpq-ptailNULL;pq-size0;}// 入队列队尾voidQueuePush(Queue*pq,QDataType x){QNode*newNode(QNode*)malloc(sizeof(QNode));if(newNodeNULL){perror(malloc fail);exit(-1);}newNode-valx;newNode-nextNULL;if(pq-ptailNULL){pq-pheadpq-ptailnewNode;}else{pq-ptail-nextnewNode;pq-ptailnewNode;}pq-size;}// 出队列队头voidQueuePop(Queue*pq){if(pq-pheadNULL)return;if(pq-pheadpq-ptail){free(pq-phead);pq-pheadpq-ptailNULL;}else{QNode*nextpq-phead-next;free(pq-phead);pq-pheadnext;}pq-size--;}// 取队头数据QDataTypeQueueFront(Queue*pq){returnpq-phead-val;}// 取队尾数据QDataTypeQueueBack(Queue*pq){returnpq-ptail-val;}// 队列判空boolQueueEmpty(Queue*pq){returnpq-pheadNULL;}// 队列有效元素个数intQueueSize(Queue*pq){returnpq-size;}// 测试队列voidTestQueue(){Queue q;QueueInit(q);QueuePush(q,1);QueuePush(q,2);QueuePush(q,3);QueuePush(q,4);while(!QueueEmpty(q)){printf(%d ,QueueFront(q));QueuePop(q);}printf(\n);QueueDestroy(q);}intmain(){TestQueue();return0;}运行结果1 2 3 4三、循环队列3.1 循环队列特点数组实现逻辑上成环节省空间避免假溢出判空front rear判满(rear 1) % (k 1) front牺牲一个位置区分空/满3.2 循环队列完整代码LeetCode 622typedefstruct{int*a;intfront;intrear;intk;}MyCircularQueue;MyCircularQueue*myCircularQueueCreate(intk){MyCircularQueue*q(MyCircularQueue*)malloc(sizeof(MyCircularQueue));q-a(int*)malloc(sizeof(int)*(k1));q-frontq-rear0;q-kk;returnq;}boolmyCircularQueueEnQueue(MyCircularQueue*obj,intvalue){if((obj-rear1)%(obj-k1)obj-front)returnfalse;obj-a[obj-rear]value;obj-rear(obj-rear1)%(obj-k1);returntrue;}boolmyCircularQueueDeQueue(MyCircularQueue*obj){if(obj-frontobj-rear)returnfalse;obj-front(obj-front1)%(obj-k1);returntrue;}intmyCircularQueueFront(MyCircularQueue*obj){if(obj-frontobj-rear)return-1;returnobj-a[obj-front];}intmyCircularQueueRear(MyCircularQueue*obj){if(obj-frontobj-rear)return-1;returnobj-a[(obj-rear-1obj-k1)%(obj-k1)];}boolmyCircularQueueIsEmpty(MyCircularQueue*obj){returnobj-frontobj-rear;}boolmyCircularQueueIsFull(MyCircularQueue*obj){return(obj-rear1)%(obj-k1)obj-front;}voidmyCircularQueueFree(MyCircularQueue*obj){free(obj-a);free(obj);}四、高频算法题LeetCode 必刷4.1 有效的括号LeetCode 20经典栈应用题#includestring.hboolisValid(char*s){char*stk(char*)malloc(strlen(s)1);inttop0;for(inti0;s[i];i){if(s[i](||s[i][||s[i]{){stk[top]s[i];}else{if(top0)returnfalse;if((s[i])stk[top-1]!()||(s[i]]stk[top-1]![)||(s[i]}stk[top-1]!{)){returnfalse;}top--;}}bool restop0;free(stk);returnres;}4.2 用栈实现队列LeetCode 232双栈模拟队列一个入栈一个出栈typedefstruct{int*stk;intstkSize;int*outStk;intoutStkSize;}MyQueue;MyQueue*myQueueCreate(){MyQueue*q(MyQueue*)malloc(sizeof(MyQueue));q-stk(int*)malloc(sizeof(int)*100);q-outStk(int*)malloc(sizeof(int)*100);q-stkSizeq-outStkSize0;returnq;}voidmyQueuePush(MyQueue*obj,intx){obj-stk[obj-stkSize]x;}intmyQueuePop(MyQueue*obj){if(obj-outStkSize0){while(obj-stkSize0){obj-outStk[obj-outStkSize]obj-stk[--obj-stkSize];}}returnobj-outStk[--obj-outStkSize];}intmyQueuePeek(MyQueue*obj){if(obj-outStkSize0){while(obj-stkSize0){obj-outStk[obj-outStkSize]obj-stk[--obj-stkSize];}}returnobj-outStk[obj-outStkSize-1];}boolmyQueueEmpty(MyQueue*obj){returnobj-stkSize0obj-outStkSize0;}voidmyQueueFree(MyQueue*obj){free(obj-stk);free(obj-outStk);free(obj);}4.3 用队列实现栈LeetCode 225用队列的顺序特性模拟栈的逆序特性typedefstruct{int*q;intfront;intrear;intcapacity;}MyStack;MyStack*myStackCreate(){MyStack*stk(MyStack*)malloc(sizeof(MyStack));stk-capacity100;stk-q(int*)malloc(sizeof(int)*stk-capacity);stk-frontstk-rear0;returnstk;}voidmyStackPush(MyStack*obj,intx){obj-q[obj-rear]x;}intmyStackPop(MyStack*obj){intsizeobj-rear-obj-front;for(inti0;isize-1;i){obj-q[obj-rear]obj-q[obj-front];}returnobj-q[obj-front];}intmyStackTop(MyStack*obj){returnobj-q[obj-rear-1];}boolmyStackEmpty(MyStack*obj){returnobj-frontobj-rear;}voidmyStackFree(MyStack*obj){free(obj-q);free(obj);}五、栈 vs 队列 核心对比特性栈队列进出原则后进先出 LIFO先进先出 FIFO操作位置栈顶队头、队尾最优底层结构数组单链表典型应用括号匹配、函数调用、递归层序遍历、消息队列、缓冲区六、总结栈只在一端操作后进先出队列一端进一端出先进先出循环队列用数组实现环形结构高效复用空间算法题栈 队列常互相模拟、括号匹配、表达式求值、BFS/DFS