今日格言：有很多时候，勇气不是从你的脑袋里生出，而是从你的脚下涌现。

考纲和命题形式

考纲

1. 栈和队列的基本概念
2. 栈和队列的顺序存储结构
3. 栈和队列的链式存储结构
4. 多维数组的存储
5. 特殊矩阵的压缩存储
6. 栈、队列和数组的应用

命题形式

• 通常以选择题1至2题考察4个考点
• 大题中只有19年考了一个队列
  题目不算难，但命题的形式比较灵活，其中栈（出入栈的过程、出栈序列的合法性和种类）以及其特征是重点。

栈

基本概念

🌟栈的定义：栈（Stack）是只允许在一端进行插入或删除操作的线性表。也就是说栈是一种受限线性表，限定这种线性表只能在某一端进行插入和删除操作。这是从数据的逻辑结构上了解栈。

如上图所示：不含任何元素的栈叫做空栈也是空表。
🌟栈顶（Top）是栈（线性表）允许进行插入和删除的那一端。
🌟栈底（Bottom）是固定的，不允许进行插入和删除的另外一端。
可以将其形象地记忆为垒起来的石堆(stack)或者一摞只允许从上面放下或者拿走的一摞盘子。
另外，从图中可以看出$a_1$是栈底元素，$a_4$是栈顶元素，$a_1$虽然最先从栈顶入栈，但是要想出栈必须在$a_4$出栈之后，这就是栈的操作特性：后进先出即Last in First out（LIFO）。
下面这段简单的模拟栈的C语言程序有助于理解：

#include<stdio.h>
int main(){    

int Stack[5];    
int top = -1;  //模拟栈顶指针    
int bottom = 0;        

Stack[++top]=985;//模拟入栈    
Stack[++top]=211;    
Stack[++top]=400;        

while(top >= bottom) { //按序打印栈中内容        
    printf("当前栈顶元素为：%d\n",Stack[top]);// 打印当前栈顶元素        
    top--; // 出栈    
}        
    return 0;
}    

栈的基本操作

接下来从数据的运算角度来看栈—栈的基本操作。除了上面提到的进栈、出栈操作，栈还有以下基本操作：

• 创： InitStack(&S):初始化一个空栈S。
• 销：DestroyStack(&S):销毁栈，并释放栈S占用的存储空间（顺序栈使用静态数组存储元素，只需逻辑上删除所有元素即可，存储空间系统自动回收）。
• 查：GetTop(S,&x):若栈S非空，则读取栈顶元素，并不出栈；若栈为空则报错。
• 判空：StackEmpty(S):判空操作，若S为空栈，则返回true否则返回false。
  入栈和出栈的操作如下：
• 增：Push(&S,x):若栈未满则进栈，使x成为新栈顶，若栈满则报错。
• 删：Pop(&S,&x):出栈，若栈非空，则弹出栈顶元素并用x返回；若栈空则报错。
  一个小知识点：当n个不同元素进栈时，出栈元素不同排列的个数为：
  
  这个数也叫做卡特兰数。

栈的两种存储方式

接下来我们将从数据的存储结构上来了解栈，栈也采用之前线性表使用的两种存储结构—顺序存储和链式存储。至于索引存储，我只在操作系统和计算机组成原理的存储系统这一章里看到过，而散列存储似乎和查找这一章节有关。

顺序栈

🌟采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素，同时附设一个指针top指示当前栈顶元素的位置。（真正有效的文字就应该这样，简短而富含信息，值得学习）一组连续的存储单元在这里就是指静态数组。

代码

示例代码仅供参考，更严谨代码请动手写代码并且运行。
1.顺序栈的定义

#include <stdio.h>
#define MaxSize 10
typedef struct {
ElemType data[Maxsize];
int top;
}SqStack;	//Sequence Stack 顺序栈

建议写代码的时候脑子里也要想着内存图：

2. 顺序栈的基本操作

//初始化 
void InitStack(SqStack &S) {
	S.top = -1;    //初始化栈顶指针 
}
//判栈空
bool StackEmpty(SqStack S) {
	if(S.top == -1)
		return true;
	else
	    return false;
} 
//进栈
bool Push(SqStack &S,ElemType x) {
	if(S.top == MaxSize - 1)
		return false;	//栈满报错
	S.data[++S.top] = x;
	return true; 
} 
//出栈
bool Pop(SqStack &S,ElemType &x) {
	if(S.top == -1)
		return false;    //栈空报错
	x = S.data[S.top--];
	return true;
} 
//读栈顶元素
bool GetTop(SqStack S,ElemType &x) {
	if(S.top == -1)
		return false;    //栈空报错
	x = S.data[S.top];   //x记录栈顶元素
	return true; 
} 

另一种方法是令top为0，这就会带来入栈操作、出栈操作、判空操作和判满操作的变化：

S.data[top++]=x;//进栈
x=S.data[--top];//出栈
if(S.top == 0) //判空
if(S.top == MaxSize)  //判满

3. 使用顺序栈实现第一个模拟栈的程序

int main() {
	ElemType x;
	SqStack S;
	InitStack(S);
	Push(S,985);
	Push(S,211);
	Push(S,400);
	while(!StackEmpty(S)) {
		Pop(S,x); //获取栈顶元素并出栈
		printf("当前栈顶元素为%d\n",x); 
	}
	return 0;
} 

共享栈

利用栈底位置相对不变的特性，可让两个顺序栈共享一个一维数组空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸，如下图所示：

两个栈的栈顶指针都指向栈顶元素，top0=-1时0号栈为空，top1=MaxSize时1号栈为空；仅当两个栈顶指针相邻（top1-top0=1）时，判断栈满。当0号栈进栈时top0先加上1再赋值，1号栈进栈时top1先减1再赋值，出栈时顺序正好相反。
共享栈是为了更有效地利用存储空间，两个栈的空间相互调节，只有在整个存储空间被占满时才发生上溢。其存取数据的时间复杂度均为O(1)，所以对存取效率没有什么影响。
定义及初始化代码如下：

#define MaxSize 10
typedef struct{
ElemType data[MaxSize];
int top0;  //0号栈栈顶指针
int top1;  //1号栈栈顶指针
}ShStack;
void InitStack(ShStack &S) {
S.top0 = -1;
S.top1 = MaxSize;
}

链栈

🌟定义：采用链式存储的栈就是链栈。
优点：便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常采用单链表实现，并规定入栈和出栈操作是在单链表的表头进行的。采用链式存储，便于结点的插入与删除。链栈的操作与链表类似，入栈和出栈的操作都在链表的表头进行。需要注意的是：对于带头结点和不带头结点的链栈，具体的实现会有所不同。

链栈本质上还是一个单链表，只不过是把表头的那端当作栈顶。入栈操作对应单链表的头插法，出栈操作对应头结点的后删操作。
下面这个过程图是使用带头结点的链栈实现第一个模拟栈的C语言程序：

代码

1.带头结点的链栈(c++完整版)

/带头结点的链栈
#include <iostream>
#include <cstdio>
#include <cstdlib>

typedef int ElemType;    //定义元素类型为int类型

typedef struct LinkNode{
	ElemType data;    //数据域
	struct LinkNode *next;    //指针域
}LinkStack, *Lhead;

//初始化
void InitStack(Lhead &L) {   
	L=(LinkStack *)malloc(sizeof(LinkStack));   
	L->next = NULL;
}
//判栈空
bool StackEmpty(Lhead L){    
	if(L->next == NULL)        
		return true;    //栈空    
	else        
		return false;    
}
//进栈
bool Push(Lhead &L,ElemType x){    
	LinkStack *p = (LinkStack *)malloc(sizeof(LinkStack));    
	if(p==NULL)        
	return false;//申请空间失败    
	p->data = x;    
	p->next = L->next;    
	L->next = p;    
	return true;    
}
//出栈
bool Pop(Lhead &L,ElemType &x) {    
	if(StackEmpty(L))        
		return false;    //栈空    
	LinkStack *p = L->next;    //找到栈顶结点    
	x = p->data;    //获取栈顶元素    
	L->next = p->next;    //出栈    
	free(p);    //释放结点空间    
	return true;
}

int main() {
//用链栈表示第一个模拟栈程序    
	ElemType x;    
	Lhead L;    //创建一个链栈并初始化    
	InitStack(L);    
	Push(L,985);    
	Push(L,211);    
	Push(L,400);    
//按序打印栈中元素    
	while(!StackEmpty(L)){        
		Pop(L,x);    //获取栈顶元素并出栈        
		printf("当前栈顶元素为：%d\n",x);    
	}    
	Pop(L,x);    
	return 0;
}

2.不带头结点的链栈

队列

仍然从逻辑结构、基本运算、存储结构这三个方面了解队列

队列的基本概念

1.队列的定义
队列(Queue)和栈一样也是一种操作受限的线性表，只允许在表的一端进行插入，而在表的另一端进行删除。允许删除的一端称为队头(Front)，又称队首。允许插入的一端称为队尾(Rear)。向队列中插入元素称为入队或进队；删除元素称为出队或离队。这和日常生活中的排队是一致的，最早排队的也是最早离队的，其操作特性是先进先出(FIFO)。
2.队列常见的基本操作

• 创：InitQueue(&Q)—初始化队列构造一个空队列。
• 销：DestroyQueue(&Q)—销毁并释放Q队列所占的内存空间。
• 增：EnQueue(&Q,x)—若队列未满，将x加入，使之成为新的队尾。
• 删：DeQueue(&Q,&x)—出队，若队列未空，删除队头元素，并用x返回。
• 判队空：QueueEmpty(Q)—若队列为空返回true，否则返回false。
• 读队头：GetHead(Q,&x)—若队列非空，则将队头元素赋值给x。

队列的顺序存储结构

队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针：队头指针(front)和队尾指针(rear)。队头指针front指向队头元素，队尾指针rear指向下一个应该插入的位置。(有的程序也将队尾指针指向队尾元素，具体情况具体分析，就像顺序栈中的top指针赋值0还是-1一样)。所以顺序队列中的指针并不是真的指针，而是数组的索引，通过数组下标的改变进行入队/出队操作。
我们可以用数组先模拟顺序队列，C语言代码如下：

#include <stdio.h>

int main(){    
  int Queue[10];    
  int front=0;   //队头指针 
  int rear=0;   //队尾指针     
//模拟入队    
  Queue[rear++]=985;    
  Queue[rear++]=211;    
  Queue[rear++]=400;        
//模拟出队    
  while(front!=rear){        
      printf("当前队首元素是：%d\n",Queue[front]);    //获取队首元素    
      front++;    
  }    
return 0;
}    

实际上，队列的顺序存储类型可描述为：

#define MaxSize 10    //定义队列中元素的最大个数
typedef struct{
    ElemType data[MaxSize];
    int rear,front;
}SqQueue;

• 初始化时：Q.front=Q.rear=0
• 进队操作：队不满时，先送值到队尾元素，再将队尾指针加1。
• 出队操作：队不为空时，先取队头元素值，再将队头指针加1。
• 判空条件：显然此时Q.front=Q.rear=0，成立时，队空。
  在数组中存放abcde五个元素后，其内存图大致如下所示。下面是顺序队列中常用的判空、判满、入队、出队操作

//初始化
void InitQueue(SqQueue &Q){    
  Q.front=Q.rear=0;
}
//判队空
bool QueueEmpty(SqQueue Q) {    
  if(Q.front==Q.rear)        
      return true;    
else        
  return false;    
}
//判队满
//入队
bool EnQueue(SqQueue &Q,ElemType x){    
  if(队满)        
      return false;    
  Q.data[Q.rear] = x;    
  Q.rear++;    
return true;
}
//出队
bool DeQueue(SqQueue &Q,ElemType &x){    
  if(队空)        
      return false;    
  x = Q.data[Q.front];    
  Q.front++;    
  return true; 
}
//获取队头元素
bool GetHead(SqQueue Q,ElemType &x)
{    if(队空)        
      return false;    
  x = Q.data[Q.front];    
  return true; 
}

表面上看，似乎没啥问题，初始条件是Q.frontQ.rear=0，判空条件是Q.frontQ.rear ，这说明队里的元素已经没了。那么判满条件呢？是Q.rear==MaxSize吗？显然不是，比如下图：

此时rear已经超出了数组的合法范围，也已经无法再插入新的元素，这是入队将出现“上溢出”，Q.rear==MaxSize，但是队列真的满了吗？并没有，这种溢出并不是真正的溢出，因为图中data数组依然存在可以存储元素的空位置 。我们把这种溢出称为**“假溢出” ** 。
为了解决顺序队列存在的“假溢出”问题，我们引入了循环队列。

循环队列

为了充分利用顺序队列的空间，我们可以化直为曲，即把存储队列元素的表从逻辑上视为一个环，称为循环队列。

如上图，当Q.rear==5，但是0位置或者0,1这些位置上由于出队操作，并没有存放元素时；我们可以让Q.rear置0，也就相当于在Q.rear==4之后，按照环装结构直接变成了0而不是5。这样就能充分利用空着的位置，也就解决了“假上溢”的问题。
Ok，解决完了这个问题，会不会引起判空和判满条件发生改变呢？
不会引起判空条件的改变，仍然是Q.front==Q.rear，这表明执行一次出队操作后front指针和rear指针之间已经没有元素了，也就是队列空了。
判满条件已经说了，显然不是Q.rear==MaxSize，那么是Q.rear-Q.front==MaxSize吗？
也不是因为我们这里已经决定采取循环队列，也就是在遇到“假溢出”时，我们让已经Q.rear==MaxSize-1的尾指针，变为0，这通过取模运算来实现，也就是(Q.rear+1)%MaxSize。
另外，如果想要解决“假溢出”后，队尾指针rear重回数组下标为0位置上的元素出队，我们也需要队头指针front跨过“界限”，重回0，所以也要使用取模运算达到这个效果Q.front=(Q.front+1)%MaxSize。当然，我们发现如果没有出现“假溢出”的情况时Q.front(rear)+1恒小于MaxSize，也自然而然与之前的入(出)队操作Q.front(rear)+1效果一致，这说明我们在解决问题的同时也没有影响之前正确的逻辑，效果很好。
但是当入队速度快于出队速度，最终达到队满时，会出现Q.rear==Q.front的情况，这与我们判断栈空的条件相同了，这会导致难以区分队空与队满，显然我们要避免这种情况。如下图所示：

有一种方法是空出一个存储单元，从而让Q.rear≠Q.front，从而区分队满和队空的情形，如图d2所示。
队空时，条件是Q.rear==Q.front。
队满时，不难看出，rear指针的下一个位置就是front指针。如果Q.rear+1<MaxSize，自然此时判断队满的条件是Q.rear+1==Q.front；但是如果是Q.rear+1==MaxSize就还需要靠取模运算(Q.rear+1)%MaxSize==Q.front
显然后者在数学上包含了前者，所以统一为：(Q.rear+1)%MaxSize==Q.front。
提个问题，请问循环队列中，队首指针为Q.front，队尾指针为Q.rear时，队列中元素的个数是多少？
分类讨论：

• 如果没有出现“假上溢”的情况，队尾指针肯定会大于队首指针，此时元素的个数是Q.rear-Q.front。
• 但是如果出现了“假上溢”的情况，队尾指针就会小于队头指针，在队头指针还在走第一圈的时候，它已经走了第二圈，所以要加上一圈的个数MaxSize之后再相减，也就是Q.rear-Q.front+MaxSize。
  但是我们要用一个式子统一实现这两种情况，于是就又用到了取模(Q.rear-Q.front+MaxSize)%MaxSize
  剩下两种方法不空出存储单元，也能区分开队满与队空：
• 在定义队列这个数据结构时，增设size成员，表示元素个数。入队成功则size+1，出队成功则size-1；队空时Q.size==0,队满时Q.size==MaxSize，此时Q.rear==Q.front。
• 在定义队列这个数据结构时，增设tag标签，入队则置tag为1，出队则置tag为0，队空执行的肯定是出队操作，此时tag==0，队满执行的肯定是入队操作，此时tag==1，即使此时Q.rear==Q.front也能区分。
  所以接下来我们给出实现顺序队列的完整c++代码

代码

#include <iostream>
#include <cstdio>

#define MaxSize 10
typedef struct {
	ElemType data[MaxSize];	  //用数组存放队列元素 
	int front;
	int rear;     //队头指针和队尾指针 
}SqQueue;

//初始化 
void InitQueue(SqQueue &Q) {
	Q.front = Q.rear = 0; 
}
//判空
bool QueueEmpty(SqQueue Q) {
	if(Q.front == Q.rear)
	    return true;
	else
	    return false;
} 
// 入队
bool EnQueue(SqQueue &Q,ElemType x) {
	if((Q.rear+1)%MaxSize==Q.front)
	    return false;
	Q.data[Q.rear] = x;
	Q.rear = (Q.rear+1)%MaxSize;
	return true;
} 
// 出队
bool DeQueue(SqQueue &Q,ElemType &x) {
	if(QueueEmpty(Q))
	    return false;    //队空则报错 
	x = Q.data[Q.front];
	Q.front = (Q.front+1)%MaxSize;    //队头指针加1取模 
	return true;
}
int main() {
    SqQueue Q;
	ElemType x;
	InitQueue(Q);
	EnQueue(Q,985);
	EnQueue(Q,211);
	EnQueue(Q,400);
	while(!QueueEmpty(Q)) {
		DeQueue(Q,x);
		printf("当前队首元素为：%d\n",x);
	}
	
return 0;
}

队列的链式存储结构

队列的链式表示称为链队列，它实际上是一个同时有队头指针和队尾指针的单链表，头指针指向队头结点，尾指针指向队尾结点，即单链表最后一个结点。如下图所示：
用单链表表示的链式队列特别适合于数据元素变动比较大的情形，而且不存在队列满且产生溢出的问题。另外，假如程序中要使用多个队列，与多个栈的情形一样，最好使用链式队列，这样就不会出现存储分配不合理和“溢出的问题”。

带头结点的链队列

#include <iostream>
#include <cstdio>
#include <cstdlib>

typedef int ElemType;
typedef struct LinkNode{
	ElemType data;
	struct LinkNode *next;
}LinkNode;
typedef struct{
	LinkNode *front, *rear;    //队列的队头和队尾指针 
}LinkQueue;

//初始化带头结点的链队列 
void InitQueue(LinkQueue &Q) {  
	Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));  //初始时front,rear指针都指向头结点 
	Q.front->next = NULL; 
}
//判队空
bool QueueEmpty(LinkQueue Q) {
	if(Q.front == Q.rear) {
		printf("队空！"); 
		return true;
	}
	else
	    return false;
} 
//入队
void EnQueue(LinkQueue &Q,ElemType x) {
	LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));    //malloc在堆上为新结点分配内存空间 
	s->data = x;    //数据装载 
	s->next = NULL;    //尾结点标志 
	Q.rear->next = s;    //原尾结点指向新结点 
	Q.rear = s;    //修改表尾指针 
}
//出队
bool DeQueue(LinkQueue &Q,ElemType &x) {
	if(Q.front == Q.rear) {   //空队 
	    return false;
	} 
	LinkNode *p = Q.front->next;    //创建新结点p，使其指向队首元素(头结点后的第一个结点) 
	x = p->data;    //用变量x返回队头元素 
	Q.front->next = p->next;    //修改队头元素指针，使其指向被删除元素p的下一个元素 
	if(Q.rear == p)    //如果p结点是最后一个结点 
		Q.rear = Q.front;    //修改rear指针使其和front指针相等，此时队中元素个数为0，队列置空 
	free(p);    //释放内存
	p = NULL;    // 
	return true;
}

int main() {
	ElemType x;
	LinkQueue Q;    //声明一个链队列 
	InitQueue(Q);   //初始化队列 
	
	//入队三个元素 
	EnQueue(Q,985); 
	EnQueue(Q,211);
	EnQueue(Q,400);
	while(!QueueEmpty(Q)) {
		DeQueue(Q,x);
		printf("当前队头元素为：%d\n",x);
	}
	return 0;
}

不带头结点的链队列

c++代码如下：

#include <iostream>
#include <cstdio>
#include <cstdlib>

typedef int ElemType;
typedef struct LinkNode {
	ElemType data;
	struct LinkNode *next; 
}LinkNode;
typedef struct {
	LinkNode *front;
	LinkNode *rear;
}LinkQueue;

//初始化不带头结点的链队列
void InitQueue(LinkQueue &Q) {
	Q.front = Q.rear = NULL;    //初始时front,rear都指向NULL 
}
//判队空
bool QueueEmpty(LinkQueue Q) {
	if(Q.rear == NULL) {
		return true; 
	}
	else
	    return false;
} 
//入队
void EnQueue(LinkQueue &Q,ElemType x) {
	LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
	s->data = x ;
	s->next = NULL;
	if(QueueEmpty(Q)) { //不带头结点的队列，第一个元素入队时需要特别处理 
		printf("入队第一个元素!\n");
		Q.front = Q.rear = s;
	}
	else {
		Q.rear->next = s;    //新结点插入到rear结点之后 
		Q.rear = s;    //修改rear指针 
	}
}
//出队
bool DeQueue(LinkQueue &Q,ElemType &x) {
	if(QueueEmpty(Q)) 
	    return false;
	LinkNode *p = Q.front;
	x = p->data; 
	Q.front = p->next;    //修改front指针 
	if(Q.rear == p) { //仅剩最后一个元素 
	    printf("出队最后一个元素!\n"); 
	    Q.rear = Q.front = NULL;  //将front,rear重置为NULL 
	} 
	free(p);
	p = NULL;
	return true;
} 

int main() {
	ElemType x;
	LinkQueue Q;
	InitQueue(Q);
	EnQueue(Q,985);
	EnQueue(Q,211);
	EnQueue(Q,400);
	while(!QueueEmpty(Q)) {
		DeQueue(Q,x);
		printf("当前队头元素为：%d\n",x);
	}
	return 0;
}

双端队列

双端队列是指允许两端都可以进行插入和删除操作的线性表。
输出受限的双端队列：允许在一段进行插入和删除，但在另一端只允许插入的双端队列。
输入受限的双端队列：允许在一段进行插入和删除，但在另一端只允许删除的双端队列。

本质上都是插入和删除受限的线性表。
如果双端队列的一端被限制输入和输出，另一端不限制，那么这个双端队列就退化成栈了。

双端队列的考点固定，就是对输出序列合法性的判断。

比如有这样一道母题，只要把它弄懂就能吃透这个考点了：
$若数据元素输入序列为1，2，3，4$，则在下面四种条件下哪些输出序列是合法的？哪些是非法的？

1. 栈
2. 输入受限的双端队列
3. 输出受限的双端队列
4. 双端队列
   

栈和队列的应用

栈的应用

括号(界限符)匹配

简而言之，就是左界限符和右界限符的匹配，这里以括号匹配为例：

括号匹配的结果只有以下几种：

• 所有括号都能两两配对。
• 当前扫描到的右括号和栈顶左括号不匹配。
• 扫描到了右括号，但是当前栈已空，右括号剩余。
• 右括号配对完毕但是，栈非空，也就是左括号剩余。
  一句话描述括号匹配的过程：依次扫描所有字符，遇到左括号入栈，遇到右括号则弹出栈顶元素检
  查是否匹配。匹配失败情况：①左括号单身②右括号单身③左右括号不匹配
  可以用算法流程图来表示整个匹配过程：
  
  不用基本操作，只用字符数组来实现：

表达式求值

中缀表达式不容易被计算机解析，但仍被许多程序语言使用，因为它更符合人们的思维习惯。
中缀表达式的括号是必需的，计算过程中必须用括号将操作符和对应的操作数括起来，用于指示运算的次序。
后缀表达式也叫逆波兰式，可以不用界限符（括号）也能无歧义地表达运算顺序。
后缀表达式的运算符在操作数后面，后缀表达式中考虑了运算符的优先级，没有括号，只有操作数和运算符。
中缀表达式转后缀表达式的手算方法
中缀表达式转后缀表达式的结果并不是唯一的，会受到运算符顺序的影响，如下图所示：

考虑到算法具有确定性，如果我们用计算机来求后缀表达式的话，我们必须采用一种原则使一个中缀表达式只对应一个后缀表达式，这就是左优先原则。另外，可以看出，整个过程操作数的前后相对顺序是没有改变的，改变的只有运算符的顺序。
在计算机中，中缀表达式转后缀表达式时需要一个栈，用于保存暂时还不能确定运算顺序的运算符。

讨论一下有上面三条规则的原因：

• 第一条规则，是因为操作数的相对先后顺序并没有发生改变，所以可以直接入栈。
• 第二条规则，遇到界限符也就是左右括号，因为括号里面的表达式优先级最高，所以我们遇到左括号时让它直接入栈，然后才能知道括号里面到底有什么。如果遇到右括号，就说明括号内的表达式已经读完了，需要确定括号内的运算优先级也就是弹出栈内运算符，直到遇到了左括号"("说明括号内的表达式结束了。
• 第三条规则，碰到运算符，需要确定运算符的优先级，括号内最先算，然后先乘除后加减，从左往右。所以我们要从左至右先算优先级高的再算优先级低的，也就是碰到一个运算符，如果其优先级高于当前栈顶运算符的，则直接入栈。否则，从栈顶开始，依次弹出优先级高于或等于当前运算符的所有运算符或者遇到"("时为止。之后再把当前运算符入栈。
• 按上述方法扫描所有字符后，再将栈中剩余运算符依次弹出，并加入后缀表达式。
  举个例子：

所谓栈的深度，是指栈中元素的个数，通常是给进栈和出栈序列，求最大深度。
对于手算后缀表达式：


每遇到一个运算符都要先取出运算符，然后取出其左右操作数，但运算符是后进的但却最先弹出，所以这符合栈的后进先出特性。
通过计算机算后缀表达式

中缀转前缀

前缀表达式的计算

递归(函数)调用

递归是一种重要的程序设计方法，若在一个函数、过程或数据结构的定义中又应用了它自身，则这个函数、过程或数据结构称为是递归定义的，简称递归。
递归策略只需少量代码就可以描述出解题过程所需要的多次重复计算，大大减少了程序的代码量，代码简单，容易理解。但在通常情况下，它的效率不太高。
递归必须满足下面两个条件：

• 递归表达式（递归体）
• 边界条件（递归出口）
  函数调用背后的过程
  
  

可以看出，函数调用过程同样具有LIFO的特性，与栈是相同的，所以可以使用一个栈存储函数调用过程中的一些必要内容，这个栈就是函数调用栈。需要用栈来存储的内容包括：

• 调用返回地址，它能告诉函数调用结束后应该执行哪条语句。
• 实参，函数调用需要传入实参。
• 局部变量，局部变量可能记录了函数调用的结果。
• 栈指针

这些内容被称为“栈帧”，需要占用一定的内存空间。而栈空间通常由操作系统预先分配，大小固定(通常1-8MB)，所以如果递归调用次数太多，空间复杂度过大，栈帧累积超过预设空间，就会出现栈溢出。

什么是递归？
递归是一种算法设计技巧，它通过将原始问题转换为属性相同，但规模较小的问题来求解。最典型的例子就是：求阶乘和求斐波那契数列。递归调用时，函数调用栈可称为“递归工作栈”，每进入一层递归，就将递归调用所需信息压入栈顶，每退出一层递归，就从栈顶弹出相应信息。


另外也可以看出，使用递归解决斐波那契数列问题时会出现重复计算的问题，所以我们可以采用数组缓存的方法减少重复计算，进行优化。此外也可以不使用递归，而是迭代或者尾递归。

队列的应用

在信息处理中有一大类问题需要逐层或逐行处理。这类问题的解决方法往往是在处理当前层或当前行时就对下一层或下一行做预处理，把处理顺序安排好，等到当前层或当前行处理完毕，就可以处理下一层或下一行。

树的层次遍历

可以看出，从上到下，从左往右，一层一层的遍历。其实可以使用与树相关的专业术语来描述整个过程:

先遍历父结点，然后再遍历父节点的兄弟结点，最后遍历父节点的子结点。 可以把这个过程看作入队和出队的过程：

• 根节点1入队，将其子结点2，3也入队，先左孩子后右孩子，然后1出队。

• 2入队，将2的左右结点4，5入队，接着2出队。

• 3入队，将3的左右结点6,7入队，3出队。

• 4入队，4没有左右结点，4直接出队。

• 5入队，将5的左右结点8，9入队5出队……，

图的广度优先遍历

广度优先遍历（Breadth-First Search，BFS）是一种逐层遍历图的算法，它从起始顶点开始，先访问所有直接相邻的顶点，然后再访问这些相邻顶点的相邻顶点，以此类推。这种遍历方式类似于水波扩散的过程。

BFS核心思想

1. 层级扩展：按距离起始顶点的层级依次访问
2. 队列驱动：使用队列管理待访问顶点
3. 避免重复：标记已访问顶点防止重复处理
4. 最短路径：在无权图中可找到最短路径

有点类似于树中的层次遍历，但是二叉树层级遍历顺序固定而图的广度优先遍历（BFS）结果不唯一，可能存在多种合法的顶点访问序列。这与图的表示方式和算法实现细节密切相关。具体内容如下图所示：

合法BFS序列（从A开始）：
A → B → C → D
访问A后：队列 [B, C]
先出队B → 访问B → 入队D → 队列 [C, D]
出队C → 访问C → D已在队列
出队D → 访问D

A → C → B → D
访问A后：队列 [C, B]（邻接表C在前）
先出队C → 访问C → 入队D → 队列 [B, D]
出队B → 访问B → D已在队列
出队D → 访问D
文字描述就是：创建队列和访问标记数组，起始顶点入队并标记为已访问;当队列非空： 出队顶点v
访问v，将v的所有未访问邻接点入队并标记。

//伪代码
 BFS(Graph G, Vertex start):
    创建队列Q
    创建访问数组visited[所有顶点]=false
    
    visited[start] = true
    Q.enqueue(start)
    
    while Q不为空:
        v = Q.dequeue()
        访问v
        
        for each 邻接点w in v的邻接表:
            if visited[w] == false:
                visited[w] = true
                Q.enqueue(w)

队列在计算机系统中的应用

队列在计算机系统中的应用非常广泛，以下仅从两个方面来阐述：第一个方面是解决主机与外部设备之间速度不匹配的问题，第二个方面是解决由多用户引起的资源竞争问题。
在操作系统中，当多个进程争抢着使用有限的系统资源时，FCFS（First Come First Service， 先来先服务）是一种常用策略，这和队列的特性FIFO相符，所以我们可以使用队列来实现。

cpu资源的竞争

这样既能满足每个进程的执行又能使CPU能够正常运行。

主机和打印机之间速度不匹配

主机输出数据给打印机打印，输出数据的速度比打印数据的速度要快得多，因为速度不匹配，若直接把输出的数据送给打印机打印，则显然是不行的。解决的方法是设置一个打印数据缓冲区，主机把要打印的数据依次写入这个缓冲区，写满后就暂停输出，转去做其他的事情。打印机就从缓冲区中按照先进先出的原则依次取出数据并打印，打印完后再向主机发出请求。主机接到请求后再向缓冲区写入打印数据。这样既保证了打印数据的正确，又使主机提高了效率。

数组和矩阵

数组的存储结构

一维数组的存储结构

一个数组的所有元素在内存中占用一段连续的存储空间。

二维数组的存储结构

显然分为两种存储方式：行优先是4×2存储；列优先是2×4存储。
如果起始地址为LOC，则对于一个M行N列的二维数组，其数组元素b[i][j]的存储地址为：

• 行优先：LOC +（i×N+j）× sizeof(ElemType)
• 列优先：LOC + (j×M+i) × sizeof(ElemType)

矩阵存储

在数据结构中考虑的是如何用最小的内存空间来存储同样的一组数据。我们的目标是：将矩阵更有效地存储在内存中，并能方便地提取矩阵中的元素。

普通矩阵存储

普通矩阵可以使用二维数组存储，不过描述矩阵时行号和列号从1开始。

特殊矩阵压缩存储

在线性代数中，学过一些特殊矩阵，它们中有些元素存在重复，因此不必每个元素都存储。我们可以找出特殊矩阵中值相同的矩阵元素的分布规律，把那些呈现规律性分布的、值相同的多个矩阵元素压缩存储到一个存储空间中。
压缩存储：指为多个值相同的元素只分配一个存储空间，对零元素不分配空间。

对称矩阵

因为上三角区的所有元素和下三角区的对应元素相同，若仍采用二维数组存放，则会浪费几乎一半空间，所以可以将n阶对称矩阵A存放在一维数组$B[\frac{n(n+1)}{2}]$中。
在这里我们选取其中的一种策略：只存储主对角线+下三角形区的元素，并采用行优先的原则将各元素存入一维数组中。则矩阵中的某个元素a[i][j]和其对应的一维数组元素b[k]，数组下标之间的关系为：
$$k=\{\begin{array}{ll}\frac{i(i-1)}{2}+j-1,& i⩾j（下三角区和主对角线元素）\\ \frac{j(j-1)}{2}+i-1,& i<j（上三角区元素a_{ij}=a_{ji}）\end{array}$$
推导过程如下：

上三角形矩阵

上三角矩阵中，下三角区的所有元素均为同一常量，只需存储主对角线、上三角区上的元素和下三角区的常量一次，可将其压缩存储在组$B[\frac{n(n+1)}{2}+1]$
按照行优先原则，$a[i][j]和b[k]$的对应关系如下：
$$k=\{\begin{array}{llc}\frac{(i-1)(2n-i+2)}{2}+(j-i),& i⩽j\text{(上三角区和主对角线元素)}& \\ \frac{n(n+1)}{2},& i>j\text{(下三角区元素)}& \end{array}$$

下三角形矩阵

压缩存储策略：按行优先原则将橙色区元素存入一维数组中，并在最后一个位置存储常量c，也是存储在$B[\frac{n(n+1)}{2}+1]$中。
按照行优先原则，$a[i][j]和b[k]$的对应关系如下：
$$k=\{\begin{array}{llc}\frac{(i-1)i}{2}+(j-1),& i⩾j\text{(下三角区和主对角线元素)}& \\ \frac{n(n+1)}{2},& i<j\text{(上三角区元素)}& \end{array}$$

三对角矩阵

三对角矩阵，又称带状矩阵：对n阶矩阵A中的任意一个元素$a_{i,j}当|i-j|>1时，恒有a[i][j]=0（1\le i,j\le n$。

如上图所示，可以看出所有的非零元素都集中在以主对角线为中心的3条对角线的区域，其他区域的元素都为0。
压缩存储策略：按行优先（或列优先）原则，只存储带状部分。
按照行优先原则，$a[i][j]$对应一维数组中的索引$k为：k=2i+j-3$，证明过程如下：

同样地，若已知三对角矩阵中的某个元素$a_{i,j}$存放在一维数组B的第$k$个位置，则有$i$等于多少？

稀疏矩阵

稀疏矩阵：非零元素远远少于矩阵元素的个数，通常以小于1%为界限。

顺序存储—— 三元组法

如果采用常规的方法存储稀疏矩阵，则相当浪费存储空间，因此仅存储非零元素即可，存储非零元素当然要存储它所在的行、列和值。这就是三元组，它可以记为$(i,j,v)$。
以上图中的稀疏矩阵为例，形成的三元组线性表为：

行	列	值
1	3	4
1	6	5
2	2	3
2	4	9
3	5	7
4	2	2

可以看出稀疏矩阵压缩后便失去了随机存取特性。

链式存储——十字链表法

十字链表法之后还会在图这一章6.2节遇到，到时候再和这个联系一下：

错题

栈

第一次做对了，但第二次做错了，根本原因就是用的是举特例，第一次列出来了，第二次列出来少了一个，本质上还是不会，应该使用讨论的方法，真正做对。

23:
24.
共享栈是为了更有效地利用存储空间，两个栈的空间相互调节，只有在整个存储空间被占满时才发生上溢。
正确答案：B.节省存储空间，降低发生上溢的可能

核心优势对比：

指标	独立双栈	共享栈	优势原因
存储空间	需分配固定大小 N×2	仅需分配 N	空间利用率可达 100%
上溢概率	栈1/栈2 各自满即溢	两栈共享空间才满	临界容量提升 100%
存取时间	O(1)	O(1)	⚠️ 无变化
下溢概率	各自空即溢	各自空即溢	⚠️ 无变化

关键技术验证：

• 空间节省：共享栈使得总空间需求从 N×2 降到 N（设 N 为最大需求）
• 上溢优化：单个栈空间需求峰值通常 < 总容量（如栈1用 60% 时栈2可用 40%）
• ⚠️ 下溢无关：栈为空时弹出操作即下溢，与是否共享无关
• ⚠️ 存取效率：入栈/出栈操作仍为 O(1)，无本质提升

队列

这个纯属没睡醒，选错了，当然是选A链头。

这个我感觉A,D都对，但是答案是选D，答案确实没错，队首指针和队尾指针都是指针，不能直接根据队首指针和队尾指针计算队列的长度。
​A. 优点是队列的长度不受限制​
​正确​：链式队列基于链表，节点可动态创建，长度仅受内存限制；顺序队列基于数组，大小固定。这是链式队列的核心优势。
​B. 优点是入队和出队时间效率更高​
​错误​：两者入队（enqueue）和出队（dequeue）的时间复杂度均为 ​O(1)​​（顺序队列循环实现也是O(1)），无显著效率差异。
​C. 缺点是不能进行顺序访问​
​错误​：链式队列支持顺序访问（可通过指针从头到尾遍历元素）；顺序队列也支持顺序访问（数组顺序）。队列操作本质是顺序访问，二者均支持。
​D. 缺点是不能根据队首指针和队尾指针计算队列的长度​
​正确但非核心​：链式队列中，队首指针（front）和队尾指针（rear）无法直接计算长度（需遍历或额外变量）；顺序队列可计算（如索引差）。这是一个缺点，但不是主要区别。

栈和队列的应用

全对，不过还有一个没学到的地方：FIFO页面替换算法中用到了队列。

数组和矩阵压缩

这个太坑了，数组下标从1开始，没仔细看。


这个做的时候虽然有所疑问，但还是选了相反地答案，归根结底是知识不充足。
答案选A，只需要保存​M的行数和M的列数。
​为什么需要总行数和总列数？​​
​恢复原矩阵​：必须知道原始矩阵的总行数（rows）和总列数（cols）才能重构矩阵结构（包括全零行/列）。
​边界定位​：运算（如矩阵乘法）需依赖总行/列数确定计算规则。
​避免歧义​：若只存非零元素的位置，无法确定矩阵是否有尾部全零行列。
​为什么不需要II和IV？​​
非零元素的行数（II）和列数（IV）​不需要单独存储​：
非零元素的行数 → 遍历三元组表即可得到不同行号的数量。
非零元素的列数 → 同理，无需额外空间存储。

比如区分这两个矩阵就需要矩阵M的总行数和总列数。