前言栈Stack和队列Queue是数据结构中最基础、最重要的受限线性表是算法与程序设计的核心基石。二者逻辑结构均为线性结构仅在操作规则上存在限制却衍生出完全不同的应用场景。本文将从核心特性、结构对比、C 语言完整实现、应用场景四个维度全方位总结栈与队列配套可直接运行的代码。一、栈与队列核心概念对比栈和队列的本质区别是进出规则这也是记忆和使用的核心对比维度栈 (Stack)队列 (Queue)全称后进先出表 LIFO先进先出表 FIFO操作规则仅在栈顶插入、删除队尾插入队头删除生活类比叠盘子、弹夹排队买票、电梯核心指针栈顶指针top队头front、队尾rear核心操作入栈push、出栈pop入队enQueue、出队deQueue二、存储结构对比栈和队列都支持顺序存储和链式存储适用场景不同顺序存储基于数组实现容量固定访问速度快链式存储基于链表实现动态扩容无空间溢出问题。三、C 语言完整代码实现带超详细注释1. 顺序栈数组实现固定容量适合数据规模已知的场景最简单的栈实现#include stdio.h #include stdlib.h #define MAXSIZE 100 // 栈最大容量 // 顺序栈结构体定义 typedef struct { int data[MAXSIZE]; // 静态数组存储栈元素 int top; // 栈顶指针-1表示空栈 } SqStack; // 初始化栈 void InitStack(SqStack *s) { s-top -1; } // 判断栈是否为空 int IsEmpty(SqStack *s) { return s-top -1; } // 入栈操作 int Push(SqStack *s, int val) { if(s-top MAXSIZE-1) { // 栈满判断 printf(栈满入栈失败\n); return 0; } s-data[s-top] val; return 1; } // 出栈操作 int Pop(SqStack *s, int *val) { if(IsEmpty(s)) { // 栈空判断 printf(栈空出栈失败\n); return 0; } *val s-data[s-top--]; return 1; } // 获取栈顶元素不删除 int GetTop(SqStack *s, int *val) { if(IsEmpty(s)) return 0; *val s-data[s-top]; return 1; } // 测试函数 int main() { SqStack s; InitStack(s); Push(s, 10); Push(s, 20); int val; Pop(s, val); printf(出栈元素%d\n, val); // 输出20 GetTop(s, val); printf(当前栈顶元素%d\n, val); // 输出10 return 0; }2. 链栈单链表实现动态内存分配无容量限制适合数据规模未知的场景#include stdio.h #include stdlib.h // 链栈节点结构体 typedef struct Node { int data; // 数据域 struct Node *next; // 指针域 } Node; // 链栈结构体仅需栈顶指针 typedef struct { Node *top; } LinkStack; // 初始化链栈 void InitStack(LinkStack *s) { s-top NULL; // 空栈 } // 入栈头插法效率最高 int Push(LinkStack *s, int val) { Node *newNode (Node*)malloc(sizeof(Node)); if(!newNode) return 0; newNode-data val; newNode-next s-top; // 新节点指向原栈顶 s-top newNode; // 更新栈顶 return 1; } // 出栈 int Pop(LinkStack *s, int *val) { if(s-top NULL) { printf(栈空出栈失败\n); return 0; } Node *temp s-top; *val temp-data; s-top s-top-next; // 栈顶下移 free(temp); // 释放节点 return 1; } // 测试函数 int main() { LinkStack s; InitStack(s); Push(s, 10); Push(s, 20); int val; Pop(s, val); printf(出栈元素%d\n, val); // 输出20 return 0; }3. 循环队列数组实现解决顺序队列假溢出问题是顺序队列的最优实现#include stdio.h #include stdlib.h #define MAXSIZE 5 // 队列容量 // 循环队列结构体 typedef struct { int data[MAXSIZE]; int front; // 队头指针 int rear; // 队尾指针 } SqQueue; // 初始化队列 void InitQueue(SqQueue *q) { q-front q-rear 0; } // 判断队列空 int IsEmpty(SqQueue *q) { return q-front q-rear; } // 判断队列满牺牲一个空间区分空/满 int IsFull(SqQueue *q) { return (q-rear 1) % MAXSIZE q-front; } // 入队 int EnQueue(SqQueue *q, int val) { if(IsFull(q)) { printf(队列满入队失败\n); return 0; } q-data[q-rear] val; q-rear (q-rear 1) % MAXSIZE; // 循环后移 return 1; } // 出队 int DeQueue(SqQueue *q, int *val) { if(IsEmpty(q)) { printf(队列空出队失败\n); return 0; } *val q-data[q-front]; q-front (q-front 1) % MAXSIZE; return 1; } // 测试函数 int main() { SqQueue q; InitQueue(q); EnQueue(q, 10); EnQueue(q, 20); int val; DeQueue(q, val); printf(出队元素%d\n, val); // 输出10 return 0; }4. 链队列单链表实现动态扩容无容量限制工业级常用队列实现#include stdio.h #include stdlib.h // 队列节点结构体 typedef struct Node { int data; struct Node *next; } Node; // 链队列结构体队头队尾指针 typedef struct { Node *front; // 队头 Node *rear; // 队尾 } LinkQueue; // 初始化创建头节点 void InitQueue(LinkQueue *q) { q-front q-rear (Node*)malloc(sizeof(Node)); q-front-next NULL; } // 入队 int EnQueue(LinkQueue *q, int val) { Node *newNode (Node*)malloc(sizeof(Node)); newNode-data val; newNode-next NULL; q-rear-next newNode; q-rear newNode; // 更新队尾 return 1; } // 出队 int DeQueue(LinkQueue *q, int *val) { if(q-front q-rear) { printf(队列空出队失败\n); return 0; } Node *temp q-front-next; *val temp-data; q-front-next temp-next; // 队列空时队尾指向头节点 if(q-rear temp) q-rear q-front; free(temp); return 1; } // 测试函数 int main() { LinkQueue q; InitQueue(q); EnQueue(q, 10); EnQueue(q, 20); int val; DeQueue(q, val); printf(出队元素%d\n, val); // 输出10 return 0; }四、栈与队列核心知识点总结共性均为线性结构元素一对一排列均支持顺序、链式两种存储方式均为受限操作的线性表。核心差异栈后进先出仅栈顶操作队列先进先出队头出队、队尾入队。选型建议数据量固定 → 顺序栈 / 循环队列数据量动态变化 → 链栈 / 链队列。五、经典应用场景栈的应用函数调用栈、递归实现中缀表达式转后缀表达式、表达式求值括号匹配检查浏览器前进后退、编辑器撤销操作队列的应用操作系统进程 / 线程调度消息队列、缓冲区处理广度优先搜索BFS打印机任务队列结语栈和队列是数据结构的入门基础也是面试高频考点。掌握它们的原理、实现、应用是学习树、图等复杂数据结构的前提。