C算法
数据结构基础：栈与队列的顺序及链式实现
栈和队列是特殊的线性表，栈遵循后进先出原则，队列遵循先进先出原则。本文详细讲解了顺序栈、共享栈、链栈的定义与操作，包括初始化、进栈、出栈及获取栈顶元素。同时涵盖了顺序队列的循环处理方案（如增加 size 或 tag 变量）以及链式队列的带头结点与不带头结点实现。通过对比顺序存储与链式存储的优缺点，帮助读者掌握数据结构的核心逻辑与代码实现细节。
栈和队列是特殊的线性表，栈遵循后进先出原则，队列遵循先进先出原则。本文详细讲解了顺序栈、共享栈、链栈的定义与操作，包括初始化、进栈、出栈及获取栈顶元素。同时涵盖了顺序队列的循环处理方案（如增加 size 或 tag 变量）以及链式队列的带头结点与不带头结点实现。通过对比顺序存储与链式存储的优缺点，帮助读者掌握数据结构的核心逻辑与代码实现细节。
我们在前两篇文章中讲到顺序表和链表其都是线性结构，我们今天讲的栈和队列也是特殊的线性表。顺序表和链表没有所谓的进出限制，但是我们今天要讲的栈就不一样，它有特殊的进栈和出栈顺序，只允许在一端进行插入和删除。也就是说后进先出，先进后出。但是队列呢，只允许从前面插入，后面出。也就是他俩是特殊的线性结构，所以在基本操作上和前文的线性表和链表有一定相似之处。
只允许在一端进行插入和删除操作的线性表。
空栈，没有元素。
栈顶允许插入和删除，栈底不允许。
就是用顺序方式存储的栈就是顺序栈。
这里用 top 指针来标记栈顶位置，初始化时 top = -1，表示栈是空的。就像刚买的空盘子架，还没放任何盘子。
#define MAXSIZE 100 // 栈的最大容量
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct {
int data[100]; // 栈的数组
int top; // 栈顶指针
} SqStack; // 顺序栈的类型定义
// 初始化操作
void InitStack(SqStack *S) {
S->top = -1; // 将栈顶指针设为 -1
}
// 判断栈是否为空
bool StackEmpty(SqStack *S) {
if (S->top == -1) {
return true; // 栈为空
} else {
return false; // 栈不为空
}
}
进栈就像往盘子架上放新盘子，只能放在最上面：
// 进栈操作
bool Push(SqStack *S, int x) {
if (S->top == MAXSIZE) {
return false; // 栈满
}
S->top++; // 栈顶指针加 1
S->data[S->top] = x; // 将 x 入栈
return true; // 入栈成功
}
先检查栈是不是满了（top 等于最大容量），没满的话就把 top 往上挪一位，再把数据放进去。
出栈则是从最上面拿走一个盘子：
// 出栈操作
bool Pop(SqStack *S, int *x) {
if (S->top == -1) {
return false; // 栈为空
}
*x = S->data[S->top]; // 将栈顶元素出栈
S->top--; // 栈顶指针减 1
return true; // 出栈成功
}
先检查栈是不是空的，不空的话就把栈顶元素取出来，再把 top 往下挪一位。
有时候我们只想看看最上面的盘子是啥样，不想拿走它：
// 获取栈顶元素
bool GetTop(SqStack *S, int *x) {
if (S->top == -1) {
return false; // 栈为空
}
*x = S->data[S->top]; // 将栈顶元素赋值给 x
return true; // 获取成功
}
这个操作和出栈的区别是，top 指针不会移动，只是'偷看'一眼。
共享栈是个节省空间的小能手，它让两个栈共享同一块数组空间，栈底分别在数组的两端，向中间生长。
// 共享栈建立
typedef struct {
int data[100]; // 栈的数组
int top; // 栈顶指针
int top1; // 栈底指针
} SharedStack; // 共享栈的类型定义
初始化时，第一个栈的 top 在 -1，第二个栈的 top1 在最大容量处：
// 初始化
void InitSharedStack(SharedStack *S) {
S->top = -1; // 将栈顶指针设为 -1
S->top1 = MAXSIZE; // 将栈顶指针设为最大容量
}
这样两个栈就可以向中间扩展，直到 top + 1 == top1 时，表示栈满。
链栈就是用链表实现的栈，链表的头结点作为栈顶，这样进栈和出栈操作都能在 O(1) 时间内完成，比顺序栈更灵活（不用提前规定大小）。
// 链栈建立
typedef struct LinkNode {
int data;
struct LinkNode *next;
} LinkNode;
typedef LinkNode* LinkStack; // 链栈的类型定义
这里栈顶指针就是链表的头指针，进栈就是在头结点前插入新节点，出栈就是删除头结点。
队列和栈正好相反，它是'先进先出'（FIFO，First In First Out）的，就像排队买奶茶——先到的人先拿到奶茶。只能在队尾插入（入队），在队头删除（出队）。
顺序队列用数组实现，但有个小问题：如果单纯地让 front 指向队头，rear 指向队尾，随着入队和出队操作，front 和 rear 都会往后移动，可能导致数组前面的空间浪费。
初始化时，front 和 rear 都指向 0：
// 队列定义
typedef struct {
int data[100]; // 队列的数组
int front; // 队头指针
int rear; // 队尾指针
} SqQueue; // 顺序队列的类型定义
// 初始化队列
void InitQueue(SqQueue *Q) {
Q->front = Q->rear = 0; // 将队头指针和队尾指针设为 0
}
// 判断队列是否为空
bool QueueEmpty(SqQueue *Q) {
if (Q->front == Q->rear) {
return true; // 队列为空
} else {
return false; // 队列不为空
}
}
// 入队操作
bool EnQueue(SqQueue *Q, int x) {
if (Q->rear == MAXSIZE) {
return false; // 队列满
}
Q->data[Q->rear] = x; // 将 x 入队
Q->rear++; // 队尾指针加 1
return true; // 入队成功
}
把数据放在 rear 指向的位置，再把 rear 往后挪一位。
// 出队操作
bool DeQueue(SqQueue *Q, int *x) {
if (Q->front == Q->rear) {
return false; // 队列为空
}
*x = Q->data[Q->front]; // 将队头元素赋值给 x
Q->front++; // 队头指针加 1
return true; // 出队成功
}
取出 front 指向的元素，再把 front 往后挪一位。
上面的方法有个缺陷：rear 到达数组末尾时，即使前面有空位，也会被判为队满。解决这个问题有几种方法：
// 获取队头元素
bool GetHead(SqQueue Q, int *x) {
if (Q.rear == Q.front) // 队列为空
return false;
*x = Q.data[Q.front]; // 将队头元素赋值给 x
return true;
}
增加一个 size 变量记录队列长度，队满条件是 size == MaxSize，队空条件是 size == 0。
#define MaxSize 10
typedef struct {
int data[10];
int front, rear;
int size; // 队列当前长度
} SqQueue;
// 插入成功：size++ 删除成功 size--
// 初始化时：rear=front=0, size=0
// 队满条件：size==MaxSize
// 队空条件：size==0
增加一个 tag 变量，记录最近操作是插入（1）还是删除（0）。队满条件是 front == rear && tag == 1，队空条件是 front == rear && tag == 0。
#define MaxSize 10
typedef struct {
int data[10];
int front, rear;
int tag; // 最近进行的是删除/插入
// 初始化时，rear=front=0; tag=0
} SqQueue;
// 每次删除操作成功时，都令 tag=0
// 每次插入操作成功时，都令 tag=1
// 只有删除操作，才可能导致队空，只有插入操作，才可能导致队满
// 队满条件：front == rear && tag == 1
// 队空条件：front == rear && tag == 0
链式队列用链表实现，队头指针指向头结点，队尾指针指向最后一个节点，这样入队和出队操作都很方便。
// 链队列的节点类型定义
typedef struct LinkNode {
int data; // 数据域
struct LinkNode *next; // 指向下一个节点的指针
} LinkNode;
// 链队列的类型定义
typedef struct {
LinkNode *front, *rear; // 队头指针和队尾指针
} LinkQueue;
头结点不存数据，只是为了操作方便。
// 初始化链队列
void InitQueue(LinkQueue *Q) {
// 初始时队头指针和队尾指针都指向头结点
Q->front = Q->rear = (LinkNode *)malloc(sizeof(LinkNode));
Q->front->next = NULL; // 头结点的 next 指针设为 NULL
}
// 判断队列是否为空
bool QueueEmpty(LinkQueue *Q) {
if (Q->front == Q->rear) {
return true; // 队列为空
} else {
return false; // 队列不为空
}
}
// 判断队列是否为空
bool QueueEmpty(LinkQueue *Q) {
if (Q->front == Q->rear) {
return true; // 队列为空
} else {
return false; // 队列不为空
}
}
入队就是在队尾添加新节点，然后把 rear 移到新节点。
// 入队操作（带头结点）
bool EnQueue(LinkQueue *Q, int x) {
// 创建一个新节点
LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
if (s == NULL) {
return false; // 内存分配失败
}
s->data = x; // 将 x 赋值给新节点的数据域
s->next = NULL; // 将新节点的 next 指针设为 NULL
Q->rear->next = s; // 将原队尾节点的 next 指针指向新节点
Q->rear = s; // 将队尾指针指向新节点
return true; // 入队成功
}
// 入队操作（不带头结点）
bool EnQueue(LinkQueue *Q, int x) {
// 创建一个新节点
LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
if (s == NULL) {
return false; // 内存分配失败
}
s->data = x; // 将 x 赋值给新节点的数据域
s->next = NULL; // 将新节点的 next 指针设为 NULL
// 若队列为空（首次入队），队头和队尾都指向新节点
if (QueueEmpty(Q)) {
Q->front = s;
Q->rear = s;
} else {
// 队列非空时，队尾节点的 next 指向新节点，再移动队尾指针
Q->rear->next = s;
Q->rear = s;
}
return true; // 入队成功
}
不带头结点的链式队列入队操作，核心区别在于需要处理'首次入队'的特殊情况：
front 和 rear 都为 NULL），新节点既是队头也是队尾，所以 front 和 rear 要同时指向这个新节点next 指向新节点，再把 rear 移到新节点上// 出队操作（带头结点）
bool DeQueue(LinkQueue *Q, int *x) {
// 队列为空时无法出队
if (QueueEmpty(Q)) {
return false;
}
LinkNode *p = Q->front->next; // p 指向队头元素节点
*x = p->data; // 保存出队元素的值
Q->front->next = p->next; // 头结点跳过队头元素，指向其后继
// 若出队的是最后一个元素，队尾指针需指向头结点（保持空队列状态）
if (Q->rear == p) {
Q->rear = Q->front;
}
free(p); // 释放出队节点的内存
return true;
}
front->next 指向的节点（头结点不存储数据）next 指针，最后一个元素出队时需将 rear 重置为头结点// 出队操作（不带头结点）
bool DeQueue(LinkQueue *Q, int *x) {
// 队列为空时无法出队
if (QueueEmpty(Q)) {
return false;
}
LinkNode *p = Q->front; // p 指向队头元素节点（不带头结点时 front 直接指向队头）
*x = p->data; // 保存出队元素的值
// 若队列只有一个元素，出队后队头队尾均置空
if (Q->front == Q->rear) {
Q->front = Q->rear = NULL;
} else {
// 队列有多个元素时，队头指针后移
Q->front = Q->front->next;
}
free(p); // 释放出队节点的内存
return true;
}
front 直接指向队头元素（首个数据节点）front 指针，最后一个元素出队后需将 front 和 rear 均置为 NULL顺序存储，预分配的空间耗尽时队满。
链式存储，一般不会队满，除非内存不足。
栈和队列都是特殊的线性表，只是对操作的位置做了限制：
它们的实现可以用数组（顺序存储）或链表（链式存储），各有优缺点：
就像两种不同的数据处理风格：栈是'后来者居上'，队列是'按规矩办事'，各有各的适用场景。掌握它们的逻辑和实现，对于理解更复杂的数据结构至关重要。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online