数据结构（二）——栈与队列与数组

1. 栈

1.1 栈的定义

栈（stack）是只允许在一端进行插入或删除操作的线性表。

栈的特点：后进先出

栈的相关术语：

  1. 栈顶（Top）：线性表允许进行插入删除的那一端。
  2. 栈底（Bottom）：固定的，不允许进行插入和删除的另一端。
  3. 空栈。不含任何元素的空表。
数据结构（二）——栈与队列与数组——栈的定义.png

栈的数学性质：当n个不同元素进栈时，出栈元素不同排列的个数为下述表达式：
$$
\frac{1}{n+1}{C_{2n}^n}
$$
这个公式称为卡特兰数公式，可采用数学归纳法证明。

1.2 顺序栈的实现

1.2.1 顺序栈的定义

1
2
3
4
5
6
7
8
9
10
11
#define MaxSize 10           //定义栈中元素最大个数 

typedef struct {
	ElemType data[MaxSize];  //静态数组存放栈中元素
	int top;				 //栈顶指针
}SqStack;

int main()
{
	SqStack S;				//声明一个顺序栈（分配空间）
}

1.2.2 初始化操作

1
2
3
4
//初始化栈
void InitStack(SqStack& S) {
	S.top = -1;				 //初始化栈顶指针
}

这里进行初始化，将栈顶指针设置为-1，则之后进行入栈操作时，将会先移动栈顶指针再进行入栈操作；进行出栈操作时，会先将数据取出，再移动栈顶指针。但是题目可能会出现S.Top=0，这个时候的入栈出栈操作就会变的不一样，需要具体问题具体分析。

1.2.3 栈空、栈满判断

栈空判断：判断栈顶指针是否为-1，如果是的，说明栈空返回true；如果不是，说明栈非空，返还false。

1
2
3
4
5
6
7
//栈空判断
bool StackEmpty(SqStack S) {
	if (S.top == -1)		//栈空，返回true
		return true;
    else
        return false;
}

栈满判断：判断栈顶指针指向的下标，是否是栈的最大长度减1，如果是，说明栈已经装满，返回true；反之返回false。

1
2
3
4
5
6
7
//栈满判断
bool StackFull(SqStack S) {
	if (S.top == MaxSize - 1)	//栈满，返回true
		return true;
    else 
        return false;
}

1.2.4 栈顶元素读取

1
2
3
4
5
6
7
//栈顶元素读取
bool GetTop(SqStack S, ElemType& x) {
	if (true == StackEmpty(S)) //判断栈空，StackEmpty为栈空函数，参考1.2.3
		return false;
	x = S.data[S.top];		   //读取栈顶元素
	return true;
}

1.2.5 入栈操作

入栈操作，需要先进行栈满判断，如果栈满要返还false信息。又因为前面进行初始化时，设置栈顶指针为-1，所以这里需要先将栈顶指针上移，再进行元素入栈。入栈成功，返还true。

1
2
3
4
5
6
7
8
9
//入栈操作
bool Push(SqStack& S, ElemType x) {
	if (true == StackFull(S)) //判断栈满，StackFull为栈满函数，参考1.2.3
		return false;
	S.top += 1;				  //指针先加1
	S.data[S.top] = x;		  //新元素入栈
	//入栈操作还可以写成S.data[++S.top]=x;
	return true;
}

1.2.6 出栈操作

出栈操作，需要先进行栈空判断，如果栈空，则返还false信息。若栈不为空，则先让栈顶元素出栈，再进行指针减1操作。出栈成功，返还true。

1
2
3
4
5
6
7
8
//出栈操作
bool Pop(SqStack& S, ElemType& x) {
	if (true == StackEmpty(S)) //判断栈空，StackEmpty为栈空函数，参考1.2.3
		return false;
	x = S.data[S.top];		   //栈顶元素先出栈
	S.top--;				   //指针减1
	return true;
}

1.2.7 S.top=0

如果栈顶指针初始化时指向0，那么在进行入栈，出栈操作时，就与栈顶指针指向-1产生了区别。

S.top=0，在进行入栈时，需要先进行入栈操作，再将栈顶指针上移。

1
2
S.data[S.top]=x;
S.top++;

S.top=0，在进行出栈时，需要先进行指针下移操作，再将栈顶元素出栈。

1
2
S.top--;
x=S.data[S.top];

1.2.8 共享栈（两个栈共享同一片空间）

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

数据结构（二）——栈与队列与数组——共享栈.png

1.2.9 顺序栈小结

数据结构（二）——栈与队列与数组——顺序栈小结.png 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
//顺序栈的C语言框架，要根据项目具体要求进行修改。
#include<stdio.h>
#define MaxSize 10           //定义栈中元素最大个数 
//ElemType并不是一个数据类型，而是伪代码中所有数据类型的代指
//ElemType可以是int，也可以是float，但项目中更多的是struct结构体类型
//这份程序做示范所以将ElemType定义为int类型 
//实际项目中ElemType究竟是什么类型要根据具体项目情况
#define ElemType int		 

//栈类型定义
typedef struct {
	ElemType data[MaxSize];  //静态数组存放栈中元素
	int top;				 //栈顶指针
}SqStack;

//初始化栈
void InitStack(SqStack& S) {
	S.top = -1;				 //初始化栈顶指针
}

//栈空判断
bool StackEmpty(SqStack S) {
	if (S.top == -1)		//栈空，返回true
		return true;
	else
		return false;
}

//栈满判断
bool StackFull(SqStack S) {
	if (S.top == MaxSize - 1)	//栈满，返回true
		return true;
	else
		return false;
}

//入栈操作
bool Push(SqStack& S, ElemType x) {
	if (true == StackFull(S)) //判断栈满，StackFull为栈满函数，参考1.2.3
		return false;
	S.top += 1;				  //指针先加1
	S.data[S.top] = x;		  //新元素入栈
	//入栈操作还可以写成S.data[++S.top]=x;
	return true;
}

//出栈操作
bool Pop(SqStack& S, ElemType& x) {
	if (true == StackEmpty(S)) //判断栈空，StackEmpty为栈空函数，参考1.2.3
		return false;
	x = S.data[S.top];		   //栈顶元素先出栈
	S.top--;				   //指针减1
	return true;
}

//栈顶元素读取
bool GetTop(SqStack S, ElemType& x) {
	if (true == StackEmpty(S)) //判断栈空，StackEmpty为栈空函数，参考1.2.3
		return false;
	x = S.data[S.top];		   //读取栈顶元素
	return true;
}

int main()
{
	SqStack S;					  //声明一个顺序栈（分配空间）
	ElemType a = 1, b = 2, c = 3; //a为入栈数，b为栈顶元素读取存放，c为出栈数
	InitStack(S);				  //初始化栈
	Push(S, a);					  //入栈
	GetTop(S, b);				  //获取栈顶元素
	Pop(S, c);					  //出栈
}

1.3 链栈

在前面我们有提过，栈就是表的一种特殊结构，链栈就是只允许在表头进行插入和删除操作的链表。所以链栈和链表一样，可以分为带头结点的和不带头结点的。

不过与链表不同的是，我们在进行链表操作时，推荐使用带头结点的链表，这样更方便我们进行插入删除等操作。

但在栈的数据结构中，我们更推荐用不带头结点的方式进行实现，因为在进行链栈的出入栈过程中，我们是在表头进行。虽然表面上是在表头进行，但在这里我们可以把表头理解为栈顶，在这种情况下，如果不带头结点，那么我们每次入栈操作只需要在栈顶插入一个新元素，并令头结点指向新元素即可；出栈同理，先取出栈头元素，再令头指针向后移动一位即可；都是非常标准的出入栈操作。

如果我们使用了带头结点的方式，那每次的入栈和出栈操作，就是非常标准的在带头结点的链表中，对第一位进行数据插入和删除操作。

数据结构（二）——栈与队列与数组——链栈的结构.png

1.3.1 链栈的实现

1
2
3
4
5
6
7
8
9
10
//定义栈的结点
typedef struct LinkNode
{
	ElemType data;			//数据域
	struct LinkNode* next;	//指针域
}LiStack;					//栈类型结构

int main() {
	LiStack S;				//定义一个栈
}

1.3.2 链栈的初始化

不带头结点的链栈初始化：

1
2
3
4
5
//不带头结点的链栈的初始化
bool InitStackWithoutHeader(LiStack& S) {
	S = NULL; // 栈顶指针初始化为NULL 
	return true;
}

带头结点的链栈初始化：

1
2
3
4
5
6
7
8
9
//带头结点的链栈的初始化
bool InitStackWithHeader(LiStack& S)
{
	//创建头结点
	S = (LinkNode*)malloc(sizeof(LinkNode));
	//头结点之后暂时还没有元素结点
	S->next = NULL;
	return true;
}

1.3.3 链栈的入栈操作

不带头结点的链栈入栈操作：

1
2
3
4
5
6
7
8
9
10
11
12
// 入栈操作函数  
bool Push(LiStack& S, ElemType e) {  
    // 分配新结点  
    LinkNode* newNode = (LinkNode*)malloc(sizeof(LinkNode));  
    if (newNode == NULL) {  
        return false; // 分配失败  
    }  
    newNode->data = e;    // 将元素值赋给新结点  
    newNode->next = S;    // 新结点的next指向原栈顶  
    S = newNode;          // 修改栈顶指针  
    return true;  
}

带头结点的链栈入栈操作：

1
2
3
4
5
6
7
8
9
10
11
12
// 带头结点的链栈的入栈操作  
bool PushWithHeader(LiStack& S, ElemType e) {  
    // 分配新结点  
    LinkNode* newNode = (LinkNode*)malloc(sizeof(LinkNode));  
    if (newNode == NULL) {  
        return false; // 分配失败  
    }  
    newNode->data = e;               // 将元素值赋给新结点  
    newNode->next = S->next;        // 新结点的next指向原栈顶结点  
    S->next = newNode;               // 头结点的next指向新结点，完成入栈  
    return true;  
}

1.3.4 链栈的出栈操作

不带头结点的出栈操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 不带头结点的链栈的出栈操作  
bool PopWithoutHeader(LiStack& S, ElemType& e) {  
    // 如果栈为空，则无法出栈  
    if (S == NULL) {  
        return false;  
    }  
      
    // 获取栈顶元素的值  
    e = S->data;  
      
    // 将栈顶指针指向下一个结点，实现出栈  
    LinkNode* temp = S;  
    S = S->next;  
      
    // 释放原栈顶结点的内存  
    free(temp);  
      
    return true;  
}

带头结点的出栈操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 带头结点的链栈的出栈操作  
bool PopWithHeader(LiStack& S, ElemType& e) {  
    // 检查栈是否为空  
    if (S->next == NULL) {  
        return false; // 栈空，无法出栈  
    }  
      
    // 获取栈顶元素的值  
    LinkNode* top = S->next;  
    e = top->data;  
      
    // 删除栈顶元素  
    S->next = top->next;  
      
    // 释放原栈顶结点的内存  
    free(top);  
      
    return true;  
}

1.3.5 链栈小结

数据结构（二）——栈与队列与数组——链栈小结.png 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
//链栈的代码框架，包含带头结点和不带头结点，按需删除更改
#include<stdio.h>
#include<stdlib.h>
#define ElemType int 

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

//不带头结点的链栈的初始化
bool InitStackWithoutHeader(LiStack& S) {
	S = NULL; // 栈顶指针初始化为NULL 
	return true;
}

//带头结点的链栈的初始化
bool InitStackWithHeader(LiStack& S)
{
	//创建头结点
	S = (LinkNode*)malloc(sizeof(LinkNode));
	//头结点之后暂时还没有元素结点
	S->next = NULL;
	return true;
}

// 入栈操作函数  
bool Push(LiStack& S, ElemType e) {
	// 分配新结点  
	LinkNode* newNode = (LinkNode*)malloc(sizeof(LinkNode));
	if (newNode == NULL) {
		return false; // 分配失败  
	}
	newNode->data = e;    // 将元素值赋给新结点  
	newNode->next = S;    // 新结点的next指向原栈顶  
	S = newNode;          // 修改栈顶指针  
	return true;
}

// 不带头结点的链栈的出栈操作  
bool PopWithoutHeader(LiStack& S, ElemType& e) {
	// 如果栈为空，则无法出栈  
	if (S == NULL) {
		return false;
	}

	// 获取栈顶元素的值  
	e = S->data;

	// 将栈顶指针指向下一个结点，实现出栈  
	LinkNode* temp = S;
	S = S->next;

	// 释放原栈顶结点的内存  
	free(temp);

	return true;
}

// 带头结点的链栈的出栈操作  
bool PopWithHeader(LiStack& S, ElemType& e) {
	// 检查栈是否为空  
	if (S->next == NULL) {
		return false; // 栈空，无法出栈  
	}

	// 获取栈顶元素的值  
	LinkNode* top = S->next;
	e = top->data;

	// 删除栈顶元素  
	S->next = top->next;

	// 释放原栈顶结点的内存  
	free(top);

	return true;
}

int main() {
	LiStack S;				//定义一个栈
	ElemType e = 1;
	InitStackWithoutHeader(S);
	Push(S, e);
	PopWithoutHeader(S, e);
}

2. 队列

2.1 队列的定义

队列同栈一样，也是一个操作受限的线性表。队列是只允许在一端进行插入，在另一端删除的线性表。

队列的特点：先进先出

队列的相关术语：

  1. 队头（Front）：允许删除的一端，又称队首。
  2. 队尾（Rear）：允许插入的一端。
  3. 空队列：不含任何元素的空表。
数据结构（二）——栈与队列与数组——队列的定义.png

2.2 队列的顺序实现

2.2.1 队列存储类型定义

1
2
3
4
5
6
7
8
9
10
//队列存储类型的描述
typedef struct {
	ElemType data[MaxSize];	//用静态数组存放队列元素
	int front, rear;		//队头指针和队尾指针
}SqQueue;

int main() {
	SqQueue Q;				//声明一个顺序存储的队列
	return 0;
}

2.2.2 队列的基本操作

队列像表与栈一样，也存在增删改查等操作，而我们说的队列，是首位不相连的结构，也就是单纯的只允许在表头、表尾操作的顺序表。而对于顺序表的操作，我就没有必要再写一遍，具体内容可参考我的线性表的笔记，然后自己去写顺序队列的基本操作（纸上得来终觉浅，绝知此事要躬行）。数据结构（一）——线性表

虽然我在此没有对队列的操作进行一个详细的描述，但并不妨碍我们发现问题，那就是对于队列的队满与队空，如何进行判断？如果我们使用 Q.front==Q.rear 进行队空判断，那我们该如何进行队满判断呢？

我们如果使用最容易想到的方法，即 Q.rear==MaxSize 来进行判断，会发现，如果队列在入队的过程中出现出队操作，即使最后Q.rear==MaxSize了，前面依然存有空余空间，显然，这个判断条件是有问题的。

在此，就可以引出我们接下来要说的循环队列。

2.2.3 循环队列的队空与队满判断

2.2.3.1 队空判断

循环队列的队空判断可以采用我们之前所说的方法，判断队头与队尾指针是否指向头一处。

1
2
3
4
5
6
7
8
//队空判断条件 Q.front==Q.rear
//队空判断
bool QueueEmpty(SqQueue Q) {
	if (Q.rear == Q.front)	//队空判断条件
		return true;
	else
		return false;
}
2.2.3.2 队满判断
数据结构（二）——栈与队列与数组——循环队列队空队满判断.png

队满判断操作可以采用取模运算的方法进行判断，这样实际上首尾不相连的队列，在逻辑上就变成了相连，普通的队列就变成了循环队列。

在循环队列中，每次入队时，先将数据元素放到队尾指针当前的位置，再令队尾指针加1取模，当队尾指针指到最后一个存储单元时，就默认队已满，如上面图例。在这里有一个疑问，那就是队列中最后一个存储单元还空着，为什么却说队已满？实际原因很简单，那就是这个时候如果往最后一个存储单元插入新的数据，那队尾指针就会继续向后指，此时队尾指针与队头指针指向同一处，根据前面所说的队空判断条件，此时会判断队空，但实际上却是队满。为了避免这种尴尬情形，所以选择牺牲最后一个存储单元。那队满的判断条件就显而易见了，每次进行入队操作前，对队尾指针的下一位进行判断是否等于队头指针；如果等于，则队满；反之则未满。

1
2
3
4
5
6
7
//队满判断
bool QueueFull(SqQueue Q) {
	if ((Q.rear + 1) % MaxSize == Q.front)	//队满判断条件
		return true;
	else
		return false;
}

2.2.4 循环队列的初始化

循环队列的初始化，让队头队尾指针全指向存储空间的首位即可。

1
2
3
4
//初始化
void InitQueue(SqQueue& Q) {
	Q.rear = Q.front = 0;	//初始化
}

2.2.5 循环队列入队操作

1
2
3
4
5
6
7
8
9
//入队操作
bool EnQueue(SqQueue& Q, ElemType x) {
	if (true == QueueFull(Q))			//判断队满
		return false;
	Q.data[Q.rear] = x;					//将数据入队	
	//用模运算将存储空间在逻辑上变成环状
	Q.rear = (Q.rear + 1) % MaxSize;	//队尾指针加1取模
	return true;
}

2.2.6 循环队列的出队操作

注意，出队是在队头进行操作的，要先把队头元素取出，再将队头指针加1取模。

1
2
3
4
5
6
7
8
//出队操作
bool DeQueue(SqQueue& Q, ElemType x) {
	if (true == QueueEmpty(Q))			//队空判断
		return false;
	x = Q.data[Q.front];				//取出队头元素
	Q.front = (Q.front + 1) % MaxSize;	//进行出队操作
	return true;
}

如果将程序里的Q.front = (Q.front + 1) % MaxSize;删掉，就是获取队头元素的函数。

2.2.7 队中元素的数量

根据上面对循环队列的队空与队满的判断条件，可以思考一下，如何对队列中的元素个数进行计算？

首先可以知道的是，在进行取模运算以后，逻辑上队列已经成了一个环，这个时候有两种情况：第一种情况是队头指针在前，队尾指针在后，这时元素个数为队尾指针减去队头指针。第二种情况是队尾指针在前，队头指针在后，这个时候队尾指针相当于第二次进入队列进行入队操作，可以让队尾指针加上存储单元的个数再减去队头指针，所得结果便是队中元素数量。

通过分析，我们可以通过下面这个式子来对上面两种情况进行一个总结：

1
Total = (Q.rear+MaxSize-Q.front)%MaxSize //获取元素个数

2.2.8 拓展补充（1）—— 队空与队满的判断

在上面，我们已经说过一种队空与队满的判断方案，那就是牺牲一个存储单元来区分队空队满，入队时少用一个队列单元，这也是一种较为普遍的做法。但除了这种做法，我们还可以使用其它方法来进行队空队满的判断，可以参考接下来的几种方案。

2.2.8.1 方案二

如果我们不想浪费那一个存储单元，又想能够进行队空队满的判断该怎么做呢？可以在描述队列结构体的存储类型时，增加一个长度项，这样每次入队和出队操作时，都对长度进行加减操作，当队头指针和队尾指针指向同一处时，对长度进行判断。如果长度为0，则队空；如果长度为最大存储数量，则队满。

1
2
3
4
5
6
//队列存储类型的描述
typedef struct {
	ElemType data[MaxSize];	//用静态数组存放队列元素
	int front, rear;		//队头指针和队尾指针
    int size;				//队列当前长度
}SqQueue;
数据结构（二）——栈与队列与数组——判断方案二.png
2.2.8.2 方案三

我们还可以定义一个变量，用来记录最近一次进行的是入队操作还是出队操作，根据最近一次进行的操作来判断队满还是队空。

比如定义一个tag变量，当tag=1时，最近一次进行的是入队操作，这时如果队头与队尾指向同一处，可以判断队满；当tag=0时，最近一次进行的是出队操作，这时如果队头与队尾指向同一处，可以判断队空。

1
2
3
4
5
6
//队列存储类型的描述
typedef struct {
	ElemType data[MaxSize];	//用静态数组存放队列元素
	int front, rear;		//队头指针和队尾指针
    int tag;				//记录最近一次操作
}SqQueue;
数据结构（二）——栈与队列与数组——判断方案三.png

2.2.9 拓展补充（2）—— 队列的变形

在前面，我们对队列进行初始化时，让队头指针和队尾指针都指向同一起始位置。然后在进行基本操作入队时，先将元素入队，再让队尾指针后移，队尾指针指向最后一个存储数据的下一位。

但也可能会遇到别的情况，就是队尾指针永远指向最后一个存储数据的位置，这个时候就需要先让队尾指针后移一位，再让数据入队。面对这种情况，在进行初始化时，就需要让队尾指针指向存储单元的最后一位，即最大存储长度减1（Q.rear=MaxSize-1），这个时候进行入队操作时，队尾指针加1，刚好与队头指向同一位置（都指向存储单元首地址），数据即可存入首位。

数据结构（二）——栈与队列与数组——队列变形.png 数据结构（二）——栈与队列与数组——变形队空队满.png

2.2.10 顺序队列小结

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
//循环队列的框架
#include<stdio.h>
#include<stdlib.h>
#define	MaxSize 10		//定义队列中元素的最大个数
#define ElemType int	//含义参考1.2.9的程序

//队列存储类型的描述
typedef struct {
	ElemType data[MaxSize];	//用静态数组存放队列元素
	int front, rear;		//队头指针和队尾指针
}SqQueue;

//队空判断
bool QueueEmpty(SqQueue Q) {
	if (Q.rear == Q.front)	//队空判断条件
		return true;
	else
		return false;
}

//队满判断
bool QueueFull(SqQueue Q) {
	if ((Q.rear + 1) % MaxSize == Q.front)	//队满判断条件
		return true;
	else
		return false;
}

//初始化
void InitQueue(SqQueue& Q) {
	Q.rear = Q.front = 0;	//初始化
}

//入队操作
bool EnQueue(SqQueue& Q, ElemType x) {
	if (true == QueueFull(Q))			//判断队满
		return false;
	Q.data[Q.rear] = x;					//将数据入队	
	//用模运算将存储空间在逻辑上变成环状
	Q.rear = (Q.rear + 1) % MaxSize;	//队尾指针加1取模
	return true;
}

//出队操作
bool DeQueue(SqQueue& Q, ElemType x) {
	if (true == QueueEmpty(Q))			//队空判断
		return false;
	x = Q.data[Q.front];				//取出队头元素
	Q.front = (Q.front + 1) % MaxSize;	//进行出队操作
	return true;
}

int main() {
	SqQueue Q;				//声明一个顺序存储的队列
	ElemType x;
	InitQueue(Q);
	EnQueue(Q, x);
	DeQueue(Q, x);
	return 0;
}

2.3 队列的链式实现

链式队列可以看成单链表的阉割版，即就是只允许在表头和表尾进行操作的单链表。所以，单链表的一切都可以移植到链式队列上来。同单链表一样，链式队列也可以分为带头结点和不带头结点两种，如果是带头结点的，队头指针就要指向头结点；如果是不带头结点的，队头指针就指向首个数据。在执行入队与出队等基本操作时，也要注意区分。

数据结构（二）——栈与队列与数组——链队列的分类.png

2.3.1 链队列的定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//定义链式队列中的结点
typedef struct LinkNode {
	ElemType data;
	struct LinkNode* next;
}LinkNode;

//定义链式队列
typedef struct {
	LinkNode* front, * rear;	//定义队头和队尾指针
}LinkQueue;

int main() {
	LinkQueue Q;	//创建一个链式队列变量
	return 0;
}

2.3.2 链队列的初始化及队空判断

因为采用链式存储的方式，所以一般不存在队满的情况（除非内存满了），那这里我就只对队列的队空进行判断。

2.3.2.1 带头结点初始化及队空判断
1
2
3
4
5
6
//带头结点的初始化
void InitQueue(LinkQueue& Q) {
	//初始化时 front、rear都指向头结点
	Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
	Q.front->next = NULL;
}
1
2
3
4
5
6
7
//判断带头结点队列是否为空
bool IsEmpty(LinkQueue Q) {
	if (Q.front == Q.rear)
		return true;
	else
		return false;
}
数据结构（二）——栈与队列与数组——带头结点初始化.png
2.3.2.2 不带头结点的初始化及队空判断
1
2
3
4
5
6
//不带头结点的初始化
void InitQueue(LinkQueue& Q) {
    //初始化时 front、rear都指向NULL
	Q.front = NULL;
	Q.rear = NULL;
}
1
2
3
4
5
6
7
//判断不带头结点队列是否为空
bool IsEmpty(LinkQueue Q) {
	if (Q.front == NULL)
		return true;
	else
		return false;
}
数据结构（二）——栈与队列与数组——不带头结点初始化.png

2.3.3 链队列的入队操作

2.3.3.1 带头结点的链队列的入队操作
1
2
3
4
5
6
7
8
9
//带头结点的链队列的入队操作
bool EnQueueWithhead(LinkQueue& Q, ElemType x) {
	LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
	s->data = x;
	s->next = NULL;
	Q.rear->next = s;
	Q.rear = s;
	return true;
}
数据结构（二）——栈与队列与数组——带头结点入队.png
2.3.3.2 不带头结点的入队操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//不带头结点的链队列入队操作
bool EnQueueWithouthead(LinkQueue& Q, ElemType x) {
	LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
	s->data = x;
	s->next = NULL;
	//在不带头结点的队列中插入数据，需要先判断当前队列有没有数据
	if (Q.front==NULL)	
	{
		//在空队列插入第一个数据，需要同时更改队头队尾指针
		Q.front = s;	
		Q.front = s;
	}
	else
	{
		//不在空队列插入数据，只需更改表尾指针
		Q.rear->next = s;
		Q.rear = s;
	}
	return true;
}
数据结构（二）——栈与队列与数组——不带头结点入队.png

2.3.4 链队列的出队操作

2.3.4.1 带头结点的链队列的出队操作
1
2
3
4
5
6
7
8
9
10
11
12
//带头结点的链队列的出队操作
bool DeQueueWithhead(LinkQueue &Q, ElemType &x) {
	if (Q.front == Q.rear)			//队空判断
		return false;
	LinkNode* p = Q.front->next;	//开辟一个结点指向头结点后首个数据
	x = p->data;					//用变量x返还队头元素
	Q.front->next = p->next;		//修改头结点next指针
	if (Q.rear == p)				//如果出队元素是最后一个
		Q.rear = Q.front;			//修改队尾指针
	free(p);						//释放结点空间
	return true;	
}
数据结构（二）——栈与队列与数组——带头结点出队.png
2.3.4.2 不带头结点的链队列的出队操作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//不带头结点的链队列的出队操作
bool DeQueueWithouthead(LinkQueue& Q, ElemType& x) {
	if (Q.front == Q.rear)			//队空判断
		return false;
	LinkNode* p = Q.front;			//开辟一个结点指向当前出队元素
	x = p->data;					//用变量x返还队头元素
	Q.front = p->next;				//修改头结点front指针
	if (Q.rear == p) {				//如果出队元素是最后一个
		Q.front = NULL;				//修改队头指针
		Q.rear = NULL;				//修改队尾指针
	}
	free(p);						//释放结点空间
	return true;
}
数据结构（二）——栈与队列与数组——不带头结点出队.png

2.3.5 链队列小结

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
//链队列框架
#include<stdio.h>
#include<stdlib.h>
#define ElemType int	//含义参考1.2.9的程序

//定义链式队列中的结点
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)
		return true;
	else
		return false;
}

//带头结点的链队列的入队操作
bool EnQueueWithhead(LinkQueue& Q, ElemType x) {
	LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
	s->data = x;
	s->next = NULL;
	Q.rear->next = s;
	Q.rear = s;
	return true;
}

//带头结点的链队列的出队操作
bool DeQueueWithhead(LinkQueue &Q, ElemType &x) {
	if (Q.front == Q.rear)			//队空判断
		return false;
	LinkNode* p = Q.front->next;	//开辟一个结点指向头结点后首个数据
	x = p->data;					//用变量x返还队头元素
	Q.front->next = p->next;		//修改头结点next指针
	if (Q.rear == p)				//如果出队元素是最后一个
		Q.rear = Q.front;			//修改队尾指针
	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)
		return true;
	else
		return false;
}

//不带头结点的链队列入队操作
bool EnQueueWithouthead(LinkQueue& Q, ElemType x) {
	LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
	s->data = x;
	s->next = NULL;
	//在不带头结点的队列中插入数据，需要先判断当前队列有没有数据
	if (Q.front==NULL)	
	{
		//在空队列插入第一个数据，需要同时更改队头队尾指针
		Q.front = s;	
		Q.front = s;
	}
	else
	{
		//不在空队列插入数据，只需更改表尾指针
		Q.rear->next = s;
		Q.rear = s;
	}
	return true;
}

//不带头结点的链队列的出队操作
bool DeQueueWithouthead(LinkQueue& Q, ElemType& x) {
	if (Q.front == Q.rear)			//队空判断
		return false;
	LinkNode* p = Q.front;			//开辟一个结点指向当前出队元素
	x = p->data;					//用变量x返还队头元素
	Q.front = p->next;				//修改头结点front指针
	if (Q.rear == p) {				//如果出队元素是最后一个
		Q.front = NULL;				//修改队头指针
		Q.rear = NULL;				//修改队尾指针
	}
	free(p);						//释放结点空间
	return true;
}

int main() {
	LinkQueue Q;	//创建一个链式队列变量
	//----------------------------
	//此间为操作函数，根据情况调用
	//----------------------------
	return 0;
}
数据结构（二）——栈与队列与数组——链队列小结.png

2.4 双端队列

2.4.1 双端队列定义

双端队列是指只允许在两端进行插入和删除操作的线性表。双端队列两端的地位是平等的。

数据结构（二）——栈与队列与数组——双端队列.png

2.4.2 输入受限的双端队列和输出受限的双端队列

输入受限的双端队列：只允许从一端插入、两端删除的线性表。

输出受限的双端队列：只允许从两端插入、一端删除的线性表。

数据结构（二）——栈与队列与数组——输入输出受限的双端队列.png

2.4.3 双端队列小结

数据结构（二）——栈与队列与数组——双端队列小结.png

3. 栈的应用

3.1 栈在括号匹配中的应用

众所周知，括号字符是以组（成双成对）的形式出现，每一组括号字符里都包含同类型的左右括号。在一连串的数据或程序里，出现的越晚的左括号，他得等级越低，所以与之匹配的同类型的右括号出现的就越早。

知道这一点后，就可以发现，括号嵌套的顺序是有规律的，如假设表达式中有圆括号和方括号两种，那么（ [ ] ( ) ）、[ ( [ ] ) ]都是合法且正确的，但是（ [ ) ]就不正确。

这是因为，假设有一个存储容器，出现左括号就暂存进去，出现右括号，就将容器里最后进入的括号取出来进行匹对，匹对成功则两者可以算作一组消除。这时就可以发现，上面正确的两组括号顺序，他们最后可以完全消除而错的那一组，”[“ “)”并不匹配。

由此可以发现，括号的匹配算法，与栈的特性很相近，都是先入后出的。先依次扫描所有字符，遇到左括号入栈，遇到右括号则弹出栈顶元素检查是否匹配。

这样的匹配会出现以下失败的情况：

  1. 左括号单身。扫描完以后，栈里仍有左括号。
  2. 右括号单身。栈里已经没有括号了，但是扫描到了右括号。
  3. 左右括号不匹配。
数据结构（二）——栈与队列与数组——括号匹配算法流程.png 数据结构（二）——栈与队列与数组——括号匹配算法实现.png

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

表达式由三个部分组成：操作数、运算符、界限符（界限符即括号，是必不可少的，反映了计算的先后顺序）

3.2.1 三种算数表达式

中缀表达式：运算符在两个操作数中间，也是最贴近人类使用的表达式，但是计算机不易解析。所以产生了后缀表达式和前缀表达式。

后缀表达式：也称逆波兰表达式，运算符在两个操作数之后。

前缀表达式：也称波兰表达式，运算符在两个操作数之前。

数据结构（二）——栈与队列与数组——三种表达式.png

3.2.2 中缀表达式转后缀表达式

数据结构（二）——栈与队列与数组——中缀转后缀.png

中缀表达式转后缀表达式，由于表达式中各个运算符的运算顺序不唯一，所以得到的后缀表达式也不唯一。如图中的 A+B*(C-D)-E/F 根据两种不同的运算顺序可以得到两种不同的后缀表达式结果。

但是需要注意，客观来看两种都正确，但计算机计算采用的是第一种情况，即后缀表达式中的运算符的排列顺序与中缀表达式的运算符的运算顺序一致。这是因为我们计算机实现此运算的算法采用的是栈的结构（参考3.2.7）。后续我们在进行中缀转后缀计算时，也可以通过查看后缀表达式中的运算符的排列顺序与中缀表达式的运算符的运算顺序是否一致进行算法的验证。

为了保证我们每次都可以获得正确的机算后缀表达式，所以这里提出一个左优先原则：只要表达式中偏向左边的运算符能先计算，就优先计算。

3.2.3 后缀表达式计算

手算：

数据结构（二）——栈与队列与数组——后缀计算.png

机算：

数据结构（二）——栈与队列与数组——后缀计算机算.png

注意，后缀表达式的计算过程，这里我只贴了一张结果图，但具体的模拟过程要掌握，考试时可能会出现选择题或大题。不熟悉的可以参考连接视频：表达式求值

3.2.4 中缀表达式转前缀表达式

数据结构（二）——栈与队列与数组——中缀转前缀.png

中缀转前缀与中缀转后缀一样，不同的是这里采用右优先原则。

右优先原则：只要表达式中偏向右边的运算符能先计算，就优先计算。

通过右优先原则得出的表达式最后的排列呈现如下的规则：即前缀表达式中的运算符的排列顺序与中缀表达式的运算符的运算顺序相反。

3.2.5 前缀表达式计算

数据结构（二）——栈与队列与数组——前缀表达式计算.png

注意：

  1. 前缀表达式计算的扫描顺序是从右向左，而后缀则是从左向右。
  2. 在前缀表达式中，先出栈的是左操作数，后出栈的是右操作数。后缀表达式恰恰相反，先出栈的是右操作数 ，后出栈的是左操作数。

3.2.6 前缀、中缀、后缀基础小结

数据结构（二）——栈与队列与数组——前缀中缀后缀小结.png

3.2.7 中缀表达式转后缀表达式算法

数据结构（二）——栈与队列与数组——中缀转后缀模拟.png

中缀转后缀表达式的机算是考试重点，尤其是牵扯到括号的转化，这里需要深入掌握计算机通过栈进行计算转化的过程。

3.2.8 栈实现中缀表达式的计算

栈实现中缀表达式计算，就是在扫描表达式的时候，将他转化成后缀，同时，在转化的时候，对已转化的部分能进行计算的先计算。

说的明白点，中缀表达式计算就是3.2.7中缀表达式转后缀表达式的算法与3.2.3后缀表达式算法的交叉结合。

通过以上的了解，就可以知道，在初始化时，需要初始化两个栈，一个用来存放操作数，一个用来存放运算符。

数据结构（二）——栈与队列与数组——中缀表达式机算.png

注意，这部分的考察是重点，3.2.7和3.2.8的知识点需要深刻掌握，相关视频链接贴在这里 栈的应用——表达式计算。

3.2.9 栈的表达式计算应用小结

数据结构（二）——栈与队列与数组——栈的应用小结.png

3.3 栈在递归中的应用

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

函数的调用，就是通过栈，将最开始执行的函数压入栈中，然后跟据其他函数被调用的顺序，依次往栈中压入函数。当最后一个被调用的函数执行结束时，则将该函数出栈，执行接下来的栈顶被调用函数。

同理函数的递归就是函数通过不断调用函数自己本身从而达到目的的一种实现方法。所以，递归函数的使用也是通过栈来执行。递归调用时，函数调用栈可称为 “递归工作栈”。

另外，函数调用时，需要用一个栈存储：调用返回地址、实参和局部变量。

数据结构（二）——栈与队列与数组——栈的递归.png

递归算法的缺点：

  1. 太多层递归可能会导致栈溢出。
  2. 可能出现很多次重复调用运算。

4. 队列的应用

队列的应用：

  1. 树的层次遍历。
  2. 图的广度优先。
  3. 操作系统的应用。多个进程争抢着使用有限的系统资源时，FCFS（先来先服务）是一种常用策略。

5. 数组和特殊矩阵的压缩存储

5.1 数组

5.1.1 一维数组存储结构

数据结构（二）——栈与队列与数组——一维数组存储结构.png

5.1.2 二维数组存储结构

二维数组如图所示，它的存储分为行优先和列优先。

数据结构（二）——栈与队列与数组——二维数组结构.png
5.1.2.1 行优先存储
数据结构（二）——栈与队列与数组——二维数组行优先.png

只要给了图中i，j的值，计算机就能立刻计算出该位的存储地址，所以二维数组也具有随机存取的特性。

5.1.2.2 列优先存储
数据结构（二）——栈与队列与数组——二维数组列优先.png

5.2 矩阵的压缩存储

5.2.1 普通矩阵的存储

数据结构（二）——栈与队列与数组——普通矩阵存储.png

5.2.2 对称矩阵的压缩存储

数据结构（二）——栈与队列与数组——对称矩阵的压缩存储.png

矩阵就是由许多ai,j组成的一个集合，也可以看成 a[i] [j]形式的一个二维数组。对称矩阵的上三角区和下三角区是相等的，所以存储的策略有两种：一是上三角加对角线；二是下三角加对角线。

(1)通过行优先加下三角加对角线的方式进行矩阵存储：

一般情况下，采用下三角加对角线的方式进行存储，这个时候，i>=j，而存储方法就是把下三角和对角线的数据映射到一个一维数组中进行存储。

这个时候产生了一个问题，这个数组的大小应为多少？假设是个n阶的方阵，数组里存储下半三角加对角线的数据，那这个数组的长度，就应该是1+2+3+……+n，即等差数列求和公式：n（n+1）/2。

解决了数组大小的问题，就又产生了第二个问题，程序员如何快速使用压缩存储后的数据呢？方法很简单，就是根据存储数据在矩阵中的下标，通过计算快速得到在一维数组中的下标，即可实现对矩阵的随机存取。具体的计算公式在接下来的贴图中。

(2)通过行优先加上三角加对角线的方式进行矩阵存储：

上三角加对角线，并通过行优先存储的方式基本实现与（1）的下三角存储一样。上三角的模型中，j>=i，可以通过将他转置的方法，把ai,j转换成aj,i，这样上三角的计算与存储，就与下三角的一样了。

数据结构（二）——栈与队列与数组——对称矩阵压缩存储行优先.png

(3)通过列优先加上三角/下三角加对角线的方式进行矩阵存储：

列优先的存储方式和行优先的思想是一致的，所以我在这里只贴了一张图，详细的思想可以参考（1）。

数据结构（二）——栈与队列与数组——对称矩阵压缩存储列优先.png

5.2.3 三角矩阵的压缩存储

所谓三角矩阵，就是除对角线和三角区，其余的元素都是相同的。这里的存储方法和对称矩阵如出一辙，唯一不同的是，需要在映射的一维数组的最后，添加一个常量存储位用来存储常量c。

(1)下三角矩阵的行优先压缩存储：

数据结构（二）——栈与队列与数组——下三角压缩存储.png

(2)上三角矩阵的行优先压缩存储：

数据结构（二）——栈与队列与数组——上三角压缩存储.png

5.2.4 三对角矩阵的压缩存储

三对角矩阵，又称带状矩阵，即只有矩阵对角线上的元素以及对角线上元素的上下左右可以是非0元素的矩阵，其余位置均为0。用数学式来表达就是，对于矩阵中任意一元素ai,j，当|i-j|>1时，ai,j=0。

从图中也可以很明显发现三对角矩阵的特点，那就是除了第一行和最后一行只有两个元素外，其余每一行都有三个元素。

数据结构（二）——栈与队列与数组——对三角压缩存储.png 数据结构（二）——栈与队列与数组——对三角压缩存储反解.png

注意上图中右侧，两种计算取值的刚好临界问题。

5.2.5 稀疏矩阵的压缩存储

(1)使用三元组进行稀疏矩阵的压缩存储：

数据结构（二）——栈与队列与数组——三元组存储稀疏矩阵.png

(2)使用十字链表法进行稀疏矩阵的压缩存储：

数据结构（二）——栈与队列与数组——十字链表存储稀疏矩阵.png

5.2.6 小结

数据结构（二）——栈与队列与数组——压缩矩阵小结.png