[TOC]
# 栈（Stack）
## 栈的基本运算
+ InitStack(S)
构造一个空栈S
+ StackEmpty(S)
判断栈空，若 S 为空栈，则返回 true，否则返回 false
+ StackFull(S)
判断栈满。若 S 栈满，返回 true，否则返回false。该运算只适用于栈的顺序存储结构
+ Push(S, x)
进栈。若 S 不满，将元素 x 插入 S 的栈顶
+ Pop(S)
出栈。若 S 非空，则将 S 的栈顶元素删去，并返回该元素。
+ StackTop(S)
取栈顶元素。若栈 S 非空，则返回栈顶元素，但不能改变栈的状态。
## 顺序栈
概念：栈的顺序存储结构称为**顺序栈**
**顺序表的类型定义**
```c
#define StackSize 100
typedef char DataType;
typedef struct{
DataType data[StackSize];
int top;
}SepStack;
```
解释说明：
+ 设 S 为 SepStack 的指针变量；
+ `S->data[0]`表示栈底元素；
+ `S->top`争相增长，即进栈`S->top + 1`，出栈时`S->top - 1`；
+ `S->top < 0 `表示**空栈**；
+ `S->top=StackSize-1`表示 **栈满**；
+ **上溢**：栈满时做进栈运算产生的空间溢出（出错状态）；
+ **下溢**：栈空时做退栈产生的空间溢出（可能是正常现象，通常用来做程序控制转移）。
**置空栈**
```c
/**
将顺序栈置空
*/
void InitStack(SepStack *S) {
S->top = -1;
}
```
**判断栈空**
```c
int StackEmpty(SepStack *S){
return S->top == -1;
}
```
**栈满**
```c
int StackFull(SepStack *S){
return S->top == StackSize - 1;
}
```
**进栈**
```c
void Push(SepStack *S, DataType x){
if (StackFull(S)) {
// error, 上溢，强行退出
}
// 压入栈顶
S->data[++S->top] = x;
}
```
**退栈**
```c
DataType Push(SepStack *S){
if (StackFull(S)) {
// error, 下溢，强行退出
}
// 返回栈顶元素，并 -1
return S->data[S->top -- ];
}
```
**获取栈顶元素**
```c
DataType StackTop(SepStack *S) {
if (StackEmpty(S)) {
// error, 空栈
}
// 返回栈顶元素
return S->data[S->top];
}
```
## 链栈
概念：栈的链式存储结构称为**链栈**
链栈行包含：data、next（下一个栈的地址）
**链栈的类型说明**
```c
typedef struct stacknode {
DataType data;
struct stacknode *next;
}StackNode;
typedef struct {
StackNode * top; // 栈顶指针
}LinkStack;
```
**链栈的操作**
```c
void InitStack(LinkStack *S){
S->top = NULL;
}
int StackEmpty(LinkStack *S) {
return S->top == NULL;
}
void Push(LinkStack *S, DataType x) {
StackNode *p = (StackNode *)malloc(sizeof(StackNode)); // 新的栈元素
p->data = x;
p->next = S->top; // 新结点*p插入链栈头部
S->top = p;
}
DataType Pop(LinkStack *S){
DataType x; // 为了保存栈顶元素的栈
StackNode *p = S->top; // 保存栈顶指针
if(StackEmpty(S)) {
// Error，下溢
}
x = p->data; //给x赋值栈顶元素的值
S->top = p->next; // 将栈顶元素从链上摘下
free(p); // 释放原栈顶空间
return x;
}
DataType StackTop(LinkNode *S) {
if(StackEmpty(S)) {
// Error，
}
//返回栈顶元素的值
return S->top->data;
}
```
# 队列（Queue）
队列只允许一端插入（队尾<Rear>），另一端进行删除（队头<Front>）
**先进先出**
## 队列的基本运算
+ InitQueue(Q)
置空队。构造一个队列Q。
+ QueueEmpty(Q)
判队空。若为空返回true，否则返回false。
+ QueueFull(Q)
判队满。若队满返回true，否则返回false。该运算只适用于队列的顺序存储结构
+ EnQueue(Q, x)
若队列非空，则将元素 x 插入Q的队尾。操作为入队。
+ DeQueue(Q)
若队列非空，则删除对头元素，并返回该元素。操作为出队。
+ QueueFront(Q)
队列Q非空，则返回队头元素，但不改变队列Q的状态。
## 顺序队列
概念：队列的顺序存储结构
入队：将新元素插入 rear 所指向的位置，然后将 rear + 1
出队：删除 frond 指向的元素，然后将 front + 1，并返回被删除的元素。
+ 判空：头尾指针相等
+ 非空队列中，头指针指向队头元素，尾指针指向队尾元素
## 循环队列（Circular Queue）
循环队列：可以想象成首尾相连的圆环。
循环队列中出栈和入栈，头尾指针都要 +1，朝前移动。不过当头尾指针指向向量上界（QueueSize - 1）时，其 +1 操作的结果指向向量的下界0。
```c
if (i+1 == QueueSize) {
i = 0;
}else {
i++;
}
```
利用`模运算`可简化为：
```c
i = (i+1) % QueueSize;
```
**循环队列判空和满**
+ 设一布尔变量来判断队列是空还是满；
+ 少用一元素空间，约定入队前测试尾指针在循环意义下+1是否等于头指针
+ 使用计数器记录队列中元素的总数
使用第三种方法实现队列的6种基本运算：
```c
#define QueueSize 100
typedef char DataType;
typedef struct {
int front; // 头指针， 队非空时指向队头元素
int rear; // 尾指针，队非空时指向队尾元素的下一个位置
int count; // 计数器，记录队中的元素总数
DataType data[QueueSize];
}CirQueue;
// 置空队
void InitQueue(CirQueue *Q){
Q->front = Q->rear = 0;
Q->count = 0; // 计数器置为0
}
// 判队空
int QueueEmpty(CirQueue *Q){
return Q->count = 0; //队列无元素为空
}
// 判队满
int QueueFull(CirQueue *Q){
return Q->count == QueueSize; // 队中的元素个数等于QueueSize
}
// 入队
void EnQueue(CirQueue *Q, DataType x){
if (QueueFull(Q)) {
// error,队满上溢
}
Q->count ++; // 队列元素个数 +1
Q->data[Q->rear] = x; // 新元素插入队尾
Q->rear = (Q->rear+1) % QueueSize; // 循环意义下将尾指针+1
}
// 出队
DataType DeQueue(CirQueue *Q){
DataType tmp;
if (QueueEmpty(Q)) {
// error 对空下溢
}
tmp = Q->data[Q->front];
Q->count --;
Q->front = (Q->front + 1 ) % QueueSize;
return tmp;
}
// 取队头元素
DataType QueueFront(CirQueue *Q) {
if (QueueEmpty(Q)) {
// error 对空下溢
}
return Q->data[Q->front];
}
```
## 链队列
概念：队列的链式存储结构
链队列的类型LinkQueue定义为一个结构类型：
```c
// 队列中的结点类型
typedef struct queuenode{
DataType data;
struct queuenode *next;
}QueueNode;
typedef struct {
QueueNode *front; // 队列头指针
QueueNode *rear; // 队列尾指针
}LinkQueue;
```
### 基本运算
```c
// 置空
void InitQueue(LinkQueue *Q){
Q->front = Q->rear = NULL;
}
// 判空
int QueueEmpty(LinkQueue *Q){
// 实际上只需要判断头指针是否为空即可
return Q->front == NULL && Q->rear == NULL;
}
// 入队
void EnQueue(LinkQueue *Q, DataType x){
// 申请新的结点
QueueNode *p = (QueueNode *)malloc(sizeof(QueueNode));
p->data = x;
p->next = NULL;
if (QueueEmpty(!Q )) {
// 将 x 插入空队列
Q->front = Q->rear = p;
// *p链接到原队尾
Q->rear->next = p;
// 队尾指针指向新的队尾
Q->rear = p;
}
}
// 出队
DataType DeQueue(LinkQueue *Q){
DataType x;
QueueNode *p;
if (QueueEmpty(Q)) {
// 下溢
}
p = Q->front; // 指向队列头结点
x = p->data; // 保存队列都结点的数据
Q->front = p->next; //将队头 结点从链上摘下
// 原队只有一个结点。删去后队列变空，此时队头指针为空
if (Q->rear == p) {
Q->rear = NULL;
}
// 释放被删除的队头结点
free(p);
// 返回原对头数据
return x;
}
// 取队头元素
DataType QueueFront(LinkQueue *Q){
if (QueueEmpty(Q)) {
// Error，空队列
}
return Q->front->data;
}
```
# 栈和队列的实际应用
## 1. 数制转换
将一个数抓换成制定的进制的数。如：3553转换成8进制
```
typedef int DataType;
/**
@pragam N 非负的十进制数
@pragam B 输出的B进制数
*/
void MutiBaseQueue(int B, int B){
int b;
SeqStack S;
// 置空栈
InitStack(&S);
// 从左往右产生B进制数的各位数字，并将其进栈
While (N) {
Push(&N, N%B); // 将 bi进栈, 0<= i <= j
N = N / B;
}
// 栈非空时退栈输出
while(!StackEmpty(&S)){
i = Pop(&S);
printf("%d", i);
}
}
```
## 2. 栈与递归
求非负整数n的阶乘。
递归的终止条件：0! == 1， 0的阶乘等于1
```c
int Factorial(int n){
if (n == 0) { // 递归终止条件
return 1;
} else {
return n * Factorial(n - 1); // 递归步骤
}
}
```
## 3. 舞伴问题
周末舞会上，男女各成一排，开始配对跳舞。若两队的人数不相等，较长的一队等待下一轮。
（先进先出问题）
```c
typedef struct {
char name[20];
char sex; // M-男，F-女
}Person;
typedef Person DataType; // 队列中元素的数据类型为Person
void DancePartners(Person dancer[], int num) {
int i;
CirQueue Mdancers, Fdancers;
InitQueue(&Mdancers);
InitQueue(Fdancers);
for (i = 0; i< num; i++) {
p = dancer[i];
if (p.sex == 'F') {
EnQueue(&Fdancers, p);
} else {
EnQueue(&Mdancers, p);
}
}
printf("The dancing partners are:\n\n");
while(!QueueEmpty(&Fdancers) && !QueueEmpty(&Mdancers)) {
p = DeQueue(&Fdancers);
printf("%s", p.name);
p = DeQueue(&Mdancers);
printf("%s", p.name);
}
if (!QueueEmpty(&Fdancers)) {
printf("\n There are %d woman waiting for the next round.", Fdancers.name);
p = QueueFront(&Fdances);
printf("%s will be the first to get a partner", p.name);
} else {
if (!QueueEmpty(&Mdancers)) {
printf("\n There are %d men waiting for the next round.", Mdancers.name);
p = QueueFront(&Mdances);
printf("%s will be the first to get a partner", p.name);
}
}
}
```
