3.1 栈(stack)

3.1.1 栈的基本概念

栈的基本概念.pdf

栈的定义

栈是特殊的线性表：只允许在一端进行插入或删除操作，其逻辑结构与普通线性表相同；
操作特性：后进先出LIFO^[LIFO：Last In First Out，后进栈的元素先出栈]
缺点：栈的大小不可变，解决方法——共享栈；
相关概念
- 栈顶：允许进行插入和删除的一端（最上面的为栈顶元素）；
- 栈底：不允许进行插入和删除的一端（最下面的为栈底元素）；
- 空栈：不含任何元素的空表；

栈的基本操作

InitStack(&S) 初始化栈：构造一个空栈S，分配内存空间；
DestroyStack(&S) 销毁栈：销毁并释放栈S所占用的内存空间；
Push(&S, x) 进栈：若栈S未满，则将 x 加入使其成为新栈顶；
Pop(&S, &x) 出栈：若栈S非空，则弹出（删除）栈顶元素，并用x返回；
GetTop(S, &x) 读取栈顶元素：若栈S非空，则用 x 返回栈顶元素；（栈的使用场景大多只访问栈顶元素）；
StackEmpty(S) 判空：判断一个栈S是否为空，若S为空，则返回true，否则返回false；

栈的常见题型

$n$ 个不同元素进栈，出栈元素不同排列的个数为 $\frac{1}{n + 1} C_{2 n}^{n}$ （卡特兰数）考前记一记
给定进栈顺序，判断有哪些合法的出栈顺序；
给定进展顺序和出栈顺序，判断出栈顺序是否合法；

LeetCode946. 验证栈序列

3.1.2 栈的顺序存储

栈的顺序存储演示

栈的顺序存储实现.pdf

顺序栈的基本操作

顺序栈的定义

顺序栈结构体算法题

#define MaxSize 10	//定义栈中元素的最大个数
 
typedef struct{
	ElemType data[MaxSize];	//静态数组存放栈中元素
	int top;				//栈顶指针。从零开始，-1代表空栈
}SqStack;

顺序栈的初始化

//初始化栈
void InitStack(SqStack &S){
	S.top = -1;	//初始化栈顶指针
}
 
void testStack(){
	SqStack S;	//声明一个顺序栈(分配空间)
	InitStack(S);
	//...
}

注：也可以初始化时定义 S.top = 0 ：top指针指向下一个可以插入元素的位置（栈顶元素的后一个位置），此时栈的基本操作略有不同；

判空：if(S.top == 0)
进栈使用：S.data[S.top++] = x，先赋值再改下标
出栈使用：x = S.data[--S.top]，先改下标再赋值
判断栈满：s.top == MaxSize

顺序栈的进栈操作

bool Push(SqStack &S, ElemType x){
	if(S.top == MaxSize - 1)//栈满
		return false;
 
	S.top = S.top + 1;	//指针先加1
	S.data[S.top] = x;	//新元素入栈
	/*或者
	S.data[++S.top] = x;
	*/
	return true;
}

顺序栈的出栈操作

bool Pop(SqStack &S, ElemType &x){
	if(S.top == -1)	//栈空
		return false;
 
	x = S.data[S.top];	//先出栈
	S.top = S.top - 1;	//栈顶指针减1
	/*或者
	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;
}

顺序栈判断栈空

bool StackEmpty(SqStack S){
	if(S.top == -1)	//栈空
		return true;
	else	//栈不空
		return false;
}

共享栈

共享栈：两个栈共享同一片空间

#define MaxSize 10	//定义栈中元素的最大个数
 
typedef struct{
	ElemType data[MaxSize];	//静态数组存放栈中元素
	int top0;	//0号栈栈顶指针
	int top1;	//1号栈栈顶指针
}ShStack;
 
//初始化栈
void InitSqStack(ShStack &S){
	S.top0 = -1;	//初始化栈顶指针
	S.top1 = MaxSize;
}

栈满条件：top0 + 1 == top1

3.1.3 栈的链式存储结构

栈的链式存储演示

栈的链式存储实现.pdf

用链式存储方式实现的栈

进栈和出栈都只能在栈顶一端进行（链头作为栈顶）
链表的头部作为栈顶，意味着：
- 在实现数据“入栈”操作时，需要将数据从链表的头部插入；
- 在实现数据“出栈”操作时，需要删除链表头部的首元节点；

因此，链栈实际上就是一个只能采用头插法插入或删除数据的链表

typedef struct Linknode{
	ElemType data;			//数据域
	struct Linknode *next;	//指针域
}*LiStack;	//栈类型的定义

链栈的基本操作

参考：单链表上基本操作的实现

参考：链栈基本操作(带头结点及不带头结点)

带头结点链栈的基本操作

定义

#include<stdio.h>
 
struct Linknode{
	int data;		//数据域
	Linknode *next;	//指针域
}Linknode,*LiStack;
 
typedef Linknode *Node;	//结点结构体指针变量
typedef Node List;		//结点结构体头指针变量

初始化

void InitStack(LiStack &L){	//L为头指针
	L = new Linknode;
	L->next = NULL;
}

判栈空

bool isEmpty(LiStack &L){
	if(L->next == NULL)
		return true;
	else
		return false;
}

进栈操作：即使用头插法插入结点

注：链栈基本上不会出现栈满的情况，故不需要判断栈满

void pushStack(LiStack &L, int x){
	Linknode s;	//创建存储新元素的结点
	s = new Linknode;
	s->data = x;
 
	//头插法
	s->next = L->next;
	L->next = s;
}

出栈操作：删除头结点的下一个结点，即头删法

bool popStack(LiStack &L, int &x){
	Linknode s;
	if(L->next == NULL)	//栈空不能出栈
		return false;
 
	s = L->next;
	x = s->data;//x返回栈顶元素
	L->next = L->next->next;
	delete(s);
 
	return true;
}

不带头结点链栈的基本操作

定义

#include<stdio.h>
 
struct Linknode{
	int data;	//数据域
	Linknode *next;	//指针域
}Linknode,*LiStack;
 
typedef Linknode *Node;	//结点结构体指针变量
typedef Node List;	//结点结构体头指针变量

初始化

void initStack(LiStack &L){
	L=NULL;
}

判栈空

bool isEmpty(LiStack &L){
	if(L == NULL)
		return true;
	else
		return false;
}

进栈操作

void pushStack(LiStack &L, int x){
	Linknode s;	//创建存储新元素的结点
	s = new Linknode;
 
	s->next = L;
	L = s;
}

出栈操作

bool popStack(LiStack &L, int &x){
	Linknode s;
	if(L = NULL)	//栈空不出栈
		return false;
 
	s = L;
	x = s->data;
	L = L->next;
	delete(s);
 
	return true;
}

3.1.4 本节习题精选

选择题：题目、答案

综合题：题目、答案

3.2 队列(Queue)

3.2.1 队列的基本概念

队列的基本概念.pdf

队列的定义

队列是操作受限的线性表，只允许在一端进行插入（入队），另一端进行删除（出队）
操作特性：先进先出 FIFO^[First In First Out，先进队列的元素先出队列]
相关术语
- 队头：允许删除的一端
- 队尾：允许插入的一端
- 空队列：不含任何元素的空表

队列的基本操作

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

3.2.2 队列的顺序存储结构

队列的顺序存储演示

队列的顺序实现.pdf

队头指针：指向队头元素；
队尾指针：指向队尾元素的后一个位置（下一个元素应该插入的位置）

\begin{document}
	\begin{tikzpicture}[scale=2,line width=1.5pt]
	\tikzstyle{every node}=[font=\huge,very thick,rectangle,minimum width=1cm, minimum height=1cm]
		% 队列结点
		\def\mystring{$q_{1}$,$q_{2}$,$q_{3}$,$q_{4}$,$q_{5}$,$q_{6}$}
		\foreach \char [count=\i] in \mystring {
			\node[draw=black,fill=gray!20] at (\i,0) (\i){\char};
		}
 
		\node [draw=black, dashed] at(7,0) (7){};
		\draw[-,line width=1pt] (0.5,0.6) -- (7.5,0.6);
		\draw[-,line width=1pt] (0.5,-0.6) -- (7.5,-0.6);
		\node at(0,1) (out) {output};
		\node at(8,1) (in) {input};
		\draw[-latex, line width=2pt] (in) -- (out);
		% 指针
		\node at(1,-1) (front){front};
		\node at(7,-1) (rear){rear};
		\draw[->] (front) -- (1);
		\draw[->] (rear) -- (7);
	\end{tikzpicture}
\end{document}

顺序队列的基本操作

定义

//队列的顺序存储类型
 define MaxSize 10;	//定义队列中元素的最大个数
typedef struct{
	ElemType data[MaxSize];	//用静态数组存放队列元素
	//连续的存储空间，大小为——MaxSize*sizeof(ElemType)
	int front, rear;	//队头指针和队尾指针
}SqQueue;

初始化

void InitQueue(SqQueue &Q){
	//初始化时，队头、队尾指针指向0
	//队尾指针是最后一个元素的下标+1
	Q.rear = Q.front = 0;
}
 
void test{
	SqQueue Q;	//声明一个队列
	InitQueue(Q);
	//...
}

入队

bool EnQueue(SqQueue $Q, ElemType x){
	if(队列已满)
		return false;	//队满则报错
	Q.data[Q.rear] = x;		//将x插入队尾
	Q.rear = Q.rear + 1;	//队尾指针后移
	/*
	Q.rear = (Q.rear+1)%MaxSize	//队尾指针+1取模（循环队列中使用）
	*/
	return true;
}

判空

bool QueueEmpty(SqQueue 0){
	if(Q.rear == Q.front)
		return true;
	else
		return false;
}

循环队列

LeetCode622. 设计循环队列

Q：能否用 Q.rear == MaxSize 作为队列满的条件？

A：不能！会有假溢出，所以需要用模运算将存储空间 {0,1,2,…,MaxSize} 在逻辑上变成“环状”——循环队列

初始：Q.front = Q.rear = 0;
队首指针进1：Q.front = (Q.front + 1) % MaxSize
队尾指针进1：Q.rear = (Q.rear + 1) % MaxSize —— 队尾指针后移，当移到最后一个后，下次移动会到第一个位置
队列元素个数： $(Q . r e a r + M a x S i z e - Q . f r o n t) % M a x S i z e$

循环队列判满

Q：能否用Q.rear == Q.front 作为队列满的条件？

A：不能！这已经作为队列空的判断条件了

方案一：牺牲一个单元来区分队空和队满

队尾指针的再下一个位置就是队头，即 (Q.rear+1)%MaxSize == Q.front（队尾指针是最后一个元素的下标+1）

\begin{document}
	\begin{tikzpicture}[scale=2,line width=1.5pt]
	\tikzstyle{every node}=[font=\huge,very thick,rectangle,minimum width=1cm, minimum height=1cm]
		\node[draw=black,fill=gray!20] at (1,0) (1){$q_{5}$};
		\node[draw=black,fill=gray!20] at (2,0) (2){$q_{6}$};
		\node[draw=black,dashed] at (3,0) (3){};
		\node[draw=black,fill=gray!20] at (4,0) (4){$q_{1}$};
		\node[draw=black,fill=gray!20] at (5,0) (5){$q_{2}$};
		\node[draw=black,fill=gray!20] at (6,0) (6){$q_{3}$};
		\node[draw=black,fill=gray!20] at (7,0) (7){$q_{4}$};
 
		\draw[-,line width=1pt] (0.5,0.6) -- (7.5,0.6);
		\draw[-,line width=1pt] (0.5,-0.6) -- (7.5,-0.6);
 
		\draw[-latex] (1) -- (0,0) -- (0,1) -- (8,1) -- (8,0) -- (7);
		\node at(4,-1) (front){front};
		\node at(3,-1) (rear){rear};
		\draw[->] (front) -- (4);
		\draw[->] (rear) -- (3);
	\end{tikzpicture}
\end{document}

循环队列获取元素个数：元素个数=(rear+MaxSize-front)%MaxSize
循环队列——入队：只能从队尾插入（判满使用方案一）

bool EnQueue(SqQueue &Q, ElemType x){
	if((Q.rear+1)%MaxSize == Q.front)	//队满
		return false;
	Q.data[Q.rear] = x;	//将x插入队尾
	Q.rear = (Q.rear + 1) % MaxSize;	//队尾指针加1取模
 
	return true;
}

循环队列——出队：只能让队头元素出队

//出队，删除一个队头元素，用x返回
bool DeQueue(SqQueue &Q, ElemType &x){
	if(Q.rear == Q.front)	//队空报错
		return false;
 
	x = Q.data[Q.front];
	Q.front = (Q.front + 1) % MaxSize;	//队头指针后移动
 
	return true;
}

循环队列——获得队头元素

bool GetHead(SqQueue &Q, ElemType &x){
	if(Q.rear == Q.front)	//队空报错
		return false;
	x = Q.data[Q.front];
	return true;
}

方案二：不牺牲存储空间，设置 size

定义一个变量 size用于记录队列此时记录了几个数据元素，初始化 size = 0，进队成功 size++，出队成功size--，根据 size 的值判断队满与队空

队满条件：size == MaxSize
队空条件：size == 0

 define MaxSize 10;
typedef struct{
	ElemType data[MaxSize];
	int front, rear;
	int size;	//队列当前长度
}SqQueue;
 
//初始化队列
void InitQueue(SqQueue &Q){
	Q.rear = Q.front = 0;
	size = 0;
}

方案三：不牺牲存储空间，设置 tag

定义一个变量 tag用来表示最近进行的操作

每次删除操作成功时，都令tag = 0；
每次插入操作成功时，都令tag = 1；

队满条件：Q.front == Q.rear && tag == 1（只有插入操作，才可能导致队满）

队空条件：Q.front == Q.rear && tag == 0（只有删除操作，才可能导致队空）

 define MaxSize 10;
typedef struct{
	ElemType data[MaxSize];
	int front, rear;
	int tag;	//最近进行的是删除or插入
}SqQueue;

其他出题方法——队尾指针指向队尾元素

判空(Q.rear + 1) % MaxSize == Q.front
判满
- 方案一：牺牲一个存储单元
- 方案二：增加辅助变量 size 或 tag
入队操作

Q.rear = (Q.rear + 1) % MaxSize; //后移一位
Q.data[Q.rear] = x;

3.2.3 队列的链式存储结构

队列的链式存储演示

队列的链式实现.pdf

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

\begin{document}
	\begin{tikzpicture}[scale=2,line width=1.5pt]
	\tikzstyle{every node}=[font=\huge,very thick,rectangle,minimum width=1cm, minimum height=1cm]
		% 队列结点
		\def\mystring{$q_{1}$,$q_{2}$,$q_{3}$,$q_{4}$,$q_{5}$,$q_{6}$}
		\foreach \char [count=\i] in \mystring {
			\node[draw=black,fill=gray!20] at (\i,0) (\i){\char};
		}
		\node [draw=black, dashed] at(7,0) (7){};
 
		\draw[-,line width=1pt] (0.5,0.6) -- (7.5,0.6);
		\draw[-,line width=1pt] (0.5,-0.6) -- (7.5,-0.6);
		\node at(0,1) (out) {output};
		\node at(8,1) (in) {input};
		\draw[-latex, line width=2pt] (in) -- (out);
		% 指针
		\node at(1,-1) (front){front};
		\node at(7,-1) (rear){rear};
		\draw[->] (front) -- (1);
		\draw[->] (rear) -- (7);
 
		%链式关系
		\draw[-latex, gray!50] (1) -- (2);
		\draw[-latex, gray!50] (2) -- (3);
		\draw[-latex, gray!50] (3) -- (4);
		\draw[-latex, gray!50] (4) -- (5);
		\draw[-latex, gray!50] (5) -- (6);
		\draw[-latex, gray!50, dashed] (6) -- (7);
	\end{tikzpicture}
\end{document}

链式队列的基本操作

判断队满

顺序存储：预分配存储空间
链式存储：一般不会队满，除非内存不足

链队长度：设置一个int length 记录链式队列长度，再遍历链队

带头结点链对的基本操作

初始化 & 判空

typedef struct LinkNode{//链式队列结点
	ElemType data;
	struct LinkNode *next;
}LinkNode;
 
typedef struct{//链式队列
	LinkNode * front, *rear;//队列的队头和队尾指针
}LinkQueue;
 
//初始化队列（带头结点）
void InitQueue(LinkQueue &Q){
	//初始化时，front、rear都指向头结点
	Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
	Q.front -> next = NULL;
}
 
//判断队列是否为空
bool IsEmpty(LinkQueue Q){
	if(Q.front == Q.rear)	//也可用 Q.front -> next == NULL
		return true;
	else
		return false;
}

入队操作

//新元素入队 (表尾进行)
void EnQueue(LinkQueue &Q, ElemType x){
	LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));	//申请一个新结点
	s->data = x;
	s->next = NULL;		//s作为最后一个结点，指针域指向NULL
	Q.rear->next = s;	//新结点插入到当前的rear之后
	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;
	Q.front->next = p->next;	//修改头结点的next指针
					//如果p是最后一个结点的话，p->next为NULL，所以这个关系也是正确的
	if(Q.rear == p)	//此次是最后一个结点出队
		Q.rear = Q.front;	//修改rear指针，释放后队列变为空队列
	free(p);	//释放结点空间
 
	return true;
}

不带头结点链对的基本操作

初始化 & 判空

void InitQueue(LinkQueue &Q){
	//初始化时，front、rear都指向NULL
	Q.front = NULL;
	Q.rear = NULL;
}
 
//判断队列是否为空
bool IsEmpty(LinkQueue Q){
	if(Q.front == NULL)	//也可以用 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(Q.front = NULL){	//在空队列中插入第一个元素，此时rear和front都指向NULL
		Q.front = s;	//修改队头队尾指针
		Q.rear = s;
	}else{
		Q.rear->next = s;	//新结点插入到rear结点之后
		Q.rear = s;	//修改rear指针指向新的表尾结点
	}
}

出队

//队头元素出队（表头进行）
bool DeQueue(LinkQueue &Q, ElemType &x){
	if(Q.front == NULL)
		return false;	//空队
 
	LinkNode *p = Q.front;	//p指针指向即将删除的结点
	x = p->data;
	Q.front = p->next;	//修改next指针
	if(Q.rear == p) {	//此次是最后一个结点出队
		Q.front = NULL;
		Q.rear = NULL;
	}
	free(p);	//释放结点空间
 
	return true;
}

3.2.4 双端队列

双端队列.pdf

双端队列定义

双端队列允许从两端插入、两端删除的线性表；
如果只使用其中一端的插入、删除操作，则等同于栈；
输入受限的双端队列：允许一端插入，两端删除的线性表；
输出受限的双端队列：允许两端插入，一端删除的线性表；

判断输出序列的合法性

例: 数据元素输入序列为 1,2,3,4，判断 $4! = 24$ 个输出序列的合法性

PS: 栈中合法的序列，双端队列中一定也合法

栈	输入受限的双端队列	输出受限的双端队列
14个合法(卡特兰数)	验证在栈中不合法的序列	验证在栈中不合法的序列
	只有 4213 和 4231 不合法	只有 4132 和 4231 不合法

3.2.5 本节习题精选

选择题：题目、答案

综合题：题目、答案

3.3 栈的应用

3.3.1 栈在括号匹配中的应用

LeetCode20. 有效的括号

栈在括号匹配中的应用.pdf

用栈实现括号匹配：( ( ( ) ) ) 最后出现的左括号最先被匹配（栈的特性—LIFO）；

实现思路：

初始时栈为空，从左往右遍历算术表达式中的各个括号
- 当遍历到左括号时，将其压入栈顶；
- 当遍历到右括号时，将栈顶的一个左括号弹出，并判断出栈的左括号是否与当前遍历到的右括号匹配
  - 如果栈空而没有左括号弹出，则匹配失败
  - 如果匹配，则继续遍历下一个括号
  - 如果不匹配，则匹配失败。
- 当遍历过所有的括号后
  - 若栈空，则匹配成功
  - 若干非空，则匹配失败

#define MaxSize 10
 
typedef struct{
	char data[MaxSize];	//静态数组存放栈中元素
	int top;
} SqStack;
 
//考试时可直接使用基本接口，但最好简要说明接口
//初始化栈
void InitStack(SqStack &S)
 
//判断栈是否为空
bool StackEmpty(SqStack &S)
 
//新元素入栈
bool Push(SqStack &S, char x)
 
//栈顶元素出栈，用x返回
bool Pop(SqStack &S, char &x)
 
 
bool bracketCheck(char str[], int length){
	SqStack S;	//声明
	InitStack(S);	//初始化栈
 
	for(int i=0; i<length; i++){
		if(str[i] == '(' || str[i] == '[' || str[i] == '{'){
			Push(S, str[i]);	//扫描到左括号，入栈
		}
		else{
			if(StackEmpty(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 StackEmpty(S);	//栈空说明匹配成功
}

3.3.2 栈在表达式求值中的应用

栈在表达式求值中的应用(上).pdf

栈在表达式求值中的应用(下).pdf

后缀表达式（逆波兰表达式）

LeetCode150. 逆波兰表达式求值

运算符在两个操作数后面

中缀表达式转后缀表达式-手算

确定中缀表达式中各个运算符的运算顺序
选择下一个运算符，按照[左操作数右操作数运算符]的方式组合成一个新的操作数
如果还有运算符没被处理，继续步骤2

\begin{document}
	\begin{tikzpicture}[scale=2,line width=1.5pt]
	\tikzstyle{every node}=[font=\huge,very thick,minimum width=1cm, minimum height=1cm]
		% 中缀表达式
		\def\infix{$A$, $+$, $B$, $-$, $C$, $\times$, $D$, $/$, $E$, $+$, $F$}
		\foreach \char [count=\i] in \infix {
			\node at (\i/2,0) {\char};
		}
		% 符号生效次序
		\foreach \idx [count=\i] in {1,4,2,3,5}{
			\node at(\i,-0.5) {\idx};
		}
		% 后缀表达式
		\def\postfix{$A$, $B$, $+$, $C$, $D$, $\times$, $E$, $/$, $-$, $F$, $+$}
		\foreach \char [count=\i] in \postfix {
			\node at (\i/2,-1) {\char};
		}
		% 符号生效次序
		\foreach \idx [count=\i] in {3,6,8,9,11} {
			\node at (\idx/2,-1.5) {\i};
		}
	\end{tikzpicture}
\end{document}

“左优先”原则：只要左边的运算符能先计算，就优先算左边的（保证运算顺序唯一），如左图所示；但客观来看左右两种方式都是正确的

\begin{document}
	\begin{tikzpicture}[scale=2,line width=1.5pt]
	\tikzstyle{every node}=[font=\huge,very thick,minimum width=1cm, minimum height=1cm]
		% 中缀表达式
		\def\infix{$A$, $+$, $B$, $\times$, $(C$, $-$, $D)$, $-$, $E$, $/$, $F$}
		\foreach \char [count=\i] in \infix {
			\node at (\i/2,0) {\char};
		}
		% 符号生效次序
		\foreach \idx [count=\i] in {3,2,1,5,4}{
			\node at(\i,-0.5) {\idx};
		}
		% 后缀表达式
		\def\postfix{$A$, $B$, $C$, $D$, $-$, $\times$, $+$, $E$, $F$, $/$, $-$}
		\foreach \char [count=\i] in \postfix {
			\node at (\i/2,-1) {\char};
		}
		% 符号生效次序
		\foreach \idx [count=\i] in {5,6,7,10,11} {
			\node at (\idx/2,-1.5) {\i};
		}
	\end{tikzpicture}
\hspace{5em}
	\begin{tikzpicture}[scale=2,line width=1.5pt]
	\tikzstyle{every node}=[font=\huge,very thick,minimum width=1cm, minimum height=1cm]
		% 中缀表达式
		\def\infix{$A$, $+$, $B$, $\times$, $(C$, $-$, $D)$, $-$, $E$, $/$, $F$}
		\foreach \char [count=\i] in \infix {
			\node at (\i/2,0) {\char};
		}
		% 符号生效次序
		\foreach \idx [count=\i] in {5,3,2,4,1}{
			\node at(\i,-0.5) {\idx};
		}
		% 后缀表达式
		\def\postfix{$A$, $B$, $C$, $D$, $-$, $\times$, $+$, $E$, $F$, $/$, $-$}
		\foreach \char [count=\i] in \postfix {
			\node at (\i/2,-1) {\char};
		}
		% 符号生效次序
		\node at (5/2,-1.5) {2};
		\node at (6/2,-1.5) {3};
		\node at (9/2,-1.5) {1};
		\node at (10/2,-1.5) {4};
		\node at (11/2,-1.5) {5};
	\end{tikzpicture}
\end{document}

中缀表达式转后缀表达式-机算

栈用于保存暂时还不能确定运算顺序的运算符考前记一记

从左到右处理各个元素，直到末尾。
- 遇到操作数：直接加入后缀表达式；
- 遇到界限符：遇到 '(' 直接入栈；遇到 ')' 则依次弹出栈内运算符并加入后缀表达式，直到弹出 '(' 为止。注意：'(' 不加入后缀表达式；
- 遇到运算符：依次弹出栈中优先级高于或等于当前运算符的所有运算符 ^[提示： $\times$ ÷ 高于 $+$ $-$ ]，并加入后缀表达式，若碰到 '(' 或栈空则停止。之后再把当前运算符入栈。
按上述方法处理完所有字符后，将栈中剩余运算符依次弹出，并加入后缀表达式。

后缀表达式求值-手算

从左往右扫描，每遇到一个运算符，就让运算符前面最近的两个操作数执行对应的运算，合体为一个操作数

注意：两个操作数的左右顺序

后缀表达式求值-机算

栈用于存放当前暂时不能确定运算次序的操作数考前记一记

从左往右扫描下一个元素，直到处理完所有元素
- 若扫描到操作数，则压入栈；
- 若扫描到运算符，则弹出两个栈顶元素，执行相应的运算，运算结果压回栈顶；
若表达式合法，则最后栈中只会留下一个元素，就是最终结果

注意：先出栈的是“右操作数”（先出栈的原本在栈的右边/上面）

前缀表达式（波兰表达式）

运算符在两个操作数前面

中缀表达式转前缀表达式-手算

确定中缀表达式中各个运算符的运算顺序
选择下一个运算符，按照[运算符左操作数右操作数]的方式组合成一个新的操作数
如果还有运算符没被处理，就继续执行步骤2

“右优先”原则：只要右边的运算符能先计算，就优先算右边的（保证运算顺序唯一），如左图所示；但客观来看左右两种方式都是正确的

\begin{document}
	\begin{tikzpicture}[scale=2,line width=1.5pt]
	\tikzstyle{every node}=[font=\huge,very thick,minimum width=1cm, minimum height=1cm]
		% 中缀表达式
		\def\infix{$A$, $+$, $B$, $\times$, $(C$, $-$, $D)$, $-$, $E$, $/$, $F$}
		\foreach \char [count=\i] in \infix {
			\node at (\i/2,0) {\char};
		}
		% 符号生效次序
		\foreach \idx [count=\i] in {5,3,2,4,1}{
			\node at(\i,-0.5) {\idx};
		}
		% 前缀表达式
		\def\prefix{$+$, $A$, $-$, $\times$, $B$, $-$, $C$, $D$, $/$, $E$, $F$}
		\foreach \char [count=\i] in \prefix {
			\node at (\i/2,-1) {\char};
		}
		% 符号生效次序
		\foreach \idx [count=\i] in {1,3,4,6,9} {
			\pgfmathtruncatemacro{\result}{6-\i};
			\node at (\idx/2,-1.5) {\result};
		}
	\end{tikzpicture}
\hspace{5em}
	\begin{tikzpicture}[scale=2,line width=1.5pt]
	\tikzstyle{every node}=[font=\huge,very thick,minimum width=1cm, minimum height=1cm]
		% 中缀表达式
		\def\infix{$A$, $+$, $B$, $\times$, $(C$, $-$, $D)$, $-$, $E$, $/$, $F$}
		\foreach \char [count=\i] in \infix {
			\node at (\i/2,0) {\char};
		}
		% 符号生效次序
		\foreach \idx [count=\i] in {3,2,1,5,4}{
			\node at(\i,-0.5) {\idx};
		}
		% 前缀表达式
		\def\prefix{$-$, $+$, $A$, $\times$, $B$, $-$, $C$, $D$, $/$, $E$, $F$}
		\foreach \char [count=\i] in \prefix {
			\node at (\i/2,-1) {\char};
		}
		% 符号生效次序
		\node at (1/2,-1.5) {5};
		\node at (2/2,-1.5) {3};
		\node at (4/2,-1.5) {2};
		\node at (6/2,-1.5) {1};
		\node at (9/2,-1.5) {4};
	\end{tikzpicture}
\end{document}

前缀表达式求值-机算

用栈实现前缀表达式的计算

从右往左扫描下一个元素，直到处理完所有元素；
若扫描到操作数则压入栈；
若扫描到运算符，则弹出两个栈顶元素，执行相应运算，运算结果压回栈顶；

注意：先出栈的是“左操作数”

中缀表达式（需要界限符）

由三个部分组成：操作数、运算符、界限符组成。
运算符在两个操作数中间：

 a + b
 a + b - c
 a + b - c*d
((15 ÷ (7-(1+1)))×3)-(2+(1+1))

中缀表达式求值-机算

LeetCode面试题 16.26. 计算器

LeetCode227. 基本计算器 II

LeetCode772. 基本计算器 III

两个算法的结合：中缀转后缀+ 后缀表达式的求值，二者都是从左往右的扫描

初始化两个栈，运算符栈和操作数栈
从左往右扫描中缀表达式，若扫描到操作数，压入操作数栈
若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈（期间也会弹出运算符，每当弹出一个运算符时

3.3.3 栈在递归中的应用

栈在递归中的应用.pdf

函数调用的特点：最后被调用的函数最先执行结束（LIFO[

函数调用时，需要用一个栈存储：

调用返回地址：返回到上一层递归的该地址处，继续执行此层递归在该地址之后的代码
实参：递归返回值
局部变量：递归所需参数

递归算法特点：可以把原始问题转换为属性相同，但规模较小的问题，如：求阶乘、斐波那契数列

LeetCode509. 斐波那契数

递归调用时，函数调用栈称为 “递归工作栈”：

每进入一层递归，就将递归调用所需信息压入栈顶；
每退出一层递归，就从栈顶弹出相应信息；

缺点：效率低，太多层递归可能回导致栈溢出；可能包含很多次重复计算

3.3 队列的应用

队列的应用.pdf

3.3.1 树的层次遍历

详见树的层序遍历

3.3.2 图的广度优先遍历

详见广度优先遍历BFS

3.3.3 队列在操作系统中的应用

CPU资源分配，先来先服务(FCFS)中采用就绪进程队列
打印数据缓冲区，SPOOLing技术中采用缓冲区队列

3.3.6 本节习题精选

选择题：题目、答案

题号	笔记
1	进制置换和迷宫求解也是栈的典型应用
2
3
4
5
6
7
8
9
10
11
12
13

综合题：题目、答案

题号	笔记
1
2
3
4

3.4 特殊矩阵的压缩存储

特殊矩阵的压缩存储.pdf

3.4.1 数组的存储结构

一维数组
- 各数组元素大小相同，物理上连续存放；
- 起始地址：LOC
- 数组下标：默认从0开始！
- 数组元素 a[i] 的存放地址 = LOC + i × sizeof(ElemType)

Elemtype a[10];		//ElemType型一维数组

二维数组
- 起始地址：LOC
- $M$ 行 $N$ 列的二维数组 b[M][N] 中，b[i][j]的存储地址：
  - 行优先存储：LOC + (i×N + j) × sizeof(ElemType)
  - 列优先存储：LOC + (j×M + i) × sizeof(ElemType)
- 行优先/列优先存储优点：实现随机存储

Elemtype b[2][4]; 	//2行4列的二维数组

\begin{document}
	\begin{tikzpicture}[scale=2, line width=1.5pt,
	every node/.style={draw=black, rectangle, very thick, font =\huge, rectangle, minimum width=6em, minimum height=3em},
	]
		\foreach \i in {0,1}{
			\foreach \j in {0,1,2,3}{
				\ifnum\i=1
					\node[fill=blue!20] at(\j*2,-\i) {b[\i][\j]};
				\else
					\node[fill=green!20] at(\j*2,-\i) {b[\i][\j]};
				\fi
			}
		}
	\end{tikzpicture}
\end{document}

行优先存储：

\begin{document}
	\begin{tikzpicture}[scale=2, line width=1.5pt,
	every node/.style={draw=black, rectangle, very thick, font =\huge, rectangle, minimum width=6em, minimum height=3em},
	]
		\foreach \i in {0,1}{
			\foreach \j in {0,1,2,3}{
			\ifnum\i=1
				\node[fill=blue!20] at(\i*8+\j*2,0){b[\i][\j]};
			\else
				\node[fill=green!20] at(\i*8+\j*2,0){b[\i][\j]};
			\fi
			}
		}
	\end{tikzpicture}
\end{document}

列优先存储：

\begin{document}
	\begin{tikzpicture}[scale=2, line width=1.5pt,
	every node/.style={draw=black, rectangle, very thick, font =\huge, rectangle, minimum width=6em, minimum height=3em},
	]
		%\idx=1
		\foreach \i in {0,1}{
			\foreach \j in {0,1,2,3}{
				\ifnum\i=1
					\node[fill=blue!20] at(\i*2+\j*4,0) {b[\i][\j]};
				\else
					\node[fill=green!20] at(\i*2+\j*4,0) {b[\i][\j]};
				\fi
			}
		}
	\end{tikzpicture}
\end{document}

3.4.2 普通矩阵的存储

可用二维数组存储

描述矩阵元素时，行、列号通常从1开始；
描述数组时，通常下标从 0 开始；

3.4.3 特殊矩阵的存储

特殊矩阵——压缩存储空间

对称矩阵

对称矩阵（方阵）， $a_{ij} = a_{j i}$

只存储主对角线和下（上）三角区的数据
可以使用一维数组存储各个元素，数组大小为 $1 + 2 + \dots + n = \frac{n ( n + 1 )}{2}$
映射函数：矩阵下标→一维数组下标，
- 当以行优先存储主对角线和下三角区数据时
  - 若 $i ⩾ j$ ，则 $a_{ij}$ 对应一维数组下标 $k_{ij} = [1 + 2 + \dots + (i - 1)] + j - 1 = \frac{i ( i - 1 )}{2} + j - 1$
  - 若 $i < j$ ，则 $a_{ij}$ 对应一维数组下标 $k_{ij} = k_{j i}$
- 当以列优先存储主对角线和下三角区数据时
  - 若 $i ⩾ j$ ，则 $a_{ij}$ 对应一维数组下标 $k_{ij} = [n + (n - 1) + \dots + (n - j + 2)] + i - 1 = \frac{( 2 n - j + 2 ) ( j - 1 )}{2} + i - 1$
  - 若 $i < j$ ，则 $a_{ij}$ 对应一维数组下标 $k_{ij} = k_{j i}$

a_{1, 1} a_{2, 1} a_{3, 1} ⋮ a_{n - 1, 1} a_{n, 1} a_{1, 2} a_{2, 2} a_{3, 2} ⋮ a_{n - 1, 2} a_{n, 2} a_{1, 3} a_{2, 3} a_{3, 3} ⋮ a_{n - 1, 3} a_{n, 3} \dots \dots \dots \dots \dots a_{1, n - 1} a_{2, n - 1} a_{3, n - 1} ⋮ a_{n - 1, n - 1} a_{n, n - 1} a_{1, n} a_{2, n} a_{3, n} ⋮ a_{n - 1, n} a_{n, n}

Example

例：以存储对称矩阵主对角线和下三角区数据为例，行优先存储和列优先存储如下所示

 

\begin{document}

\def\myMatrix{{

{0,5,3,3,4},

{5,0,2,6,7},

{3,2,0,8,9},

{3,6,8,0,6},

{4,7,9,6,0}

}}

\begin{tikzpicture}[scale=1, ultra thick,

every node/.style={font=\huge, draw=black, very thick, rectangle, minimum width=1cm, minimum height=1cm},

]

\def\rowfirst{0};

\foreach \row in {0,1,2,3,4} {

  \foreach \col in {0,1,2,3,4} {

  	\pgfmathtruncatemacro{\value}{\myMatrix[\row][\col]};

  		\ifnum\row=\col

  			\node[fill=blue!20] at (\col, -\row) {\value};

  			\node[fill=blue!20] at (\rowfirst+8, -1) {\value};

  			\xdef\rowfirst{\rowfirst+1};

  		\else

  			\ifnum\row>\col

  				\node[fill=green!20] at (\col, -\row) {\value};

  				\node[fill=green!20] at (\rowfirst+8, -1) {\value};

  				\xdef\rowfirst{\rowfirst+1};

  			\else

  				\node at (\col, -\row) {\value};

\fi

\fi

}

\def\colfirst{0};

\foreach \col in {0,1,2,3,4} {

  \foreach \row in {0,1,2,3,4} {

  	\pgfmathtruncatemacro{\value}{\myMatrix[\row][\col]};

  		\ifnum\row=\col

  			\node[fill=blue!20] at (\colfirst+8, -3) {\value};

  			\xdef\colfirst{\colfirst+1};

  		\else

  			\ifnum\row>\col

  				\node[fill=green!20] at (\colfirst+8, -3) {\value};

  				\xdef\colfirst{\colfirst+1};

  			\else

\fi

\fi

}

% 序号

\foreach \i in{1,2,3,4,5}{

  \node[draw=none, font=\Large] at (\i-1, 1) {\i};

  \node[draw=none, font=\Large] at (-1, -\i+1) {\i};

}

\foreach \i in{0,1,…,14}{

  \node[draw=none, font=\Large] at(\i+8, -2){\i};

  \node[draw=none, font=\Large] at(\i+8, -4){\i};

}

\end{tikzpicture}

\end{document}

三角矩阵

三角矩阵（方阵）：除了主对角线和下（上）三角区，其余元素都相同

重点存储主对角线和下（上）三角区的数据，并在最后一个位置存储常量 $c$
映射函数：矩阵下标→一维数组下标，
- 当以行优先存储主对角线和下三角区数据时
  - 若 $i ⩾ j$ ，则 $a_{ij}$ 对应一维数组下标 $k_{ij} = [1 + 2 + \dots + (i - 1)] + j - 1 = \frac{i ( i - 1 )}{2} + j - 1$
  - 若 $i < j$ ，则 $a_{ij}$ 对应一维数组下标 $k_{ij} = \frac{n ( n + 1 )}{2}$
- 当以列优先存储主对角线和下三角区数据时
  - 若 $i ⩾ j$ ，则 $a_{ij}$ 对应一维数组下标 $k_{ij} = [n + (n - 1) + \dots + (n - j + 2)] + i - 1 = \frac{( 2 n - j + 2 ) ( j - 1 )}{2} + i - 1$
  - 若 $i < j$ ，则 $a_{ij}$ 对应一维数组下标 $k_{ij} = \frac{n ( n + 1 )}{2}$

a_{1, 1} a_{2, 1} a_{3, 1} ⋮ a_{n - 1, 1} a_{n, 1} c a_{2, 2} a_{3, 2} ⋮ a_{n - 1, 2} a_{n, 2} c c a_{3, 3} ⋮ a_{n - 1, 3} a_{n, 3} \dots \dots \dots \dots \dots c c c ⋮ a_{n - 1, n - 1} a_{n, n - 1} c c c ⋮ c a_{n, n}

Example

例：以 $c = 0$ 为例，行优先存储和列优先存储如下所示

 

\begin{document}

\def\myMatrix{{

{1,0,0,0,0},

{5,1,0,0,0},

{3,2,1,0,0},

{3,6,8,1,0},

{4,7,9,6,1}

}}

\begin{tikzpicture}[scale=1, ultra thick,

every node/.style={font=\huge, draw=black, very thick, rectangle, minimum width=1cm, minimum height=1cm},

]

\def\rowfirst{0};

\foreach \row in {0,1,2,3,4} {

  \foreach \col in {0,1,2,3,4} {

  	\pgfmathtruncatemacro{\value}{\myMatrix[\row][\col]};

  		\ifnum\row=\col

  			\node[fill=blue!20] at (\col, -\row) {\value};

  			\node[fill=blue!20] at (\rowfirst+8, -1) {\value};

  			\xdef\rowfirst{\rowfirst+1};

  		\else

  			\ifnum\row>\col

  				\node[fill=green!20] at (\col, -\row) {\value};

  				\node[fill=green!20] at (\rowfirst+8, -1) {\value};

  				\xdef\rowfirst{\rowfirst+1};

  			\else

  				\node at (\col, -\row) {\value};

\fi

\fi

}

\def\colfirst{0};

\foreach \col in {0,1,2,3,4} {

  \foreach \row in {0,1,2,3,4} {

  	\pgfmathtruncatemacro{\value}{\myMatrix[\row][\col]};

  		\ifnum\row=\col

  			\node[fill=blue!20] at (\colfirst+8, -3) {\value};

  			\xdef\colfirst{\colfirst+1};

  		\else

  			\ifnum\row>\col

  				\node[fill=green!20] at (\colfirst+8, -3) {\value};

  				\xdef\colfirst{\colfirst+1};

  			\else

\fi

\fi

}

% 存储常量c

\node at(23,-1) {0};

\node at(23,-3) {0};

% 序号

\foreach \i in{1,2,3,4,5}{

  \node[draw=none, font=\Large] at (\i-1, 1) {\i};

  \node[draw=none, font=\Large] at (-1, -\i+1) {\i};

}

\foreach \i in{0,1,…,15}{

  \node[draw=none, font=\Large] at(\i+8, -2){\i};

  \node[draw=none, font=\Large] at(\i+8, -4){\i};

}

\end{tikzpicture}

\end{document}

三对角矩阵

三对角矩阵(方阵)：当 $∣ i - j ∣ > 1$ 时，有 $a_{ij} = 0$ ，即只需存储主对角线以及上下左右相邻元素

* 第一行和最后一行两个元素，其余三个元素，共 $3n-2$ 个元素

a_{1, 1} a_{2, 1} 0 ⋮ 00 a_{1, 2} a_{2, 2} a_{3, 2} ⋮ 00 0 a_{2, 3} a_{3, 3} ⋮ 00 \dots \dots \dots \dots \dots 000 ⋮ a_{n - 1, n - 1} a_{n, n - 1} 000 ⋮ a_{n - 1, n} a_{n, n}

稀疏矩阵

稀疏矩阵：非零元素远远少于矩阵元素的个数

顺序存储——三元组<行，列，值>
链式存储——十字链表法
- 向下域 down：指针指向第 $j$ 列的各个元素
- 向右域 right：指针指向第 $i$ 行的各个元素

0000003020400000900000700

3.4.4 本节习题精选

选择题：题目、答案

我的 Obsidian 知识库

探索

第3章 栈和队列

3.1 栈(stack)

3.1.1 栈的基本概念

栈的定义

栈的基本操作

栈的常见题型

3.1.2 栈的顺序存储

顺序栈的基本操作

共享栈

3.1.3 栈的链式存储结构

用链式存储方式实现的栈

链栈的基本操作

带头结点链栈的基本操作

不带头结点链栈的基本操作

3.1.4 本节习题精选

3.2 队列(Queue)

3.2.1 队列的基本概念

队列的定义

队列的基本操作

3.2.2 队列的顺序存储结构

顺序队列的基本操作

循环队列

循环队列判满

3.2.3 队列的链式存储结构

链式队列的基本操作

带头结点链对的基本操作

不带头结点链对的基本操作

3.2.4 双端队列

双端队列定义

判断输出序列的合法性

3.2.5 本节习题精选

3.3 栈的应用

3.3.1 栈在括号匹配中的应用

3.3.2 栈在表达式求值中的应用

后缀表达式（逆波兰表达式）

中缀表达式转后缀表达式-手算

中缀表达式转后缀表达式-机算

后缀表达式求值-手算

后缀表达式求值-机算

前缀表达式 （波兰表达式）

中缀表达式转前缀表达式-手算

前缀表达式求值-机算

中缀表达式（需要界限符）

中缀表达式求值-机算

3.3.3 栈在递归中的应用

3.3 队列的应用

3.3.1 树的层次遍历

3.3.2 图的广度优先遍历

3.3.3 队列在操作系统中的应用

3.3.6 本节习题精选

3.4 特殊矩阵的压缩存储

3.4.1 数组的存储结构

3.4.2 普通矩阵的存储

3.4.3 特殊矩阵的存储

对称矩阵

三角矩阵

三对角矩阵

稀疏矩阵

3.4.4 本节习题精选

关系图谱

目录

反向链接

第3章栈和队列

前缀表达式（波兰表达式）