在数据结构的世界里栈Stack和队列Queue是两种最基础也最重要的线性表。它们看似简单却支撑着操作系统、编译器、算法设计等无数底层系统的运行。栈遵循 后进先出LIFO的规则队列遵循 先进先出FIFO的规则二者共同构成了程序设计中最经典的两种数据存取模型。本文将深入解析动态顺序栈基于数组实现的栈与链式队列基于链表实现的队列从基本概念、核心操作到完整代码实现带你彻底掌握这两种数据结构。一动态顺序栈一什么是顺序栈顺序栈是利用一组地址连续的存储单元即数组依次存放栈中元素的数据结构。它设置一个栈顶指针top始终指向当前栈顶元素的下一个位置。typedef int SDatatype; typedef struct stack { SDatatype* _data; int _size; int _capacity; }stack;1栈底固定在数组下标为 0 的一端。2栈顶动态变化由 _size 指针标识。3空栈_size 0约定。4栈满当栈满时_size_capacity扩容。二基本操作实现1初始化栈void init(stack* st){ st-_data NULL; st-_size st-_capacity 0; }2判断栈空当栈为空时返回true非空时返回false。bool empty(stack* st){ return st-_size 0; }3入栈操作当栈满时_size_capacity扩容。void Push(stack* st, const SDatatype x){ if (st-_size st-_capacity) { int newcapacity st-_capacity 0 ? 4 : 2 * st-_capacity; SDatatype* tmp (SDatatype*)realloc(st-_data, newcapacity * sizeof(SDatatype)); if (tmp NULL) { perror(扩容失败); return; } st-_data tmp; st-_capacity newcapacity; } st-_data[st-_size] x; }4出栈操作当栈为空时就不能在出栈了直接断言报错。SDatatype Pop(stack* st){ assert(!empty(st)); SDatatype ret st-_data[st-_size - 1]; --st-_size; return ret; }5获取栈顶元素获取栈顶元素只返回当前栈顶的元素不删除数据。跟出栈一样也不能在栈为空时获取栈顶元素。SDatatype Top(stack* st){ assert(!empty(st)); return st-_data[st-_size - 1]; }6获取栈中元素个数int size(stack* st) { return st-_size; }7销毁栈当程序结束时我们就不在使用这个栈了由于栈中的数组是动态开辟出来的动态开辟出来的数组使用完都要释放。void destroy(stack* st){ if (st-_data) free(st-_data); st-_data NULL; st-_size st-_capacity 0; }三动态顺序栈的优缺点1优点存取速度极快所有接口操作都是O(1)。实现简单代码量少。内存连续CPU 缓存命中率高。2缺点需要realloc动态开辟异地扩容代价较大。扩容之后如果后面的空间不再使用会浪费大量空间。二链式队列链式队列是用单链表实现的队列结构。它包含两个指针队头指针_front指向队头结点队尾指针_tail指向队尾结点。为了操作方便通常会设一个头结点。队头_front指向头结点真正的队头元素在 front-next。队尾_tail指向最后一个元素结点。空队列_front _tail且都指向头结点。一基本操作实现1结构体定义typedef int QDatatype; typedef struct QueueNode { QDatatype _data; struct QueueNode* _next; }QNode; typedef struct Queue { QNode* _front; QNode* _tail; int _size; }queue;QNode用来产生节点queue里面的两个指针_front指向头结点_tail指向队尾元素节点_size用来表示当前队列中元素个数。2初始化队列void init(queue* q){ q-_front q-_tail (QNode*)malloc(sizeof(QNode)); if (q-_front NULL){ perror(7,malloc fail!); exit(-1); } q-_front-_data q-_tail-_data -1; q-_front-_next q-_tail-_next NULL; q-_size 0; }3判断队空当队列为空时返回true非空时返回false。bool empty(queue* q){ return q-_size 0; }4入队操作void push(queue* q, const QDatatype x){ QNode* newnode (QNode*)malloc(sizeof(QNode)); if (newnode NULL){ perror(19,malloc fail!); exit(-1); } newnode-_data x; newnode-_next NULL; q-_tail-_next newnode; q-_tail q-_tail-_next; q-_size; }5出队操作出队操作需要注意的是当队列中只有一个元素时出队不能直接free掉这个节点因为_tail指针指向这个节点如果直接free不改变_tail的指向_tail就会变成野指针所以要将_tail指向头结点。void pop(queue* q){ assert(!empty(q)); QNode* del q-_front-_next; if (del q-_tail){ q-_tail q-_front; } q-_front-_next del-_next; free(del); del NULL; --q-_size; }6获取队头元素QDatatype front(queue* q){ assert(!empty(q)); return q-_front-_next-_data; }7获取队尾元素QDatatype back(queue* q){ assert(!empty(q)); return q-_tail-_data; }8获取队列中元素个数int size(queue* q){ return q-_size; }9销毁队列void destroy(queue* q){ while (q-_front-_next){ QNode* del q-_front-_next; if (del q-_tail){ q-_tail q-_front; } q-_front-_next del-_next; free(del); del NULL; } free(q-_front); q-_front q-_tail NULL; q-_size 0; }二链式队列的优缺点1优点容量不受限可动态增长不存在溢出问题。内存使用灵活用多少分配多少。入队出队都只需修改指针效率高。2缺点每个结点需要额外的指针域存在内存开销。内存不连续缓存命中率较低。三为什么是 顺序栈 链式队列很多初学者会问为什么教材里通常讲 顺序栈 和 链式队列而不是反过来这背后其实是工程实践的最优选择1栈适合顺序存储栈只在一端操作顺序存储完全够用若·空间不够就直接扩容。动态数组实现简单高效。2队列适合链式存储队列两端都要操作如果用数组会产生 假溢出 问题。虽然可以用循环队列解决但边界条件复杂。链式队列逻辑清晰天然支持动态长度。队列长度往往不可预测链式存储更灵活。四总结顺序栈和链式队列是数据结构的入门基石它们的思想朴素却深刻。掌握了这两种结构你就理解了 受限线性表 的设计精髓 —— 通过限制存取位置来换取操作的简洁性和确定性。学习数据结构不能只停留在背诵代码层面更要理解为什么这么设计、每种方案的权衡是什么。顺序栈的数组下标、链式队列的头尾指针、出队时的边界处理…… 这些细节都值得反复推敲。