栈总结
对于栈而言，最主要是要清楚它先入后出的特性。其次拿捏清楚指向栈顶元素的"指针"，因为无论是数组模拟的栈还是结构体实现的栈，核心操作都是对指针的移动
队列
队列的定义和基本运算
队列的定义
队列是只允许在一端进行插入操作，而在另外一端进行删除操作的线性表
队列是一种先进先出(First In First Out)的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。
队列的基本运算
队列的存储和实现
队列数组实现——算法竞赛必备
队列在算法竞赛中也是常客了，主流的依旧是使用的数组模拟的队列。原因和栈用数组模拟的原因一致。
队列用得最多，知名度最广的应该是在边权相等的情况下用宽度优先搜索去求最短路径，进而还有拓扑排序等等
下面依旧是从一道例题中引入数组模拟队列
样例描述：
原题传送门
参考实现代码(C++版本)
#include <iostream> using namespace std; const int N = 100010; int m; int q[N];//模拟队列的数组 hh, tt = -1;//队头和队尾 int main() { cin >> m; while (m -- ) { string op; int x; cin >> op; if (op == "push") { cin >> x; q[ ++ tt] = x; //移动尾指针实现插入 } else if (op == "pop") hh ++ ; //移动头指针位置，实现删除 else if (op == "empty") cout << (hh <= tt ? "NO" : "YES") << endl; else cout << q[hh] << endl; } return 0; }
队列的初始状态如下图
在初始化状态中，队头队尾都放在索引为0的位置也是可以的，那么在后面移动尾指针tt的时候使用后缀++即可。
//队尾从-1开始 q[ ++ tt] = x; //移动尾指针实现插入 //变通===> 队尾从0开始 q[tt ++] = x; //移动尾指针实现插入
入队
因为本质是数组，所以当有新数据插入的时候，让新数据插入到数组的尾部就可以实现入队操作。
cin >> x; q[ ++ tt] = x; //移动尾指针实现插入
出队
数组模拟的队列中，使用队头指针hh来维护队列中第一个元素的位置。当有元素要出队了，那么通过移动队头指针调整队列的区间，从而确定新的队头。
else if (op == "pop") hh ++ ; //移动头指针位置，实现删除
队列链表实现——工程开发和期末应试必备
链队列类型定义
使用结构体加上指针实现的队列在本质上仍旧是线性表中的链表，只是对它开发了新的特性，实现了先进先出(FIFO)的效果。
参考实现代码
typedef int DataType; //定义DataType为int 型 typedef struct qnode{ //链队列存储类型 DataType data; //定义链队中每个结点的数据域 struct qnode *next; //定义链队中每个结点的指针域 }LinkListQ; typedef struct { LinkListQ *front,*rear; //链队列的队头指针和队尾指针 }LinkQueue;
只是对于队列而言，为了实现维护一段队伍的效果，需要额外增加一个队头指针front和一个队尾指针rear
LinkListQ *front,*rear; //链队列的队头指针和队尾指针
初始化队列
操作流程：
①先建立一个队列的头结点Q，该头结点中有维护队列的队头指针front和队尾指针rear
② 建立一个链队的头结点p,并让其指针域为空
③ 将Q->front 和 Q->rear都指向该头结点并返回指针Q
参考实现代码：
LinkQueue *InitQueue() { LinkQueue *Q; LinkListQ *p; Q = (LinkQueue *) malloc(sizeof (LinkQueue)); //建立链队列头指针所指的结点 p = (LinkListQ *)malloc(sizeof(LinkListQ)); //建立链队列的头结点 p->next = NULL; Q->front = p; //Q指针所指的front指针指向p Q->rear = p; //Q指针所指的rear指针指向p return Q; }
入队操作
实现流程：
①将新结点插入到队尾，原本队尾的指针域Q->rear->next 指向新结点p(Q->rear->next = p;)
②将队尾Q->rear指向新结点p(Q->rear = p; )
参考实现代码：
//入队函数 void InQueue(LinkQueue *Q,DataType x) { LinkListQ *p; p = (LinkListQ *)malloc(sizeof(LinkListQ)); //生成新的结点 p->data = x; //将x存入新结点的数据域 p->next = NULL; Q->rear->next = p; //将新结点插入到链队之后 Q->rear = p; //队尾指针指向队尾元素 }
出队操作
操作①：将队头指针的指针域指向原本队头元素的下一个位置的地址（Q->front->next = p->next;）
操作②：当队列中仅含有一个元素的时候，出队后队尾指针指向队头指针所指向的位置(if(p->next == NULL) Q->rear = Q->front)
操作③：释放p指针所指的空间
参考实现代码：
//判断队列是否为空的函数 int EmptyQueue(LinkQueue *Q) { if(Q->front == Q->rear) return 1; else return 0; } //出队函数 int DeQueue(LinkQueue *Q,DataType *x) { LinkListQ *p; if(EmptyQueue(Q)) //调用判空函数，判断当前队列是不是为空 { printf("队空，无法出队任何元素\n") ; return 0; }else //队列不空 { p = Q->front->next; //p指向队头元素 *x = p->data; //取出队头元素赋值给x Q->front->next = p->next; //队头指针的指针域中存放新队头元素的地址 if(p->next == NULL) Q->rear = Q->front; //处理队列中只有一个元素的情况 free(p); return 1; } }
求队头元素
参考实现代码：
int GetFront(LinkQueue *Q,DataType *x) { if(EmptyQueue(Q)) //调用判空函数，判断当前队列是不是为空 { printf("队列为空，无法获取任何元素"); return 0; }else { *x = Q->front->next->data; //将队头元素中存放的数据给x return 1; } }
遍历链队
void ShowQueue(LinkQueue *Q) { LinkListQ *p = Q->front->next; if(p == NULL) printf("队列为空，无法显示任何元素\n"); else { printf("从队头起，队列中的每个元素是："); while(p != NULL) { printf("%d ",p->data); p = p->next; } } }
队列的应用举例
"宽度优先搜索(BFS)"方向
队列是宽搜实现的核心结构，因为笔者之前已经详解总结和演示过宽搜，那我这里就不再赘述啦，小伙伴们可以看看这篇文章喔
"优先队列"——堆
优先队列是一种特殊的队列了，优先队列的出队是按照元素的优先级出队，比如，数值最小的先出队，或者数值最大的先出队。优先队列和二叉树结合起来，就又变成了一种神器——样同样的，因为笔者之前已经写过和堆相关的内容了，现在就直接推荐小伙伴们去看一看啦数据结构——被优先队列玩起来的“树“
队列总结
数组模拟的队列实现和操作都是比较清晰和轻松的，只是有时候需要注意元素假如要进行多次的入队和出队，那么用于实现队列结构的数组开头部分的空间就会被严重浪费，这种情况可以采用"循环队列"的方式优化。笔者这里就不展开讲了，我想在后续的《算法基础》专栏中结合习题进行系统的剖析。
结构体+指针的实现方式就要对指针十分小心，清楚当前的指针是指向谁的
