目录
前言
每接触一种数据结构类型，就要从逻辑结构，物理结构，数据的运算这三个方面进行考虑，深入理解定义
一、栈的定义和特点
栈（stack）是只允许在一端进行插入或删除操作的线性表。
- 栈顶（top）：允许插入删除的一端（一般是表尾）
- 栈底（bottom）：不允许插入删除的一端（一般是表头）
- 空栈：不含任何元素的空表。
- 原则：后进先出 (Last In First Out, LIFO) 。
可以类比叠盘子。
超纲了解：卡特兰数
一个n个元素皆不相同的序列，给定入栈顺序，但出栈与入栈同时进行，出栈的排列总共有(卡特兰数Catalan)。
问题：入栈顺序a->b->c->d->f， 在入栈的同时出栈，哪些出栈顺序是合法的？
二、栈的逻辑结构以及基本操作
2.1 用抽象数据类型来定义栈的数据结构
2.2 顺序栈的定义及其特点
顺序栈是指利用顺序存储结构实现的栈。
即利用一组地址连续的存储单元依次存放自栈底到 栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。
2.3 顺序存储结构对栈基本操作的实现
与顺序表类似，顺序栈类型的表示方法有两种：静态分配和动态分配。静态分配：用静态的“数组”存放数据；动态分配：用指针指向一片连续的区域。
栈顶用从0记的话初始化top为-1；
栈顶用从1记的话初始化top为0；
| 声明顺序栈类型： 静态分配方式 |
#define Maxsize 10 //定义栈中最多元素 typedef struct { int data[Maxsize]; //存放栈中元素 int top;// 栈顶指针 }SStack; |
静态分配方式，大小固定不变； 顺序栈；栈顶指针类型与数据域类型相同。 |
| //初始化 void InitStack(SStack *S){ S.top=-1; } |
// 初始化2 void InitStack(SStack *S){ S.top = 0; } |
由于data[i] (0<=i<=Maxsize-1) 数据都是有效的所以这里初始化top为-1， |
| // 清空栈 bool ClearStack(SStack *S){ S.top=-1; return true; } |
// 清空栈 bool ClearStack(SStack *S){ S.top=0; return true; } |
如果top初始化为0，那么top指向的就是下一个可以插入的位置。也就是top[0]可入栈。 |
| //进栈 bool Push(SStack *S,int x){ if(S.top==Maxsize-1) return false;// 栈满，报错 S.data[++S.top] = x; return true; } |
bool Push(SStack *S,int x){ // 栈满，报错 if(S.top==Maxsize) return false; S.data[S.top++]=x; return true; } |
|
| // 出栈 bool Pop(SStack *S,int &x){ if(S.top==-1) return false;// 栈空，报错 x = S.data[S.top--]; return true; } |
bool Pop(SStack *S,int &x){ // 栈空报错 if(S.top==0) return false; x = S.data[--S.top]; return true; } |
|
| // 判断栈空 bool StackEmpty(SStack S){ if(S.top==-1) return true; else return false; } |
// 判断栈空 bool StackEmpty(SStack S){ if(S.top==0) return true; else return false; } |
共享栈：利用栈底位置相对不变的特性，可以让两个顺序栈共享一个数据空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶项共享空间的中间延伸。
栈满的标志是top0==top1-1;
2.4 链栈的定义及其特点
链栈：采用链式存储方式实现的栈。
链栈的优点是：便于多个栈共享存储空间和提高其效率，且不存在栈满溢出的情况。
链栈的内容与链表相似，但也都有带头结点，与不带头结点的区别，注意区别。
2.5 链式存储结构对栈基本操作的实现
暂略。
三、队列的定义和特点
队列：只允许在一端进行插入，而在另一端进行删除的线性表。
- 队尾（rear）：允许插入的一端；
- 队头（front）：允许删除的一端；
- 空队列：
- 原则（特点，先进先出）：先进先出（First In First Out，FIFO）。
四、队列的逻辑结构以及基本操作
4.1 用抽象数据类型来定义队列的数据结构
4.2 顺序队列的定义及其特点
在队列的顺出存储结构中，除了用一组地址连续的存储单元一次存放从队头到队尾的元素外，还需要附设连个整形变量front和rear分别指示队头元素和队尾元素的位置（后面分别称为头指针和尾指针）。
4.3 顺序存储结构对队列基本操作的实现
| 声明队列类型： 静态数组形式 |
#define Maxsize 10 typedef struct{ int data[Maxsize]; int front; int rear; }SQ; |
|
| 初始化队列 |
void InitQ(SQ *Q){ Q->front = 0;// 指向队头 Q->rear = 0;// 队尾指向下一个要插入的位置（下一个应该插入的位置） } |
|
| 队列是否为空 |
bool Empty(SQ Q){ if(Q.front==Q.rear) return true; else return false; } |
|
| 入队 |
bool EnQueue(SQ *Q,int x){ if((Q->rear+1)%Maxsize==Q.front) return false; Q->data[Q.rear]=x;//插入队尾 Q->rear=(Q->rear+1)%Maxsize;//队尾指针后移 return true; } 因为这里判断队列是否为满的方法是：当前队尾（下一个要插入的位置）的下一节点是否为队头，容易注意到这里Q->rear是下一个要插入的位置，然而如果我们直接用Q->rear%Maxsize==Q->front去判断是否为满，因为这个判断方式与判断队空是等价的，所以会产生冲突，所以就选择了牺牲循环队列队头的前一个元素的空间，(Q->rear+1)%Maxsize==Q.front，如果这个下一个要插入元素的下一个元素是队头，那么我们就不能入队，也就是下一个的下一个如果是队头，所以实际上最多只能存放9个有效数据。 |
由于队列的特性，可能即使队尾是Maxsize也是非空。 利用取余运算，模运算将无限的整数域映射到有限的整数集合上{0,1,2,...,b-1}上。 {0,1,2,..,Maxsize-1}将存储空间在逻辑上变成了“环状”。 如果Q->rear==9那么（Q->rear+1）%Maxsize==0 即使（Q->rear+1）%Maxsize==0,也不能说明是队满，因为队列的环状结构，让队头的位置可能已经不再是0下标的位置 所以下一个要插入的位置如果是队头Q.front，那么这就满了。 所以队列不像栈一样，将值设为-1,而是将Q.front直接指向第一个结点。再看左边是关键:为什么会浪费一个结点？ |
| 出队 |
bool DeQueue(SQ *Q,int *x){ // 队空 if(Q->rear==Q->front) return false; x=Q->data[Q->front];// 出队 Q->front = (Q.front+1)%Maxsize;// 队头向后移动 return true; } |
如果 Q->front = (Q.front+1)%Maxsize; 造成队头和队尾重合，那么这个队列就是空的。 |
| 访问队头元素 |
bool GetHead(SQ Q,int *x){ if(Q.rear==Q.front) return false; x = Q.data[Q.front]; return true; } |
|
| 判断为满1 |
bool Full1(SQ Q){ if((Q.rear+1)%Maxsize==Q.front) return true; else return false } |
这种判断方法会导致一个结点的内存浪费 |
| 判断为满2 |
typedef struct{ int data[Maxsize]; int front,rear; int size; }SQ2; bool Full2(SQ2 Q){ if(size==Maxsize) return true; else return false; } |
增加一个变量size来保存队列长度。用来判断队空和队满。 初始化size=0； 入队size++ 出队size-- 队满size==Maxsize 对空size==0 |
| 判断为满3 |
typedef struct { int data[Maxsize]; int front,rear; int tag; }SQ3; bool Full3(SQ3 Q){ if(Q.rear==Q.front&&tag==1) return true; else return false; } |
增加一个标志tag，初始化tag=0; 每次删除成功时，令tag=0； 每次插入成功是，令tag=1； 注意： 只有删除操作能让队空； 只有插入操作能让队满； 所以现在即使我们下一个要插入的结点是队头，我们只要知道上一次操作是插入，那么队列肯定是满的，即： 队满：Q.rear==Q.front&&tag==1 队空：Q.rear==Q.front&&tag==0 |
上面的操作实现过程是基于初始化时，让队尾指针指向的是下一个要插入的位置；当然还有其他情况，比如让队尾指向当前队列的最后一个元素，那么操作的方法又会有所不同。
| 初始化： 让队尾指向当前队列的最后一个元素 |
void InitQ2(SQ *Q){ Q->rear = Maxsize-1; Q->front=0; } |
为了方便我们可以让Q->rear 初始化为n-1的位置，那么插入的时候自然就到n%n，也就是0 的位置 |
| 入队： 牺牲一个存储单元 |
bool EnQueue2(SQ *Q,int x){ // 队满 if((Q->rear+2)%Maxsize==Q->front) return false; // Q->rear指向的是队列最后一个元素 Q->rear = (Q->rear+1)%Maxsize; Q->data[Q->rear]=x; return true; } |
判断队空： (Q->rear+2)%Maxsize==Q->front 判断队满：
|
4.4 链式队列的定义及其特点
链队是指采用链式存储结构实现的队列。
通常链队用单链表来表示。
一个链队显然需要两个指示队头和队尾的指针（分别称为头指针和尾指针）才能唯一确定。
这里和线性表的单链表一样，为了操作方便起见，给链表添加一个头结点，并令指针始终指向头结点。
4.5 链式存储结构对队列基本操作的实现
| 队列的链式存储结构 |
typedef struct LQNode{// 链式队列结点 int data; struct QNode *next; }QNode; typedef struct{ //队头和队尾（头指针和尾指针） QNode *front,*rear; }LinkedQueue; |
|
| 初始化 带头结点 不带头结点 |
// 初始化（带头结点） void InitLQ(LinkedQueue *L){ // 生成新节点作为头结点 L->front=(QNode *)malloc(sizeof(QNode)); // 队头和队尾都指向此节点 L->rear=L->front; // 头结点域置空 L->front->next = NULL; } // 链队为空 // 为空的条件：Q.front==Q.rear或Q.front->next==NULL bool Empty(LinkedQueue L){ if(Q.front==Q.rear) return true; else return false; } |
//初始化（不带头结点） void InitLQ_noh(LinkedQueue *L){ L->front=NULL; L->rear=NULL; } //判断队列是否为空(不带头结点) //判断为空的条件L.front==L.rear或L.front==NULL bool Empty_noh(LinkedQueue L){ if(L.front==NULL) return true; else return false; } |
| 入队： 带头结点，只需要修改队尾； 不带头结点，如果是第一个插入，需要修改队头队尾。 |
//入队（带头结点） bool EnQueue(LinkedQueue *L,int x){ LQNode *s=(LQNode *)malloc(sizeof(LQNode));//新节点 s->data=x; s->next=NULL; // 新节点插入尾结点后面 L->rear->next=s; // 将新节点作为尾结点 L->rear=s; return true; } |
带头结点，只要将新节点插入队尾，并将新节点作为队尾。 |
| 入队 |
bool EnQueue_noh(LinkedQueue *L,int x){ LQNode *s=(LQNode *)malloc(sizeof(LQNode)); s->data=x; s->next=NULL; // 队列为空，那么队头，队尾为NULL if(L->front==NULL){ L->front=s; L->rear=s; } else{ L->rear->next=s; L->rear=s; } return true; } |
不带头结点，如果是空队列，那么就不能使用L->rear->next，因为这就相当于NULL->next。 只要将新节点作为队头，队尾即可。 |
| 出队： 带头结点 |
bool DeQueue(LinkedQueue *L,int *x){ if(L->front==NULL) return false;//空队 //要出队的结点 LQNode *p=L->front->next;// x=p->data; L->front->next=p->next; // 队头是队尾的特别情形 if(p==L->rear) L->rear=L->front; free(p); return true; } |
出队的是头结点的后一个结点； 特别的是出队的结点是尾结点。 |
| 队满 |
链式队列除非空间不够否则一般不会出现队满的情形 |
4.6 双端队列的用法
双端队列：允许在两端进行插入删除操作的线性表。
相当于是整合了队列和链表的特性。
题型：若数据元素输入序列为(1,2,3,4),输入的同时进行输出，则哪些输出序列是在栈中合法的，哪些是在栈中非法的？双端队列呢？
步骤：首先从第一个输出去判断已经输入的结点，以及输出此结点后重复这一步骤，知道判断不合法或者合法。
判断在双端队列中是否合法，我们知道，在栈中合法的输出序列合法，那么双端队列肯定是合法的，所以我们只需要在栈中不合法的序列中找在双端队列中不合法的序列。比如(3,1,4,2)在栈中不合法，
第一个输出是3也就意味着：已经输入（1,2,3），由于是双端队列，所以输出队尾输出3，队头再输出1；然后输出的是4，所以，已经输入（1,2,3,4），目前队列还剩（2,4），输出4，再输出2；所以是合法的。
还有（4,2,1,3）在栈中不合法，
第一个输出是4，那么已经输入（1,2,3,4），那么还剩（1,2,3）然后只能输出1或3，所以输出2明显错误。
注意，这里的队列是双端队列，但却是输入受限的双端队列，因为给出的输入序列，都是从一个端口输入的。
五、栈的经典应用
5.1 栈的经典应用1：括号匹配问题
情形1 出现的括号是相同类型的层层叠加，没有同级关系，比如：
| ( |
( |
( |
( |
) |
) |
) |
) |
容易发现：最后出现的左括号最先被匹配（LIFO）。
于是发现可以用“栈”，实现该特性。
情形2出现的括号是相同类型的，但有同级关系，比如：
| ( |
( |
( |
) |
) |
( |
) |
) |
容易发现：每出现一个右括号，就“消耗”（出栈）一个最后发现的左括号。
于是发现还是可以用“栈”，实现该特性。
情形3：出现的括号是不同类型的，比如：
|
void test(){ int a[10][10]; int x= 10*(20*(1+3)-(3-2)); printf("加油奥利给"; } |
给出一段文本，要求匹配括号，括号的种类有：{},[],()，比如说：上面的文本。
我们要对这里的括号进行匹配：我们根据括号出现的顺序进行排列：
| { |
[ |
] |
[ |
] |
( |
( |
) |
( |
） |
） |
( |
} |
规则如下：
- 遇到左括号就入栈；
- 遇到右括号就将最后一个入栈括号出栈，要求这个出栈的括号类型与右括号必须相同；
错误情形：
- 遇到右括号，栈中最后一个括号与之类型不同；
- 当扫描遇到一个右括号，栈空时；
- 当文本扫描结束，栈非空；
| #include <stdio.h> // void test(){ // int a[10][10]; // int x= 10*(20*(1+3)-(3-2)); // printf("加油奥利给"; // } #define Maxsize 10//定义栈中最大元素· typedef struct{ int data[Maxsize]; int top; }SqStack; //初始化栈 void InitSqStack(SqStack *S); // 入栈 bool Push(SqStack *S,int x); // 出栈 bool Pop(SqStack *S, int *x); // 是否为空 bool IsEmpty(SqStack S); // 传入一个包含文本内容的数组，和数组长度。 bool BracketCheck(char str[],int length){ SqStack S; InitSqStack(&S);初始化一个栈 for(int i=0;i<length;i++){ if(str[i]=='('||str[i]=='{'||str=='[') Push(&S,str[i]); else{ if(IsEmpty(S))//扫描到右括号，且当前栈空 return false;//匹配失败 char topElem; Pop(&S,&topElem);//栈顶元素出栈 if(str[i]==')'&&topElem!='(') return false; if(str[i]==']'&&topElem!='[') return false; if(str[i]=='}'&&topElem!='}') return false; } } return IsEmpty(S);// 检查全部括号后，栈空说明匹配成功。 } |
5.2 栈的经典应用：表达式求值问题
常见的中缀表达式：((15÷(7-(1+1)))×3-(2+(1+1))
由三个部分组成：操作数、运算符、界限符
一个波兰数学家发现可以一种不用界限符也能表达运算顺序的方式。
Reverse Polish notation(逆波兰表达式=后缀表达式）
Polish notation(波兰表达式=前缀表达式）
| 中缀表达式 |
后缀表达式 |
前缀表达式 |
| a+b |
ab+ |
+ab |
| a+b-c理解为((a+b)-c)或(a+(b-c)) |
ab+c-或abc-+ |
-+abc或+a-bc |
| a+b-c*d |
=>a+b-cd* =>ab+cd*-或abcd*-+ |
=>+ab-*cd =>-+ab*cd |
5.2.1 中缀表达式转后缀表达式（类似手算过程）
- 确定中缀表达式中各个运算符的运算顺序；
- 选择下一个运算符，按照[左操作数 右操作数 运算符]的方式组合成一个新的操作数；
- 如果还有运算符没被处理，就继续2)。
如下面的转换例子：
注意：运算顺序不唯一，因此对应的后缀表达式也不唯一,比如
但是，算法当中有一条性质：确定性。输出的结果只能是一个。
“左优先”原则：只要左边的运算符能先计算，就优先算左边的，保证手算和机算结果相同。
“左优先”并不等价于“优先级运算”比如：
特点：
- 操作数的顺序不变；
- 越往后出现的操作数越先被计算
5.2.2 中缀表达式转后缀表达式（机算）
输入一个中缀表达式，初始化一个运算符栈，保存暂时还不能确定运算顺序的运算符。
从左往右处理中缀表达式的各个元素，直到末尾。可能遇到三种情况。
- 遇到操作数，直接加入后缀表达式；
- 遇到界限符，
- 遇到“（”，则将“(”入栈;
- 遇到“）”，则栈内运算符依次出栈，并加入到后缀表达式，直到弹出“(”为止。注意：“(”“)”不会加入后缀表达式，但“（”也会出栈。
- 遇到运算符
- 从栈顶开始，依次将运算符栈中优先级大于等于当前运算符的所有运算符出栈，加入后缀表达式；(这个遇到的先不加入后缀表达式)
- 若栈中遇到“（”或栈空，则停止出栈，“(”并不出栈。
- 将遇到的运算符压栈。
- 按1) 2) 3)处理完所有字符后，将栈中所有剩余运算符，依次出栈，并加入后缀表达式。
以A+B*(C-D)-E/F为例，进行中缀表达式转后缀表达式
| 执行顺序 |
执行位置 |
执行情形 |
栈状态(栈尾,...,栈头) |
后缀表达式状态 |
| 1 |
A+B*(C-D)-E/F |
1 |
A |
|
| 2 |
A+B*(C-D)-E/F |
3 |
+ |
A |
| 3 |
A+B*(C-D)-E/F |
1 |
+ |
AB |
| 4 |
A+B*(C-D)-E/F |
3 |
*+ |
AB |
| 5 |
A+B*(C-D)-E/F |
2 |
(*+ |
AB |
| 6 |
A+B*(C-D)-E/F |
1 |
(*+ |
ABC |
| 7 |
A+B*(C-D)-E/F |
3 |
-(*+ |
ABCD |
| 8 |
A+B*(C-D)-E/F |
1 |
-(*+ |
ABCD |
| 9 |
A+B*(C-D)-E/F |
2 |
*+ |
ABCD- |
| 10 |
A+B*(C-D)-E/F |
3 |
- |
ABCD-*+ |
| 11 |
A+B*(C-D)-E/F |
1 |
- |
ABCD-*+E |
| 12 |
A+B*(C-D)-E/F |
3 |
/- |
ABCD-*+E |
| 13 |
A+B*(C-D)-E/F |
1 |
/- |
ABCD-*+EF |
| 14 |
A+B*(C-D)-E/F |
4 |
ABCD-*+EF/- |
5.2.3 用栈实现后缀表达式的计算（机算）
- 从左到右扫描下一个元素，直到处理完所有元素；
- 若扫描到操作数则压入栈，并回到1）；否则执行3）；
- 若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶，回到1）。
这里的输入是：后缀表达式，输出是结果。
注意：后缀表达式栈先出栈的是右操作数，后出栈的是左操作数。（与前缀相反）
区别：
将前缀表达式转后缀表达式的栈是用来存放还不能确定运算顺序的运算符；
用栈实现后缀表达式的计算的栈是用来存放还不能确定运算顺序的操作数。
5.2.4 用栈实现中缀表达式的计算（机算）
这个过程就是上面两部分结合起来，但并不是相加，而是穿插（相加也行）。因为在用栈实现后缀表达式的计算中可以发现，并不需要完整的后缀表达式我们才可以计算，只要遇到第一个运算符，我们就可以进行计算，所以我们只要在“前缀转后缀”过程中挨个找到下一个运算符，就可以执行计算。
比如上面的9、10、14我们都可进行计算，不用等到最后，但实际操作还是要按完整的算法来。
初始化两个栈，操作数栈和运算符栈。
- 若扫描到操作数，压入操作数栈。
- 若扫描到运算符，则按照“中缀转后缀”相同的逻辑压入运算符栈
- 从栈顶开始，依次将运算符栈中优先级大于等于当前运算符的所有运算符出栈。
加入后缀表达式；(这个遇到的先不加入后缀表达式) - 每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈。
- 若栈中遇到“（”或栈空，则停止出栈，“(”并不出栈。
- 将遇到的运算符压栈。
- 从栈顶开始，依次将运算符栈中优先级大于等于当前运算符的所有运算符出栈。
5.2.5 中缀表达式转前缀表达式（手算方法）
- 确定中缀表达式的各个运算符的运算顺序。(与后缀相同)
- 选择下一运算符，按照【运算符 左操作数 右操作数】的方式组合成一个新的操作数。
- 如果还有运算符没有被处理，就继续2。
| A+B*(C-D)-E/F |
=>-CD（根据上面转换规则） =>*B-CD =>+A*B-CD =>+A*B-CD /EF =>-+A*B-CD/EF |
(右优先）=>/EF =>-CD /EF =>*B-CD /EF =>-*B-CD/EF =>+A*B-CD/EF |
“右优先”原则：只要右边的运算符能先计算，就优先计算右边的。
5.2.6 用栈实现前缀表达式的计算
- 从右往左扫描下一个元素，直到处理完所有元素；
- 若扫描到操作数则压栈，并回到1；否则执行3
- 若扫描到运算符，则弹出栈顶两个元素，执行相应运算，运算结果压回栈顶，回到1
注意：前缀表达式栈中，先出栈的是左操作数，后出栈的是右操作数。（与后缀相反）
5.3 理解递归调用和栈之间的关系
函数调用的特点：最后被调用的函数最先执行结束（LIFO）。
在任何一段代码运行前，系统都会开辟一段函数调用栈，用来保存函数调用信息。
- 调用返回地址(函数运行结束时，其下一个要执行语句的地址，func1下的c=a+b)
- 实参 (func1中的a,b,func2中的x)
- 局部变量(main 中的 a,b,c)
如下图所示，依次压栈，并按照执行结束顺序依次出栈。
递归：若在一个函数、过程或者数据结构定义的内部又直接（或间接）出现定义本身的应用，则称它们是递归，或者是递归定义的。
在以下三种情况下，常常使用递归的方法。
1. 定义是递归的
有很多数据函数是递归定义的，如大家熟悉的阶乘函数，二阶Fibonacci数列。
int fact(int n){
if(n==1) return 1;
else
return n*fact(n-1);
}
void main() {
// ...其他代码
int x=fact(5);
printf("nc\n");
}
递归调用时，函数调用栈可称为“递归工作栈”；
每进一层递归，就将递归调用所需信息压入栈顶；
每退一层递归，就从栈顶弹出相应信息。
缺点：
从上面可以看出，太多层递归可能导致栈溢出。
而且从fibonacci算法可以看出，递归调用可能造成重复调用。
可以自定义栈将递归算法改造成非递归算法。
2. 数据结构是递归的
3. 问题的解法是递归的
六、队列应用
6.1 队列应用：树的层次遍历
层次遍历指的是一层一层地遍历这些结点，“左优先”。
新建一个空队列；
6.2 队列应用：图的广度优先遍历
新建一个空队列
6.3 队列在操作系统中的应用
多个进程争着使用有线的系统资源时，FCFS（First Come First Service，先来先服务）是一种常用策略。