线 性 数 据 结 构 双 雄：栈 与 队 列 的 原 理、实 现 与 应 用
线 性 数 据 结 构 双 雄：栈 与 队 列 的 原 理、实 现 与 应 用
- 栈
- 栈 的 操 作 实 现
- 代 码 全 貌 与 功 能 介 绍
- 代 码 效 果 展 示
- 队 列
- 队 列 的 操 作 实 现
- 代 码 全 貌 与 功 能 介 绍
- 代 码 效 果 展 示
- 栈 与 队 列 的 对 比 分 析
- 总 结 与 进 阶 建 议
- 核 心 知 识 点 回 顾
- 学 习 进 阶 建 议
- 总 结
💻作 者 简 介：曾 与 你 一 样 迷 茫，现 以 经 验 助 你 入 门 数据 结 构。
💡个 人 主 页：@笑口常开xpr 的 个 人 主 页
📚系 列 专 栏：硬 核 数 据 结 构 与 算 法
✨代 码 趣 语：栈 如 弹 夹，后 进 先 出；队 似 排 队，先 进 先 出。
💪代 码 千 行，始 于 坚 持，每 日 敲 码，进 阶 编 程 之 路。
📦gitee 链 接：gitee
在 数 据 结 构 的 世 界 里，每 一 种 设 计 都 可 能 孕 育 出 惊 人 的 效 率 变 革。你 是 否 深 思 过，一 组 精 心 组 织 的 数 据 究 竟 能 创 造 怎 样 的 奇 迹？每 一 次 挖 掘 底 层 原 理，都 是 与 计 算 机 智 慧 的 巅 峰 对 话；每 一 次 剖 析 存 储 模 式，都 在 破 解 数 据 世 界 的 终 极 密 码。准 备 好 迎 接 这 场 盛 宴 了 吗？让 我 们 一 同 探 寻 栈 和 队 列 的 无 尽 奥 秘，见 证 它 如 何 重 塑 数 字 时 代 的 运 行 法 则！
栈
定 义
栈 是 一 种 特 殊 的 线 性 表，其 只 允 许 在 固 定 的 一 端 （栈 顶）进 行 插 入 和 删 除 元 素 操 作。
基 本 概 念
栈 顶
进 行 数 据 插 入 和 删 除 操 作 的 一 端 称 为 栈 顶。
栈 底
另 一 端 称 为 栈 底。
入 栈
栈 的 插 入 操 作 叫 做 进 栈 / 压 栈 / 入 栈，数 据 从 栈 顶 进 入。将 一 个 元 素 添 加 到 栈 顶，当 执 行 入 栈 操 作 时，栈 顶 指 针 向 上 移 动 一 位，指 向 新 加 入 的 元 素。
出 栈
栈 的 删 除 操 作 叫 做 出 栈，数 据 从 栈 顶 删 除。移 除 并 返 回 栈 顶 的 元 素，出 栈 后，栈 顶 指 针 向 下 移 动 一 位，指 向 栈 中 的 下 一 个 元 素。
原 则
栈 中 的 数 据 元 素 遵 守 后 进 先 出 或 者 先 进 后 出 的 原 则。即 最 后 入 栈 的 元 素 会 先 出 栈，最 先 入 栈 的 元 素 后 出 栈。
下 面 分 别 以 元 素 为 1234 入 栈 和 出 栈 进 行 动 画 演 示
栈 的 操 作 实 现
代 码 全 貌 与 功 能 介 绍
整 个 栈 由 三 个 主 要 文 件 构 成：stack.h、stack.c 和 test.c。这 种 多 文 件 的 架 构 设 计，有 助 于 将 不 同 功 能 模 块 分 离，提 高 代 码 的 可 读 性、可 维 护 性 与 可 扩 展 性。
stack.h
stack.h 包 含 了 栈 所 需 的 头 文 件 引 用、常 量 定 义 以 及 函 数 声 明。
test.c
test.c 是 栈 的 主 逻 辑 文 件，负 责 处 理 用 户 输 入 和 代 码 流 程 的 控 制。
stack.c
stack.c 则 实 现 了 栈 的 具 体 功 能 函 数。
下 面 展 示
完 整 代 码。
读 者 可 以 将 这 段 代 码 复 制 到 自 己 的 编 译 器 中 运 行。
stack.h
#pragma once#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
//静态栈
//#define N 10
//struct Stack
//{
// int a[N];
// int top;
//};//动态栈
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity; //容量
}ST;//初始化
void STInit(ST* ps);void STDestroy(ST* ps);void STMiddle(void(*Pf)(ST* ps, STDataType x), ST* ps);//只能在一端插入,即栈顶
void STPush(ST* ps,STDataType x);void STPop(ST* ps);int STSize(ST* ps);bool STEmpty(ST* ps);//访问栈顶元素
STDataType STTop(ST* ps);void STPrint(ST* ps);//保存栈中的元素到文件中
void STSave(ST* ps);//从文件中加载
void STLoad(ST* ps);
test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "stack.h"
void menu()
{printf("***************************************\n");printf("***** 0. STExit 1. STPush *****\n");printf("***** 2. STPop 3. STSize *****\n");printf("***** 4. STEmpty 5. STTop *****\n");printf("***** 6. STPrint *****\n");printf("***************************************\n");
}
void test()
{int input = 0;ST st;STInit(&st);do{menu();printf("请输入你想要进行的操作:>");scanf("%d", &input);switch (input){case 0:STSave(&st);STDestroy(&st);break;case 1:STMiddle(STPush, &st);break;case 2:STPop(&st);STPrint(&st);break;case 3:printf("%d\n", STSize(&st));break;case 4:if (STEmpty(&st)){printf("栈为空\n");}else{printf("栈不为空\n");}break;case 5:printf("栈顶元素是:%d\n", STTop(&st));break;case 6:STPrint(&st);break;default:printf("输入无效,请重新输入\n");break;}} while (input);
}
int main()
{test();return 0;
}
stack.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "stack.h"void STInit(ST* ps)
{assert(ps);ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);if (ps->a == NULL){perror("ps->a");return;}ps->capacity = 4;ps->top = 0; //top是栈顶元素的下一个位置//ps->top = -1; //top是栈顶元素STLoad(ps);
}void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = 0;ps->capacity = 0;
}
void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->capacity * 2);if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity *= 2;}ps->a[ps->top] = x;ps->top++;
}void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps->top--;
}int STSize(ST* ps)
{assert(ps);return ps->top;
}bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}STDataType STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->a[ps->top - 1];
}void STPrint(ST* ps)
{assert(ps);int i = 0;while (i < ps->top){printf("%d ", ps->a[i]);i++;}printf("\n");
}
void STSave(ST* ps)
{assert(ps);FILE* pf = fopen("stack.txt", "w");if (pf == NULL){perror("fopen fail");return;}int i = 0;for (i = 0;i < ps->top;i++){fprintf(pf, "%d ", ps->a[i]);}fclose(pf);pf = NULL;printf("保存数据成功\n");
}void STLoad(ST* ps)
{assert(ps);FILE* pf = fopen("stack.txt", "r");if (pf == NULL){perror("fopen fail");return;}int data = 0;while (fscanf(pf, "%d", &data) == 1){STPush(ps, data);}fclose(pf);pf = NULL;
}
void STMiddle(void(*pf)(ST* ps, STDataType x),ST* ps)
{assert(ps);int x = 0;printf("请输入你想要插入的数字:>");scanf("%d", &x);pf(ps, x);STPrint(ps);
}
代 码 效 果 展 示
菜 单 展 示
每 次 循 环 开 始 时 会 显 示 菜 单，内 容 包 括：
STExit：退 出 程 序 并 将 栈 中 的 元 素 保 存 到 文 件 中
STPush：入 栈
STPop：出 栈
SLSize：栈 中 元 素 的 个 数
STEmpty：栈 是 否 为 空
STTop：栈 顶 元 素
STPrint：输 出 栈 中 的 元 素
退 出 栈（STExit）
输 入 0 后，程 序 会 将 栈 中 的 信 息 保 存 到 文 件 “stack.txt” 中。释 放 内 存 并 销 毁 栈， 然 后 退 出 程 序。
入 栈（STPush）
输 入 1 后，程 序 会 提 示 用 户 输 入 插 入 的 数 字。输 入 完 成 后，数 字 被 添 加 到 栈，然 后 输 出 修 改 后 的 栈。
出 栈（STPop）
输 入 2 后，先 入 栈 的 数 字 会 被 删 除，然 后 输 出 修 改 后 的 栈。
栈 中 有 效 元 素 个 数（STSize）
输 入 3 后，程 序 会 输 出 栈 中 的 元 素 个 数。
检 查 栈 是 否 为 空（STEmpty）
输 入 4 后，程 序 会 检 查 栈 是 否 为 空，如 果 栈 为 空，则 输 出 栈 是 空，反 之，则 输 出 栈 不 为 空。
输 出 栈 顶 元 素（STTop）
输 入 5 后，程 序 会 输 出 栈 顶 元 素。
输 出 栈 中 的 元 素（STPrint）
输 入 6 后，程 序 会 在 屏 幕 上 显 示 目 前 已 经 保 存 的 栈 中 的 元 素。
队 列
定 义
队 列 是 一 种 线 性 表。队 列 只 允 许 在 线 性 表 的 一 端 进 行 插 入 元 素，而 在 另 一 端 删 除 元 素。
基 本 概 念
队 尾
队 列 中 允 许 插 入 的 一 端 被 称 作 队 尾。
队 头
队 列 中 允 许 删 除 的 一 端 被 称 作 队 头。
出 队
出 队 是 从 队 列 的 头 部 移 除 并 返 回 一 个 元 素 的 操 作。
入 队
入 队 是 将 一 个 新 元 素 添 加 到 队 列 的 尾 部 的 操 作。
队 空
队 列 中 没 有 元 素
队 满
队 列 中 元 素 数 量 达 到 上 限
原 则
队 列 是 一 种 遵 循 先 进 先 出 或 者 后 进 后 出 原 则 的 重 要 数 据 结 构。
队 列 的 操 作 实 现
代 码 全 貌 与 功 能 介 绍
整 个 队 列 由 三 个 主 要 文 件 构 成：Queue.h、Queue.c 和 test.c。这 种 多 文 件 的 架 构 设 计，有 助 于 将 不 同 功 能 模 块 分 离，提 高 代 码 的 可 读 性、可 维 护 性 与 可 扩 展 性。
Queue.h
Queue.h 包 含 了 队 列 所 需 的 头 文 件 引 用、常 量 定 义 以 及 函 数 声 明。
test.c
test.c 是 队 列 的 主 逻 辑 文 件，负 责 处 理 用 户 输 入 和 代 码 流 程 的 控 制。
Queue.c
Queue.c 则 实 现 了 队 列 的 具 体 功 能 函 数。
下 面 展 示
完 整 代 码。
读 者 可 以 将 这 段 代 码 复 制 到 自 己 的 编 译 器 中 运 行。
Queue.h
#include<stdio.h>
#include<stdbool.h>
#include<assert.h>
#include<stdlib.h>typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;//初始化队列
void QueueInit(Queue* pq);//销毁队列
void QueueDestory(Queue* pq);//队尾入队列
void QueuePush(Queue* pq,QDataType x);//队头出队列
void QueuePop(Queue* pq);//获取队列中有效元素个数
int QueueSize(Queue* pq);//检查队列是否为空
bool QueueEmpty(Queue* pq);//取出队头的数据
QDataType QueueFront(Queue* pq);//取出队尾的数据
QDataType QueueBack(Queue* pq);//输出队列
void QueuePrint(Queue* pq);void QueueMiddlePush(void(*pf)(Queue* pq, QDataType x), Queue* pq);void QueueMiddle(Queue* pq, int num);//保存队列到文件中
void QueueSave(Queue* pq);//从文件中加载队列
void QueueLoad(Queue* pq);
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
void menu()
{printf("**********************************************\n");printf("***** 0. QueueExit 1. QueuePush *****\n");printf("***** 2. QueuePop 3. QueueSize *****\n");printf("***** 4. QueueFront 5. QueueBack *****\n");printf("***** 6. QueueEmpty 7. QueuePrint *****\n");printf("**********************************************\n");
}
void test()
{int input = 0;Queue q;QueueInit(&q);do{menu();printf("请输入你想要进行的操作:>");scanf("%d", &input);switch (input){case 0:QueueSave(&q);QueueDestory(&q);break;case 1:QueueMiddlePush(QueuePush, &q);break;case 2:QueueMiddle(&q, 2);break;case 3:printf("队列元素个数:%d\n", QueueSize(&q));break;case 4:QueueMiddle(&q, 4);break;case 5:QueueMiddle(&q, 5);break;case 6:QueueMiddle(&q, 6);break;case 7:QueuePrint(&q);break;default:printf("输入无效,请重新输入\n");break;}} while (input);
}
int main()
{test();return 0;
}
Queue.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "Queue.h"void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;QueueLoad(pq);
}void QueueDestory(Queue* pq)
{assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("newnode");return;}newnode->data = x;newnode->next = NULL;if (pq->head == NULL){assert(pq->tail == NULL);pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}void QueuePop(Queue* pq)
{assert(pq);assert(pq->head != NULL);//方法1//QNode* next = pq->head->next;//free(pq->head);//pq->head = next;//if (pq->head == NULL)//{// pq->tail = NULL;//}//方法2if (pq->head->next == NULL){free(pq->head);pq->tail = pq->head = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;
}
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
bool QueueEmpty(Queue* pq)
{assert(pq);//return pq->size == 0;return pq->head == NULL && pq->tail == NULL;
}QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}void QueuePrint(Queue* pq)
{assert(pq);QNode* cur = pq->head;if (QueueEmpty(pq)){printf("队列为空\n");return;}else{while (cur){printf("%d ", cur->data);cur = cur->next;}printf("\n");}
}
void QueueMiddlePush(void(*pf)(Queue* pq, QDataType x), Queue* pq)
{int x = 0;printf("请输入你想要插入的元素:>");scanf("%d", &x);pf(pq, x);QueuePrint(pq);
}void QueueMiddle(Queue* pq, int num)
{if (num == 2){if (QueueEmpty(pq)){printf("队列已空,无法出队\n");}else{printf("出队元素:%d\n", QueueFront(pq));QueuePop(pq);}}else if (num == 4){if (QueueEmpty(pq)){printf("队列已空,无队头元素\n");}else{printf("队头元素:%d\n", QueueFront(pq));}}else if (num == 5){if (QueueEmpty(pq)){printf("队列已空,无队尾元素\n");}else{printf("队尾元素:%d\n", QueueBack(pq));}}else{if (QueueEmpty(pq)){printf("队列已空\n");}else{printf("队列不为空\n");}}
}void QueueSave(Queue* pq)
{assert(pq);FILE* pf = fopen("queue.txt", "w");if (pf == NULL){perror("无法打开文件");return;}QNode* cur = pq->head;while (cur){fprintf(pf, "%d ", cur->data);cur = cur->next;}fclose(pf);pf = NULL;printf("保存文件成功\n");
}void QueueLoad(Queue* pq)
{assert(pq);FILE* pf = fopen("queue.txt", "r");if (pf == NULL){// 文件不存在或无法打开，可能是第一次运行return;}int data = 0;while (fscanf(pf, "%d", &data) != EOF){QueuePush(pq, data);}fclose(pf);pf = NULL;
}
代 码 效 果 展 示
菜 单 展 示
每 次 循 环 开 始 时 会 显 示 菜 单，内 容 包 括：
QueueExit：退 出 程 序 并 将 队 列 元 素 保 存 到 文 件 中
QueuePush：入 队 列
QueuePop：出 队 列
QueueSize：获 取 队 列 中 有 效 元 素 个 数
QueueFront：取 出 队 头 的 数 据
QueueBack：取 出 队 尾 的 数 据
QueueEmpty：检 查 队 列 是 否 为 空
QueuePrint：输 出 队 列 元 素
退 出 程 序（QueueExit）
输 入 0 后，程 序 会 将 队 列 中 的 信 息 保 存 到 文 件 “queue.txt” 中。释 放 内 存 并 销 毁 队 列， 然 后 退 出 程 序。
入 队 列（QueuePush）
输 入 1 后，程 序 会 提 示 用 户 输 入 插 入 的 数 字。输 入 完 成 后，数 字 被 添 加 到 队 列 的 末 尾，然 后 输 出 修 改 后 的 队 列。
出 队 列（QueuePop）
输 入 2 后，队 列 的 头 部 的 数 字 会 被 删 除，并 输 出 删 除 的 元 素（出 队 的 元 素）。
队 列 中 有 效 元 素 个 数（QueueSize）
输 入 3 后，程 序 会 输 出 队 列 中 的 元 素 个 数。
取 出 队 头 元 素（QueueFront）
输 入 4 后，程 序 会 输 出 队 列 的 头 部 元 素（队 列 的 第 一 个 元 素）。
取 出 队 尾 元 素（QueueBack）
输 入 5 后，程 序 会 输 出 队 列 的 尾 部 元 素（队 列 的 最 后 一 个 元 素）。
检 查 队 列 是 否 为 空（QueueEmpty）
输 入 6 后，程 序 会 检 查 队 列 是 否 为 空，如 果 队 列 为 空，则 输 出 队 列 是 空，如 果 队 列 不 为 空，则 输 出 队 列 不 为 空。
输 出 队 列 元 素（QueuePrint）
输 入 7 后，程 序 会 在 屏 幕 上 显 示 目 前 已 经 保 存 的 队 列 元 素。
栈 与 队 列 的 对 比 分 析
| 对比 | 栈（Stack） | 队列（Queue） |
|---|---|---|
| 操作限制 | 仅在栈顶进行插入和删除 | 队尾插入，队头删除 |
| 数据原则 | 后进先出 | 先进先出 |
| 典型操作 | Push（入栈）、Pop（出栈） | Enqueue（入队）、Dequeue（出队） |
| 实现方式 | 数组或链表 | 数组或链表（通常链表更优） |
| 内存管理 | 通常需要考虑扩容 | 链表实现时动态分配节点 |
总 结 与 进 阶 建 议
核 心 知 识 点 回 顾
1、栈 是 一 种 先 进 后 出 的 数 据 结 构，所 有 操 作 集 中 在 栈 顶，适 合 需 要 “回 退” 逻 辑 的 场 景。
2、队 列 是 一 种 先 进 先 出 的 数 据 结 构，插 入 在 队 尾，删 除 在 队 头，适 合 需 要 保 持 顺 序 的 场 景。
3、两 者 都 是 线 性 数 据 结 构，但 操 作 方 式 截 然 不 同。
4、代 码 实 现 上，栈 可 以 用 数 组 或 链 表，队 列 更 倾 向 于 链 表 实 现 以 避 免 “假 溢 出”。
学 习 进 阶 建 议
深 入 理 解 原 理：尝 试 分 析 不 同 场 景 下 栈 和 队 列 的 效 率 差 异。
拓 展 实 现 方 式：尝 试 用 不 同 数 据 结 构 实 现 栈 和 队 列 （如 双 向 循 环 链 表）。
总 结
至 此，关 于 栈 和 队 列 的 探 索 暂 告 一 段 落，但 你 的 编 程 征 程 才 刚 刚 启 航。编 写 代 码 是 与 计 算 机 逻 辑 深 度 对 话，过 程 中 虽 会 在 结 构 设 计、算 法 实 现 的 困 境 里 挣 扎，但 这 些 磨 砺 加 深 了 对 代 码 逻 辑 和 数 据 组 织 的 理 解。愿 你 合 上 电 脑 后，灵 感 不 断，在 数 据 结 构 的 世 界 里 持 续 深 耕，书 写 属 于 自 己 的 编 程 传 奇，下 一 次 开 启，定 有 全 新 的 精 彩 等 待。小 编 期 待 重 逢，盼 下 次 阅 读 时 见 证 你 们 更 大 的 进 步，共 赴 代 码 之 约！