当前位置： 首页 > news >正文

【数据结构】栈与队列全方位对比 + C 语言完整实现

news 2026/6/13 1:11:02

前言

栈（Stack）和队列（Queue）是数据结构中最基础、最重要的受限线性表，是算法与程序设计的核心基石。二者逻辑结构均为线性结构，仅在操作规则上存在限制，却衍生出完全不同的应用场景。

本文将从核心特性、结构对比、C 语言完整实现、应用场景四个维度，全方位总结栈与队列，配套可直接运行的代码。

一、栈与队列核心概念对比

栈和队列的本质区别是进出规则，这也是记忆和使用的核心：

对比维度栈 (Stack)队列 (Queue)
全称后进先出表 LIFO先进先出表 FIFO
操作规则仅在栈顶插入、删除队尾插入，队头删除
生活类比叠盘子、弹夹排队买票、电梯
核心指针栈顶指针top队头front、队尾rear
核心操作入栈push、出栈pop入队enQueue、出队deQueue

二、存储结构对比

栈和队列都支持顺序存储和链式存储，适用场景不同：

  1. 顺序存储：基于数组实现，容量固定，访问速度快；
  2. 链式存储：基于链表实现，动态扩容，无空间溢出问题。

三、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; }

四、栈与队列核心知识点总结

  1. 共性

    • 均为线性结构，元素一对一排列；
    • 均支持顺序、链式两种存储方式；
    • 均为受限操作的线性表。

  2. 核心差异

    • 栈：后进先出，仅栈顶操作；
    • 队列：先进先出，队头出队、队尾入队。

  3. 选型建议

    • 数据量固定 → 顺序栈 / 循环队列；
    • 数据量动态变化 → 链栈 / 链队列。

五、经典应用场景

栈的应用

  1. 函数调用栈、递归实现
  2. 中缀表达式转后缀表达式、表达式求值
  3. 括号匹配检查
  4. 浏览器前进后退、编辑器撤销操作

队列的应用

  1. 操作系统进程 / 线程调度
  2. 消息队列、缓冲区处理
  3. 广度优先搜索（BFS）
  4. 打印机任务队列

结语

栈和队列是数据结构的入门基础，也是面试高频考点。掌握它们的原理、实现、应用，是学习树、图等复杂数据结构的前提。

http://www.jsqmd.com/news/562305/

相关文章：

  • 5步颠覆性方案：BilibiliDown让视频下载效率飙升300%
  • 2026版AI论文工具测评：精选8款免费利器，省时降重，高效成稿 - 沁言学术
  • 别再让PCB走线偷走你的电压！手把手教你用开尔文四线法搞定FPGA核心供电
  • FPGA驱动14K超高清屏：MIPI DSI接口的实战解析与点屏全流程
  • 如何用ScanTailor Advanced将扫描文档变身为专业级电子文档？完全开源解决方案
  • 基于STM32freeRTOS的Modbus从机设备数据传输方案
  • 自动化办公三件套：OpenClaw+百川2-13B处理邮件、日历与文档
  • 清华大学重磅发现：AI模型读不懂“符号“，原来它们在“靠蒙“！
  • HoRain云--Vue3条件渲染完全指南
  • Linux 内核中的内存管理优化：从理论到实践
  • 如何用React打造经典Windows XP桌面体验：完整实现指南
  • 原创：黄大年茶思屋难题揭榜第11期｜5道核心题精简公开·被退稿求技术指正
  • eFuse电子保险丝：现代电路保护的智能选择
  • 【数据结构】字符串模式匹配：暴力算法与 KMP 算法实现与解析
  • Origin绘图进阶：如何在现有图形上叠加散点图与等高线（附完整操作步骤）
  • PingFangSC字体实战：3个关键决策提升中文界面性能与体验
  • 4步终极指南：用OpenCore Legacy Patcher让老Mac重获新生
  • 解决MicroBlaze程序启动难题：Vivado中bit与elf文件合并的完整流程
  • HoRain云--Vue.js循环渲染完全指南：v-for实战技巧
  • 手把手教你用TI官方方案搭建V-I转换器恒流源（含MOSFET选型指南）
  • WinDiskWriter：突破Mac系统限制的Windows启动盘制作革新工具
  • ISL29125 RGB环境光传感器驱动与嵌入式应用实战
  • 终极指南：Windows APK安装工具完整使用教程
  • 2026年媒体发稿平台首选：传声港新媒体平台三大核心平台赋能企业全域传播 - 博客湾
  • MuJoCo仿真实战：用aubo-i5机器人模型搭建你的第一个物理仿真环境（Windows/Linux双平台）
  • React Native Material Design 与 React Native Paper 对比分析：选择合适的Material Design库
  • 面试必备之自动化测试(上)技能参考
  • OneMore社区贡献指南：如何参与开源项目开发
  • OpenCV-Mobile跨平台部署终极指南：Windows、MacOS、Linux全攻略 [特殊字符]
  • 5大场景全覆盖：Converter NOW为全平台用户打造极速单位转换体验