文章目录1. 引言2. 栈Stack后进先出的线性表3. 队列Queue先进先出的线性表4. 代码实现示例栈的实现代码5. 栈与队列的对比总结6. 总结与学习建议1. 引言栈和队列是计算机科学中最基础、也最常用的两种数据结构。它们都属于线性表但通过“限制插入和删除的位置”形成了完全不同的操作规则栈是后进先出LIFO队列是先进先出FIFO。理解栈和队列之所以重要主要有三个原因它们是理解程序运行逻辑的基础。函数调用、递归、表达式求值、编辑器撤销、浏览器后退等日常功能背后都依赖栈而任务调度、消息队列、广度优先搜索等场景则离不开队列。它们是很多算法和高级数据结构的起点。深度优先搜索与栈、广度优先搜索与队列之间有着天然联系单调栈、循环队列、双端队列、优先队列等也都是从栈和队列的基础上延伸出来的。它们是面试与工程实践中的高频内容。很多经典面试题都围绕栈和队列展开真正理解它们的存储方式、操作特性和复杂度分析也是后续学习树、图等复杂结构的重要基础。本文将围绕栈和队列的定义、实现、应用场景、代码示例以及常见面试题展开帮助读者从原理到实践系统掌握这两种数据结构。2. 栈Stack后进先出的线性表栈的定义与核心特征后进先出LIFO, Last In First Out栈的基本操作入栈push、出栈pop、取栈顶peek/top、判空isEmpty栈的两种实现方式顺序栈基于数组链式栈基于链表栈可以用链表来实现但是因为进栈和出栈对于数组和链表来说都很简单而数组占用空间更小所以一般使用数组来充当栈的底层数据存储的角色。3. 队列Queue先进先出的线性表队列的定义与核心特征先进先出FIFO, First In First Out队列的基本操作入队enqueue、出队dequeue、取队首front、判空isEmpty队列的抽象数据类型ADT描述队列的两种实现方式顺序队列基于数组链式队列基于链表因为链表会用到头部删除头部插入所以用链表来表示。4. 代码实现示例栈的实现代码栈的结构体和数据类型的确定typedefintSTDataType;typedefstructstack{STDataType*arr;//等效为size;inttop;intcapacity;}ST;栈的实现代码voidSTInit(ST*ps){assert(ps);ps-arrNULL;ps-topps-capacity0;}voidSTPush(ST*ps,STDataType x){assert(ps);if(ps-capacityps-top){//使用问好表达式加括号intnewcapacity(ps-capacity0?4:ps-capacity*2);//用realloc新开STDataType*tmp(STDataType*)realloc(ps-arr,sizeof(STDataType)*newcapacity);if(!tmp){perror(malloc failed:);exit(1);}ps-arrtmp;//capacity也要改ps-capacitynewcapacity;}//插入数据后记得让topps-arr[ps-top]x;}//检查栈是否为空boolSTEmpty(ST*ps){assert(ps);//只需要关注top的值就行returnps-top0;}STDataTypeSTPop(ST*ps){assert(!STEmpty(ps));//删除只需要让有效数据减一ps-top--;returnps-arr[ps-top];}//返回栈顶处的值STDataTypeSTTop(ST*ps){assert(!STEmpty(ps));//注意这里是返回top - 1的值returnps-arr[ps-top-1];}voidSTDestroy(ST*ps){assert(ps);//这里需要检查一下数组是不是空的freeNULL会导致程序崩溃if(ps-arr)free(ps-arr) ps-arrNULL;ps-topps-capacity0;}intSTSize(ST*ps){assert(ps);returnps-top;}队列结构体和数据类型的确定这里需要两个结构体一个结构体用于创建队列另一个用于创建队列的节点typedefintQDatatype;typedefstructQueueNode{QDatatype data;structQueueNode*next;}QN;typedefstructQueue{QN*phead;QN*ptail;//为了快速访问大小intsize;}qu;队列的实现代码voidQueueInit(qu*pq){//注意有解引用就有断言assert(pq);pq-pheadpq-ptailNULL;pq-size0;}voidQueueDestroy(qu*pq){assert(pq);QN*pcurpq-phead;while(pcur){QN*nextpcur-next;free(pcur);pcurnext;}pq-pheadpq-ptailNULL;pq-size0;}intQueueSize(qu*pq){assert(pq);returnpq-size;}//入队---队尾//注意想要在函数里创建新节点只能用内存函数voidQueuePush(qu*pq,QDatatype x){assert(pq);//这里注意检查mallocQN*Newnode(QN*)malloc(sizeof(QN));if(!Newnode){perror(malloc failed);exit(1);}Newnode-datax;Newnode-nextNULL;//这里需要特判一下如果头节点为空后面ptail会出现空指针解引用if(pq-pheadNULL){pq-pheadpq-ptailNewnode;}else{pq-ptail-nextNewnode;pq-ptailpq-ptail-next;}pq-size;}//和所以数据结构一样要删除数据之前要验查是否为空boolQueueEmpty(qu*pq){assert(pq);returnpq-ptailNULL;}//出队对头QDatatypeQueuePop(qu*pq){//删除数据都要判空assert(!QueueEmpty(pq))//这里需要保存出队数据QDatatype revpq-phead-data;//只有一个节点的时候要特判if(pq-pheadpq-ptail){free(pq-phead);pq-ptailpq-pheadNULL;}else{QN*nextpq-phead-next;free(pq-phead);pq-pheadnext;}//删除之后size--pq-size--;returnrev;}QDatatypeQueueFront(qu*pq){//注意这里要判空取数据一定不能为空assert(!QueueEmpty(pq));returnpq-phead-data;}QDatatypeQueueBack(qu*pq){assert(!QueueEmpty(pq));returnpq-ptail-data;}5. 栈与队列的对比总结栈和队列本质上都是“操作受限的线性表”都是在一组相同类型元素之间建立先后顺序。它们最主要的区别在于插入和删除发生的位置不同由此形成了截然不同的访问规则。从操作规则上看栈遵循LIFOLast In First Out后进先出所有插入和删除都只发生在同一端也就是“栈顶”。因此最后入栈的元素会最先被取出。队列则遵循FIFOFirst In First Out先进先出插入发生在队尾删除发生在队首最先入队的元素最先出队。从实现方式上看两者都可以基于数组或链表实现。栈的入栈和出栈都只在栈顶进行因此无论使用数组还是链表操作都比较简单由于数组在空间上更紧凑实际中更常使用数组作为栈的底层存储。队列则需要在队尾插入、在队首删除使用数组实现顺序队列时容易出现“假溢出”问题因此实际工程中常采用循环队列而使用链表实现队列时需要通过维护队首和队尾指针来保证两端操作都足够高效。在选择数据结构时可以按照以下思路判断如果问题具有“后进先出”的特征例如函数调用、撤销操作、括号匹配、表达式求值等应优先考虑栈。如果问题需要按照“先进先出”的顺序处理例如任务调度、消息队列、广度优先搜索、缓冲区等应优先考虑队列。简单来说栈解决的是“最近发生的事先处理”的问题而队列解决的是“最早发生的事先处理”的问题。理解两者的限制条件与操作特性是进一步学习双端队列、优先队列以及相关算法的基础。6. 总结与学习建议栈和队列是数据结构学习中绕不开的两个基础结构它们都属于“操作受限的线性表”核心差别只在于插入和删除发生的位置不同栈只能在栈顶进出遵循后进先出LIFO队列在队尾插入、在队首删除遵循先进先出FIFO。在实现上两者都可以基于数组或链表完成。栈由于只在一端操作实现相对简单实际中更常用数组来充当底层存储队列则因为需要维护两端操作使用数组时要注意“假溢出”问题工程中常采用循环队列或者通过链表维护队首、队尾指针来保证高效。学习这两个结构时可以重点关注几个易错点入栈、出栈前要留意栈是否已满或已空循环队列要理清取模运算以及判空与判满条件的区别链表实现时要注意指针更新的先后顺序避免断链或重复释放。后续学习中可以把栈和队列当作进一步理解递归、深度优先搜索、广度优先搜索以及单调栈、优先队列等高级内容的基础。多做“用栈模拟递归”“用队列实现广度优先搜索”等练习能够帮助更快建立起对数据结构的直觉。