我的数据结构4-栈和队列

（叠甲：如有侵权请联系，内容都是自己学习的总结，一定不全面，仅当互相交流（轻点骂）我也只是站在巨人肩膀上的一个小卡拉米，已老实，求放过）

一、栈（Stack）

1. 核心概念

栈是只允许在一端进行插入和删除操作的线性表。
允许操作的一端称为栈顶（Top），固定的另一端称为栈底（Bottom）
核心特性：后进先出（LIFO, Last In First Out）—— 最后入栈的元素最先被取出
空栈：不含任何元素的栈

2. 基本操作（ADT 定义）

栈的所有操作都围绕栈顶进行，单步时间复杂度均为 O(1)

操作	功能说明
InitStack(&S)	初始化一个空栈
Push(&S, x)	元素 x 入栈（插入到栈顶）
Pop(&S, &x)	栈顶元素出栈，用 x 返回其值
GetTop(S, &x)	读取栈顶元素，不删除
StackEmpty(S)	判断栈是否为空
StackSize(S)	返回栈中元素个数
DestroyStack(&S)	销毁栈，释放空间

3. 两种存储实现

（1）顺序栈（数组实现）

用连续数组存储元素，搭配top变量标记栈顶下标，是最常用的实现方式。

结构体定义（C 语言）：

#define MaxSize 100 // 栈的最大容量 typedef struct { int data[MaxSize]; // 存储栈元素 int top; // 栈顶指针，初始值为-1表示空栈 } SqStack;

核心操作实现：
初始化：S.top = -1;
入栈：先移动栈顶指针，再赋值

bool Push(SqStack &S, int x) { if (S.top == MaxSize - 1) return false; // 栈满，上溢 S.data[++S.top] = x; return true; }

出栈：先取值，再移动栈顶指针

bool Pop(SqStack &S, int &x) { if (S.top == -1) return false; // 栈空，下溢 x = S.data[S.top--]; return true; }

• 读栈顶：x = S.data[S.top];
• 判空：return S.top == -1;

注意：也存在top初始为 0 的实现，此时栈顶元素为data[top-1]，入栈先赋值再top++。考研主流写法为top=-1。

（2）链式栈（单链表实现）

用单链表存储，链表头部作为栈顶，入栈用头插法，出栈用头删法，天然无栈满限制。

结构体定义：

typedef struct LinkNode { int data; struct LinkNode *next; } LinkNode, *LiStack;

核心特点：入栈、出栈均为 O(1)，无需遍历，适合元素数量波动大、无法预估容量的场景
缺点：每个节点需额外存储指针，存在空间开销

n 个不同元素依次入栈，合法出栈序列的总数为卡特兰数：

//slist.h #pragma once #include<stdio.h> #include<assert.h> #include<stdlib.h> typedef int SLTDataType; typedef struct SlitNode { SLTDataType data; struct SLTNode* next; }SLTNode; //初始化 void SLPInit(SLTNode* phead); //打印 void SLTPrint(SLTNode*phead); //头插 void SLPushFront(SLTNode** phead, SLTDataType x); //尾插 void SLPushBack(SLTNode** phead, SLTDataType x); //头删 void DestroyFront(SLTNode** phead); //尾删 void DestroyBack(SLTNode** phead); //查找 SLTNode* SLTFind(SLTNode* phead, SLTDataType x); //修改 void SLTChange(SLTNode* phead, SLTDataType x, SLTDataType y); //销毁 void SLTDestroy(SLTNode** phead); //中间位置插入 void SLTIsert(SLTNode* phead, SLTDataType x , SLTDataType y);

//slist.c #include"slist.h" //初始化 void SLPInit(SLTNode* phead) { phead->data = 0; phead->next = NULL; } void SLTPrint(SLTNode* phead) { SLTNode* cur = phead; while (cur) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); } SLTNode* newnode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); if (newnode==NULL) { perror("malloc faild:"); return NULL; } newnode->data = x; newnode->next = NULL; return newnode; } void SLPushFront(SLTNode** phead, SLTDataType x) { SLTNode* cur = newnode(x); if (*phead == NULL) { *phead = cur; } else { cur->next = *phead; *phead = cur; } } void SLPushBack(SLTNode** phead, SLTDataType x) { SLTNode* cur = newnode(x); if (*phead == NULL) { *phead = cur; } else { SLTNode* tial = *phead; while (tial->next!=NULL) { tial = tial->next; } tial->next = cur; } } void DestroyFront(SLTNode ** phead) { assert(*phead); if ((*phead)->next == NULL) { free(*phead); *phead = NULL; } else { SLTNode* cur = *phead; *phead = (*phead)->next; free(cur); cur = NULL; } } void DestroyBack(SLTNode** phead) { assert(*phead); if ((*phead)->next == NULL) { free(*phead); *phead = NULL; } else { SLTNode* tail = *phead; SLTNode* cur = NULL; while (tail->next) { cur = tail; tail = tail->next; } free(tail); tail = NULL; cur->next = NULL; } } //查找 SLTNode* SLTFind(SLTNode* phead, SLTDataType x) { assert(phead); SLTNode* cur = phead; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } void SLTChange(SLTNode* phead, SLTDataType x, SLTDataType y) { assert(phead); SLTNode* node = SLTFind(phead, x); node->data = y; } void SLTDestroy(SLTNode** phead) { assert(*phead); SLTNode* cur = *phead; while (cur) { cur= (cur)->next; free(*phead); *phead = cur; } free(cur); free(*phead); *phead = NULL; } //中间位置插入 void SLTIsert(SLTNode* phead, SLTDataType x, SLTDataType y) { SLTNode* cur = NULL; SLTNode* node = SLTFind(phead, x); SLTNode* new = newnode(y); cur = node->next; node->next = new; new->next = cur; }

//test.c #define _CRT_SECURE_NO_WARNINGS 1 #include"slist.h" int main() { SLTNode* list = NULL; SLPushFront(&list,1); SLPushFront(&list,2); SLPushFront(&list,3); SLPushFront(&list,4); //SLPushBack(&list, 5); //SLPushBack(&list, 6); //SLPushBack(&list, 7); /*DestroyFront(&list); SLTPrint(list); DestroyFront(&list); SLTPrint(list); DestroyFront(&list); SLTPrint(list); DestroyFront(&list); SLTPrint(list); DestroyFront(&list); SLTPrint(list);*/ //DestroyBack(&list); //SLTPrint(list); //DestroyBack(&list); //SLTPrint(list); //DestroyBack(&list); //SLTPrint(list); //DestroyBack(&list); /*SLTPrint(list); SLTChange(list,3,6); SLTPrint(list); SLTDestroy(&list); SLTPrint(list);*/ SLTPrint(list); SLTIsert(list,4, 5); SLTPrint(list); return 0; }

二、队列（Queue）

1. 核心概念

队列是只允许在一端插入、另一端删除的线性表。
插入端称为队尾（Rear），删除端称为队头（Front）
核心特性：先进先出（FIFO, First In First Out）—— 最先入队的元素最先被取出
空队列：不含任何元素的队列

2. 基本操作（ADT 定义）

所有单步操作时间复杂度均为 O(1)：

操作	功能说明
InitQueue(&Q)	初始化空队列
EnQueue(&Q, x)	元素 x 入队（插入队尾）
DeQueue(&Q, &x)	队头元素出队，用 x 返回
GetHead(Q, &x)	读取队头元素，不删除
QueueEmpty(Q)	判断队列是否为空
QueueSize(Q)	返回队列元素个数
DestroyQueue(&Q)	销毁队列

3. 三种存储实现

（1）普通顺序队列（存在缺陷）

用数组存储，front 标记队头，rear 标记队尾下一个位置。
缺陷：随着入队出队，两个指针不断后移，数组前部空间无法复用，产生假溢出。

（2）循环队列（顺序存储最优解）

将数组逻辑上视为环形，通过取模运算让指针绕回数组开头，彻底解决假溢出问题

#define MaxSize 100 typedef struct { int data[MaxSize]; int front; // 队头指针，指向队头元素 int rear; // 队尾指针，指向队尾元素的下一个位置 } SqQueue;

初始化：Q.front = Q.rear = 0;

核心操作：

• 入队：

bool EnQueue(SqQueue &Q, int x) { if (队满) return false; Q.data[Q.rear] = x; Q.rear = (Q.rear + 1) % MaxSize; // 指针循环后移 return true; }

出队：

bool DeQueue(SqQueue &Q, int &x) { if (队空) return false; x = Q.data[Q.front]; Q.front = (Q.front + 1) % MaxSize; // 指针循环后移 return true; }

判空与判满的三种方案（重点）：

由于front == rear既可能表示空也可能表示满，需通过额外规则区分：

方案	判空条件	判满条件	元素个数计算
牺牲 1 个存储单元（最常用）	front == rear	(rear + 1) % MaxSize == front	(rear - front + MaxSize) % MaxSize
增加 size 计数器	size == 0	size == MaxSize	直接返回 size
增加 tag 标记位	front == rear && tag == 0	front == rear && tag == 1	结合 tag 推导

（3）链式队列

用带头结点的单链表实现，同时保存队头和队尾指针，入队尾插、出队头删，无队满限制。

结构体定义：

typedef struct LinkNode { int data; struct LinkNode *next; } LinkNode; typedef struct { LinkNode *front; // 队头指针 LinkNode *rear; // 队尾指针 } LinkQueue;

4. 队列的常见变种

• 双端队列（Deque）：两端都可以入队和出队。进一步分为输入受限、输出受限双端队列。
• 优先队列：每次出队返回优先级最高的元素，底层由堆实现，不属于普通线性队列。

//queue.h #pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> //队列：只允许在一端插入数据操作，先入先出，进行插入操作的一端被称为队尾，进行删除的一端叫做对头 //队列可以由数组与链表结构实现，但是使用链表的结构更优，因为使用数组，出队列在数组头出数据，效率会比较低下 //单链表 typedef int QDataType; typedef struct QListNode { struct QListNode* next; QDataType data; }QNode; typedef struct Queue { QNode* front; QNode* rear; }Queue; //初始化队列 void QueueInit(Queue* q); //判断队列是否为空 bool QueueEmpty(Queue* q); //对头出队列 void QueuePop(Queue* q); //获取队头的数据 QDataType QueueFront(Queue* q); //获取队尾的数据 QDataType QueueRear(Queue* q); //获取队列有效个数 int QueueSize(Queue* q); //销毁队列 void QueueDestory(Queue* q);

//queue.c #define _CRT_SECURE_NO_WARNINGS 1 #include"Queue.h" //队列初始化 void QueueInit(Queue* q) { assert(q); q->front = NULL; q->rear = NULL; } //队尾入队 void QueuePush(Queue* q, QDataType x) { QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail\n"); return ; } newnode->data = x; newnode->next = NULL; if (q->rear == NULL) { assert(q->front == NULL); q->rear = newnode; q->front = newnode; } else { q->rear->next = newnode; q->rear = newnode; } } //判断队列是否为空 bool QueueEmpty(Queue* q) { assert(q); return q->front==NULL; } //对头出队列 void QueuePop(Queue* q) { assert(q); assert(!QueueEmpty(q)); if (q->front->next == NULL) { free(q->front); q->front = NULL; q->rear = NULL; } QNode* next = q->front->next; free(q->front); q->front = next; } //获取对头的数据 QDataType QueueFront(Queue* q) { assert(q); assert(!QueueEmpty(q)); return q->front->data; } //获取队尾的数据 QDataType QueueRear(Queue* q) { assert(q); assert(!QueueEmpty(q)); return q->rear->data; } //获取队列有效个数 int QueueSize(Queue* q) { assert(q); assert(!QueueEmpty(q)); size_t size = 0; QNode* cur = q->front; while (cur) { ++size; cur = cur->next; } return size; } void QueueDestory(Queue* q) { while (q->front) { QueuePop(q); } }

//test.c #define _CRT_SECURE_NO_WARNINGS 1 #include"Queue.h" int main() { Queue q; QueueInit(&q); QueuePush(&q, 1); QueuePush(&q, 2); QueuePush(&q, 3); QueuePush(&q, 4); QueuePush(&q, 5); printf("%d\n", QueueFront(&q)); printf("%d\n", QueueSize(&q)); QueuePop(&q); printf("%d\n", QueueFront(&q)); printf("%d\n", QueueSize(&q)); QueuePop(&q); printf("%d\n", QueueRear(&q)); printf("%d\n", QueueSize(&q)); QueuePop(&q); printf("%d\n", QueueRear(&q)); QueuePop(&q); printf("%d\n", QueueRear(&q)); return 0; }

三、栈 vs 队列 核心对比

维度	栈	队列
核心规则	后进先出（LIFO）	先进先出（FIFO）
操作端	仅栈顶一端可插入、删除	队尾插入、队头删除，两端操作
顺序存储	普通数组即可	普通数组有假溢出，需用循环队列
典型遍历思想	深度优先（DFS）	广度优先（BFS）
基础操作复杂度	入栈 / 出栈 O(1)	入队 / 出队 O(1)

#pragma once

一、核心作用与原理

C/C++ 的#include本质是文本级别的原样替换：编译器会把被包含的头文件内容，完整插入到#include所在的位置。

如果一个头文件被多次包含（比如 A 包含 B，C 同时包含 A 和 B，那么 B 就会被间接包含两次），头文件里的结构体、全局变量、函数声明、宏定义等就会被重复定义，直接触发编译报错（典型错误：redefinition of 'xxx'）。

#pragma once的工作逻辑很简单：

• 写在头文件的最开头，编译器第一次处理这个头文件时会标记该文件；
• 后续编译过程中，只要再遇到#include这个文件，编译器会直接跳过，不会再次展开文件内容。

二、和传统头文件卫士的对比

在#pragma once普及之前，标准的头文件保护方式是「条件编译卫士」，写法如下：

// 比如 file.h #ifndef FILE_H // 如果没定义过 FILE_H 这个宏 #define FILE_H // 定义这个宏，标记文件已被包含 // 头文件的所有代码内容... #endif // 结束条件编译

特性	#pragma once	#ifndef/#define/#endif卫士
标准性	非 C/C++ 官方标准，属于编译器扩展	C/C++ 标准语法，所有编译器 100% 兼容
写法	一行代码，简洁不易写错	需要三行，且宏名必须全局唯一
编译效率	更高：编译器直接通过文件身份判断，无需重复进入文件预处理	稍低：每次都要进入文件检查宏是否定义
潜在风险	极端场景：同一份头文件有多个物理副本时，会被识别为不同文件，仍会重复包含	宏名如果和其他头文件冲突，会导致头文件内容莫名丢失，bug 更隐蔽

三、使用注意事项

必须写在头文件最顶部，位于所有代码、其他预处理指令之前，否则可能失效。
目前主流编译器（GCC、Clang、MSVC、MinGW 等）全部支持 #pragma once，工业界绝大多数项目都在使用，兼容性已不再是实际问题。
不建议两种方式混用，一个头文件写一次 #pragma once 即可。
它只能防护「同一个物理文件」的重复包含，不能解决不同文件里的同名定义冲突。
简单总结：#pragma once 是更现代、更省心的头文件保护方案，日常写 C/C++ 项目优先用它就可以。

我们用 4 个文件完整复现这个场景，例子完全贴合你正在学习的栈结构，一步步拆解「重复包含 → 触发报错 → 加保护后修复」的全过程。

一、无保护的错误版本

我们先写不带任何头文件保护的代码，复现编译错误。

4 个文件的代码

1. stack.h（栈结构定义头文件，无保护）

这个文件定义了顺序栈的结构体和函数声明，会被其他文件多次引用。

// stack.h —— 没有加任何头文件保护 #include <stdbool.h> #define MaxSize 100 // 定义顺序栈结构体 typedef struct { int data[MaxSize]; int top; } SqStack; // 栈操作函数声明 void InitStack(SqStack *S); bool Push(SqStack *S, int x);

2.func1.h（功能模块 1，依赖栈）

// func1.h —— 业务模块1，需要用到栈结构 #include "stack.h" void func1(SqStack *S); // 用栈实现功能1

3. func2.h（功能模块 2，也依赖栈）

// func2.h —— 业务模块2，也需要用到栈结构 #include "stack.h" void func2(SqStack *S); // 用栈实现功能2

4. main.c（主程序，同时引用两个模块）

// main.c —— 主程序同时用到两个业务模块 #include <stdio.h> #include "func1.h" #include "func2.h" int main() { SqStack S; InitStack(&S); Push(&S, 10); func1(&S); func2(&S); return 0; }

为什么会报错？手动模拟展开过程

#include的本质是文本原样替换。预编译阶段，编译器会把所有#include引用的文件内容，原封不动地粘贴到当前位置。

我们一步步展开main.c：

1. 先展开#include "func1.h"→ 里面又包含stack.h→ 第一次粘贴stack.h的全部内容
2. 再展开#include "func2.h"→ 里面又包含stack.h→ 第二次粘贴stack.h的全部内容

展开后，main.c里相当于出现了两份完全相同的栈结构体定义，简化后如下：

// ===== 第一次展开 stack.h 的内容 ===== #include <stdbool.h> #define MaxSize 100 typedef struct { int data[MaxSize]; int top; } SqStack; void InitStack(SqStack *S); bool Push(SqStack *S, int x); void func1(SqStack *S); // ===== 第二次展开 stack.h 的内容 ===== #include <stdbool.h> #define MaxSize 100 // 宏重复定义警告 typedef struct { // 结构体重复定义，直接编译错误 int data[MaxSize]; int top; } SqStack; void InitStack(SqStack *S); bool Push(SqStack *S, int x); void func2(SqStack *S);

实际编译报错信息
用 GCC 编译时，会输出典型的重复定义错误：

error: redefinition of 'struct SqStack' error: redefinition of typedef 'SqStack' warning: "MaxSize" redefined

C 语言不允许同一个结构体、typedef、全局变量在同一作用域下被定义多次，因此直接编译失败。

二、加上 #pragma once 修复

只需要修改 stack.h，在文件最开头加一行 #pragma once：

#pragma once // 头文件保护：本文件只被包含一次 #include <stdbool.h> #define MaxSize 100 typedef struct { int data[MaxSize]; int top; } SqStack; void InitStack(SqStack *S); bool Push(SqStack *S, int x);

修复原理
编译器处理头文件时会做标记：
第一次遇到 #include "stack.h"：正常展开内容，并标记「stack.h 已处理过」
第二次再遇到 #include "stack.h"：检测到已标记，直接跳过整个文件，不再展开内容
最终 main.c 里只会保留一份 stack.h 的内容，结构体、宏都只定义一次，编译顺利通过。

三、补充说明

不是所有重复包含都会报错
只有头文件里包含「定义类内容」时才会报错，比如结构体定义、全局变量定义、函数实现、宏定义；
如果头文件只有函数声明，重复包含通常不会报错，但会增加预编译耗时，依然是不良写法。
保护的是同一个物理文件
#pragma once 只能防止「同一个文件」被多次包含。如果两份内容相同的头文件放在不同路径下，它会识别为两个不同文件，仍然会重复定义。
传统 #ifndef 卫士效果完全一致
老式写法是用条件编译实现同等效果，原理是通过宏标记是否已包含：

#ifndef STACK_H // 如果没定义过STACK_H这个宏 #define STACK_H // 定义宏，标记文件已进入 #include <stdbool.h> // ... 头文件全部内容 #endif

#include<stdbool.h>

#include <stdbool.h>是 C 语言中引入布尔类型支持的标准头文件包含语句，它的核心作用是：让 C 语言可以像其他语言一样，使用bool、true、false来表示布尔逻辑，让代码的语义更清晰、可读性更强。

一、背景：C 语言原本没有布尔类型

在 C99 标准（1999 年）之前，C 语言没有原生的布尔类型，大家普遍用整数来模拟真假：

• 用0表示「假」
• 用非0（通常是1）表示「真」

// 没有 stdbool.h 时，只能用 int 返回真假 int Push(SqStack &S, int x) { if (栈满) return 0; // 0 代表失败/假 // ... return 1; // 1 代表成功/真 }

这种写法的问题是：int语义不明确，读者无法一眼看出这是个布尔标志，还是普通整数。

二、stdbool.h 到底提供了什么

C99 标准新增了原生布尔关键字 _Bool（这是 C 语言真正的布尔类型），但名字很反直觉。于是配套推出了 <stdbool.h> 头文件，里面通过宏定义做了一层友好的别名包装：

宏名	展开后等价于	含义
bool	_Bool	布尔类型名，只能存储 0 或 1
true	整数常量1	逻辑真
false	整数常量0	逻辑假

也就是说，只要你在代码开头加上 #include <stdbool.h>，就可以直接写 bool、true、false，编译器会自动替换成 C 原生支持的语法。
之前的栈代码就可以写成更易读的版本：

#include <stdbool.h> bool Push(SqStack &S, int x) { if (S.top == MaxSize - 1) return false; // 语义明确：失败 S.data[++S.top] = x; return true; // 语义明确：成功 }

三、_Bool 类型的特性

_Bool 是 C 语言真正的布尔类型，和普通 int 有区别：
它只能存 0 和 1 两个值。
如果你给 bool 变量赋一个非 0 的整数（比如 5、-3），编译器会自动转换成 1，保证值只有真假两种状态。

bool flag = 100; printf("%d", flag); // 输出 1，而不是 100

四、关键注意事项

1. 标准依赖：stdbool.h是 C99 及以后标准才有的，现代编译器（GCC、Clang、MSVC）默认都支持，无需额外配置。
2. C++ 不需要它：C++ 语言本身就把bool、true、false作为内置关键字，不需要包含任何头文件。只有纯 C 代码才需要#include <stdbool.h>。
3. 本质是宏：bool不是 C 语言的原生关键字（C23 之前），它是stdbool.h定义的宏，底层还是_Bool。

简单总结：这行代码就是给 C 语言补上「布尔类型」的语法糖，让代码里的真假判断更直观、更易维护，也是写 C 语言数据结构代码时的常用头文件。