1. 栈

1.1 栈的基本概念

• 线性表 (linear list) 是相同类型的 n (n>=0) 个数据元素的有限序列，若用 L 命名为线性表，则一般表示为 \(L = (a_1,a_2,…,a_i,a_{i+1},…,a_n)\)
• 栈 (stack) 是限定仅在一端进行插入或删除操作的线性表。因此，对栈来说进行插入删除数据的这一端称为栈顶 (top)，另一端称为栈底 (bottom)，不含元素的空表称为空栈。栈中的数据元素遵循后进先出 (LIFO Last In First Out) 的特性。
• 栈插入和删除数据都在栈顶端，插入数据一般叫做入栈 / 进栈，删除数据一般叫做出栈。

这张图可以很好的帮助我们了解栈的进出方式，既然栈是线性表那么就可以分为顺序存储和链式存储。

1.2 入栈和出栈顺序

假设入栈顺序为 a1,a2,a3,a4,a5，那么出栈顺序是什么呢？大家最容易想到的是所有数据都入栈以后再出栈就是 a5,a4,a3,a2,a1；实际上有多种出栈顺序，比如每个数据入栈以后马上出栈，所以另一种出栈顺序也可以是 a1,a2,a3,a4,a5；还可以是 a1,a2,a3 入栈，出 a3,a2，再入栈 a4,a5，再出栈 a5,a4,a1，也就是说出栈顺序为 a3,a2,a5,a4,a1；通过分析我们可以看到因为出栈时机的不同，可以有很多种出栈顺序。

一句话：一种入栈顺序可以有多种出栈顺序。

至于有多少种出栈顺序，出栈顺序组合数是⼀个卡特兰数：

具体的推导过程我这里就不详细讲述了，你们可以自己去搜索资料了解一下，这个公式我们校招并没有要求，但是我们考408的同学就要注意一下它的推导过程了。

1.3 栈的基本操作

栈是⼀种只允许在⼀端进⾏插⼊和删除的线性表，栈插⼊和删除数据都在栈顶端，插⼊数据⼀般叫 做⼊栈，删除数据⼀般叫做出栈，所栈最核⼼的接⼝函数就是⼊栈和出栈函数。

// 栈的初始化 void StackInit(Stack& s); // 栈的销毁 void StackDestroy(Stack& s); // x元素入栈(进栈) void StackPush(Stack& s, STDataType x); // 将栈顶元素出栈，并用返回栈顶元素 STDataType StackPop(Stack& s); // 获取栈顶元素并返回 STDataType StackTop(Stack& s); // 获取栈中有效元素个数 int StackSize(Stack& s); // 检测栈是否为空，如果是空返回真，否则返回假 bool StackEmpty(Stack& s);

这些关于栈的相关接口，你们自己一定要尝试一下能不能自主完成。

1.3.1 栈的结构定义

跟顺序表类似，栈的顺序存储实现可以使⽤静态数组，我们称为静态顺序栈，也可以使⽤堆上动态申 请数组实现，我们称为动态顺序栈。静态顺序栈的缺陷跟静态顺序表类似，只适⽤于确定知道最多需 要多少空间的场景，那么我们后续重点讲解动态数组实现的版本。

静态栈结构定义：

#define MAX_SIZE 10 typedef int STDataType; typedef struct{ STDataType arr[MAX_SIZE]; int top; // 标记栈顶 }Stack;

动态栈结构定义：

typedef int STDataType; typedef struct{ STDataType* arr; // 指向栈数组空间的指针 int top; // 栈顶位置 int capacity; // 容量 }Stack;

1.3.2 动态顺序栈实现

有了前面学习顺序表的基础，这里我们实现动态顺序栈简直小菜一碟。相比而言这里的入栈和出栈操作还要更简单一些。

需要注意的是栈结构中初始化时，top=-1还是top=0，top=-1代表 top 指向栈顶元素，那么入栈时要先++top，再把入栈数据放到 top 位置。top=0代表 top 指向栈顶元素的下一个位置，那么入栈时要先把入栈数据放到 top 位置，再++top。其他接口函数处理细节也要对应调整。这两种方式没有优劣之分，大家任选一种即可！

为何初始化时top=0，不能代表 top 指向栈顶元素呢？那我们要思考栈为空和栈只有一个数据时，top 都是 0，如何区分呢？

这两种定义方式也就决定了，我们再入栈和出栈的时候是先top++，还是先存数据。

栈接口的实现：

#define _CRT_SECURE_NO_WARNINGS #include"SeqStack.h" //栈的初始化 void StackInit(Stack* s) { assert(s); s->arr = (STDataType*)malloc(4 * sizeof(STDataType)); if (s->arr == NULL) { perror("StackInit()::malloc()"); return; } s->top = 0; s->capacity = 4; } // 栈的销毁 void StackDestroy(Stack* s) { assert(s); if (s->arr == NULL) { return; } free(s->arr); s->arr = NULL; s->capacity = 0; s->top = 0; } // x元素⼊栈(进栈) void StackPush(Stack* s, STDataType x) { assert(s); assert(StackEmpty != NULL); //满了 if (s->top == s->capacity) { STDataType* tmp = (STDataType*)realloc(s->arr, sizeof(STDataType) * s->capacity * 2); if (tmp == NULL) { perror("StackPush()::realloc()"); return; } s->arr = tmp; s->capacity *= 2; } //未满 s->arr[s->top] = x; s->top++; } // 将栈顶元素出栈，并⽤返回栈顶元素 STDataType StackPop(Stack* s) { assert(s); assert(StackEmpty != NULL); STDataType x = s->arr[s->top - 1]; s->top--; return x; } // 获取栈顶元素并返回 STDataType StackTop(Stack* s) { assert(s); assert(StackEmpty != NULL); return s->arr[s->top - 1]; } //获取栈中有效元素个数 int StackSize(Stack* s) { assert(s); return s->top; } //检测栈是否为空，如果是空返回真，否则返回假 bool StackEmpty(Stack* s) { assert(s); if (s->top = 0) { return false; } return true; }

这个是顺序存储不是链式存储，这是动态顺序存储，后续我们还要实现动态链式存储。

1.4 栈的链式存储

我们学习了这么多链式存储方式，这里我们可以使用那种方式来存储呢？

• 栈的链式存储，我们可以选用单链表结构，也可以选用双向链表结构。但是需要注意的是，如果选用单链表必须用链表头这一端做栈顶，入栈出栈就是对应头插头删，时间复杂度为\(O(1)\)。否则用链表尾做栈顶，出栈对应尾删代价太大了，时间复杂度为O(N)。
• 如果选用双向链表，则用表头表尾做栈顶都可以，因为双向链表头尾插入删除效率都是\(O(1)\)。当然我们完全没必要选择双向链表，因为单链表就可以高效实现，还省空间一些。双向链表没有优势，每个结点还要多存储一个前驱指针，使用它纯粹浪费了。
• 其次我们选择单链表实现，可以带头结点，也可以不带头结点；但是这里入栈出栈就是对应头插头删，单链表带头结点时，头插头删并不会带来什么便利，所以一般我们选择不带头结点实现即可。

#define _CRT_SECURE_NO_WARNINGS #include"LinkStack.h" // 初始化链式栈s void LinkStackInit(LinkStack* s) { assert(s); s->topHead = NULL; s->size = 0; } // 销毁链式栈s void LinkStackDestroy(LinkStack* s) { LNode* cur = s->topHead; while (cur) { LNode* next = cur->next; free(cur); cur = next; } s->size = 0; s->topHead = NULL; } // x入栈 void LinkStackPush(LinkStack* s, STDataType x) { assert(s); LNode* newNode = (LNode*)malloc(sizeof(LNode)); if (newNode == NULL) { perror("LinkStackPush()::malloc()"); return; } newNode->data = x; newNode->next = s->topHead; s->topHead = newNode; s->size++; } // 出栈，并返回栈顶元素 STDataType LinkStackPop(LinkStack* s) { assert(s); assert(!LinkStackEmpty(s)); LNode* delNode = s->topHead; LNode* topE = delNode->data; s->topHead = delNode->next; free(delNode); delNode = NULL; s->size--; return topE; } // 获取栈顶元素 STDataType LinkStackTop(LinkStack* s) { return s->topHead->data; } // 获取栈中有效元素个数 int LinkStackSize(LinkStack* s) { return s->size; } // 检测栈是否为空，如果是空返回真，否则返回假 bool LinkStackEmpty(LinkStack* s) { return (s->size == 0); }

1.4.1 入栈

我们无论是入栈还是出栈的时候都一定要考虑，临界情况的问题，入栈时链表为空，我们该怎入？是不是和正常情况是一样的，还是说要分情况讨论。

我们这里的入栈时链表为空时的逻辑和正常情况下的是一样的。

// x入栈 void LinkStackPush(LinkStack* s, STDataType x) { assert(s); // 1. 申请新结点 LSNode* newNode = (LSNode*)malloc(sizeof(LSNode)); if (NULL == newNode) { printf("LinkStackPush:申请节点失败"); exit(-1); } newNode->data = x; newNode->next = s->topHead; s->topHead = newNode; s->size++; }

1.4.2 出栈

出栈时链表中还有一个链表和多个链表的情况是一样的。

// 出栈，并返回栈顶元素 STDataType LinkStackPop(LinkStack* s) { assert(s); assert(!LinkStackEmpty(s)); LNode* delNode = s->topHead; LNode* topE = delNode->data; s->topHead = delNode->next; free(delNode); delNode = NULL; s->size--; return topE; }

1.5 栈的链式存储和顺序存储的区别

• 栈的顺序存储和链式存储都可以做到入栈和出栈时间复杂度为\(O(1)\)，效率都很高。
• 栈的顺序存储的唯一问题是入栈时空间不够，扩容有一定的消耗，但是这个消耗几乎可以忽略不计，因为插入一定量数据才会扩容。
• 栈的顺序存储相比链式存储 CPU 高速缓存命中率较高，且没有内存碎片。所以栈的实现一般我们使用顺序存储。

前两点我觉得还是很好理解的，但是第三点，这个cpu缓存命中率是什么呢？

我们的cpu在读取数据的时候，是在缓存中读取的，缓存中的数据又是在内存中缓存的，我们的缓存区就是为了可以不用每次读取数据的时候cpu直接去内存中读取，我们缓存区先从内存中读取一块连续的内存，cpu再在缓存区中读取想要的数据，如果没有读取到，缓存区会继续去内存中读取另一块内存，再给cpu读取，我们将cpu读取数据时，读取到数据叫为cpu的命中，因为缓存区在读取数据的时候时一块一块读取的，我们的链式存储是零碎的，顺序存储是一块的，这就是为什么说顺序存储的命中率较高的原因。

2. 队列

• 线性表 (linear list) 是相同类型的n(n>=0)个数据元素的有限序列，若用 L 命名为线性表，则一般表示为 \(L = (a_1,a_2,…,a_i,a_{i+1},…,a_n)\)
• 队列 (queue) 是限定在一端插入另一端删除的线性表。因此，对队列来说，插入那一端叫做队尾，插入叫入队，删除那一端叫队头，删除叫做出队。队列中的数据元素遵循先进先出 (FIFO First In First Out) 的特性。
• 队列的入队出队顺序就简单多了，无论如何操作，一种入队顺序只对应一种出队顺序。

这个队列就跟我们平常排队一样，只能一头进一头出。

2.1 队列的基本操作

队列在队尾⼊数据，在对头出数据，主要⽀持的核⼼接⼝就是⼊队和出队。

#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int QDataType; // 队列中存储数据元素的类型 // 采用单链表实现队列，链表结点的定义 typedef struct LinkNode { QDataType data; struct LinkNode* next; }QNode; typedef struct { QNode* front; //队头指针 QNode* rear; //队尾指针 int size; //队内元素个数 }LinkQueue; // 初始化队列 void QueueInit(LinkQueue* q); // 销毁队列 void QueueDestroy(LinkQueue* q); // 检测队列是否为空，空返回真，否则返回假 bool QueueEmpty(LinkQueue* q); // 获取队列中有效元素个数 int QueueSize(LinkQueue* q); // 获取队头元素 QDataType QueueFront(LinkQueue* q); // 将x入队列 void EnQueue(LinkQueue* q, QDataType x); // 出队并返回队头数据 QDataType DeQueue(LinkQueue* q);

你们可以自己尝试一下完成这些接口的实现。

既可以采用顺序存储又可以采用链式存储，后续的代码我采用的是链式存储的方式

2.2 入队

入队就是在表尾插⼊⼀个结点，队列设计中我们增加了尾指针，所以要实现尾插是很容易的。
我们是带头结点的结构，队列空和⾮空的情况⼀样的代码就尾插处理了。

// 将x入队列 void EnQueue(LinkQueue* q, QDataType x) { assert(q); QNode* newNode = (QNode*)malloc(sizeof(QNode)); if (newNode == NULL) { perror("EnQueue()::malloc()"); return; } newNode->data = x; newNode->next = NULL; q->rear->next = newNode; q->rear = newNode; q->size++; }

2.3 出队

我们是带头结点的结构，出队就是删除头结点后的第⼀个结点，需要区分多个结点和最后⼀个结点 的情况，最后⼀个结点删除后，rear需要指向哨兵位的头结点了。

// 出队并返回队头数据 QDataType DeQueue(LinkQueue* q) { assert(q); assert(!QueueEmpty(q)); QNode* delNode = q->front->next; QDataType val = delNode->data; q->front->next = delNode->next; //如果除头结点之外只有一个结点 if (q->rear == delNode) { q->rear = q->front; } free(delNode); delNode = NULL; q->size--; return val; }

2.4 接口实现

#define _CRT_SECURE_NO_WARNINGS #include"LinkQueue.h" // 初始化队列 void QueueInit(LinkQueue* q) { assert(q); q->front = q->rear = (QNode*)malloc(sizeof(QNode)); //申请哨兵位，不存数据，这时候头指针和尾指针都是同一块区域 if (q->front == NULL) { perror("QueueInit()::malloc()"); return; } q->front->next = NULL; q->size = 0; } // 将x入队列 void EnQueue(LinkQueue* q, QDataType x) { assert(q); QNode* newNode = (QNode*)malloc(sizeof(QNode)); if (newNode == NULL) { perror("EnQueue()::malloc()"); return; } newNode->data = x; newNode->next = NULL; q->rear->next = newNode; q->rear = newNode; q->size++; } // 出队并返回队头数据 QDataType DeQueue(LinkQueue* q) { assert(q); assert(!QueueEmpty(q)); QNode* delNode = q->front->next; QDataType val = delNode->data; q->front->next = delNode->next; //如果除头结点之外只有一个结点 if (q->rear == delNode) { q->rear = q->front; } free(delNode); delNode = NULL; q->size--; return val; } // 获取队头元素 QDataType QueueFront(LinkQueue* q) { assert(q); assert(!QueueEmpty(q)); return q->front->next->data; } // 检测队列是否为空，空返回真，否则返回假 bool QueueEmpty(LinkQueue* q) { assert(q); return q->size == 0; } // 获取队列中有效元素个数 int QueueSize(LinkQueue* q) { assert(q); return q->size; } // 销毁队列 void QueueDestroy(LinkQueue* q) { assert(q); QNode* cur = q->front; while (cur) { QNode* next = cur->next; free(cur); cur = next; } q->rear = q->front = NULL; q->size = 0; }

2.4 队列的存储方式

2.4.1 链式队列的存储

• 队列的链式存储，我们可以选用单链表结构，也可以选用双向链表结构。他们入队对应着在表尾插入，出队对应着在表头删除。当然我们完全没必要选择双向链表，因为单链表就可以高效实现，还省空间一些。双向链表没有优势，每个结点还要多存储一个前驱指针，使用它纯粹浪费了。
• 其次这里我们选择单链表实现，入队就是尾插，出队就是头删。可以带头结点，也可以不带头结点，带头结点的结构略简单一点

2.4.2 顺序队列的存储

我们顺序存储的方式，在尾插时，可以做到O(1)，但是我们在头插时需要挪动数据，时间复杂度为O(n)，如果实现顺序存储的效率太低了话，我们就完全没有实现的必要了，所以我们这里可以调整思路，我们头删时，不挪动数据，而是直接挪动指针或者对头的下标。

2.4.3 顺序队列的问题

如果我们使用上面的那种方式来实现顺序队列，这里有一个顺序队列的经典问题“假溢出问题”，队列的存储空间（数组）中明明还有空闲位置，但由于 队尾指针rear已经移动到了数组的末尾，导致⽆法再插⼊新元素，系统错误地判断为“队列已满” 的现象，这种情况之所以被称为“假”溢出，是因为它并⾮真正的空间耗尽，⽽是⼀种由于数据结 构设计缺陷导致的空间浪费。

解决假溢出问题的经典方法是使用循环队列。

• 入队后，rear 指针的更新方式为：rear = (rear + 1) % 数组容量
• 出队后，front 指针的更新方式为：front = (front + 1) % 数组容量

顺序队列的第二个问题是他更适合于静态顺序结构，不太适合动态顺序结构，因为满了扩容时相对复杂而且效率低下。既然这么麻烦，不确定有多少数据时，直接使用链式队列岂不是更好！所以封装实现队列一般都用链式结构，顺序存储适宜于确定最多使用多少空间的局限场景。

指针移动导致，前面的下标有空格，系统会认为队列已满，我们如果使用循环队列的话就没有这种情况了。

这就是循环队列的逻辑图了，但是在空间上并不是这样存储的，但是这种情况我们该怎么判断队列是否满了呢？

一种方式是我们可以牺牲一个空间，当rear==front时就说明已满。

另一种方式就是我们创建一个计数变量，或者使用标记的方式。

2.5 双端队列

这个双端队列我们只需要对其有所了解即可。

• 双端队列也是一种特殊线性结构，其允许两端都可以进行数据元素入队和出队操作。将队列的两端分别称为前端和后端，两端都可以进行数据入队和出队。
• 双端队列入队时，前端进的元素排列在队列中后端进的元素的前面，后端进的元素排列在队列中前端进的元素的后面。在双端队列出队列时，无论是前端还是后端出队列，先出的元素排列在后出的元素的前面。

3. GitHub

完整代码已经上传GitHub，欢迎Star

https://github.com/PeterYuanCoder/ds-c-programs.git

后续我会出一期关于GitHub的使用指南，尽情期待！