栈

一、栈的概念及结构

栈一种特殊的线性表，它只允许在固定的一端进行插入和删除元素操作；进行数据插入和删除操作的一端称为栈顶，另一端称为栈底；栈中的数据元素遵守后进先出 LIFO（Last In First Out）的原则；

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶；出栈：栈的删除操作叫做出栈，出数据也在栈顶；

注意：不要把栈区和栈混为一谈：栈区是内存划分的一块区域，属于操作系统学科；而栈是用于管理数据的一种结构，它在堆区上申请空间，属于数据结构学科。

栈的概念相关选择题

1.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出 栈的顺序是（ ）

A 12345ABCDE

B EDCBA54321

C ABCDE12345

D 54321EDCBA

答案：B 这道题很简单，根据栈的后进先出原则，直接就可以得出答案。

2.若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）

A 1,4,3,2

B 2,3,4,1

C 3,1,4,2

D 3,4,2,1

答案：C 这道题就需要我们仔细分析了，题目中明确说明了在进栈过程中可以出栈，基于这个原则，我们来对选项进行分析：

A：

B：

C：对于C来说，想要取出3，就必须先push 1 2 3，然后它紧接着取出了1，这是办不到的，想要取出1，必须先取出2；

D：

---

二、栈的实现

1、栈的结构

栈可以用顺序表实现，也可以用链表实现，我们这里选用顺序表实现，原因如下：

1、栈的插入和删除操作都在栈顶，即在数据的尾部进行，而顺序表在尾部插入和删除数据的效率为O(1)，完美的避开了顺序表的缺陷；

2、顺序表扩容和链表频繁 malloc 在整体上的效率是差不多的，只是顺序表会存在一定的空间浪费；

3、顺序表支持随机访问，且其缓存利用率更高；

综合考虑以上几种因数，我们采用顺序表实现栈；

结构的定义

//结构和符号的定义
#define DEF_SIZE 5     //默认初始化大小
#define CRE_SIZE 2     //默认一次扩容的倍数
typedef int STDataType;//重命名数据类型

typedef struct Stack
{
	STDataType* data;  //指向动态开辟的数组
	int top;           //记录栈顶
	int capacity;      //记录容量，容量满时扩容
}ST;
1
2
3
4
5
6
7
8
9
10
11

2、初始化栈

//初始化栈
void StackInit(ST* ps)
{
	assert(ps);
	ps->data = (STDataType*)malloc(sizeof(STDataType) * DEF_SIZE);
	if (ps->data == NULL)
	{
		perror("malloc fail");
		return;
	}
	ps->top = 0;
	ps->capacity = CRE_SIZE;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3、入栈

由于栈只能在栈顶插入元素，所以我们只需要在 push 函数中进行检查容量并扩容的操作，而不需要把 CheckCapacity 单独封装成一个函数。

void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	//检查是否需要扩容
	if (ps->top == ps->capacity)
	{
		STDataType* ptr = (STDataType*)realloc(ps->data, sizeof(STDataType) * ps->capacity * CRE_SIZE);
		if (ptr == NULL)
		{
			perror("realloc fail");
			return;
		}
		ps->data = ptr;
		ps->capacity *= DEF_SIZE;
	}

	//入栈
	ps->data[ps->top] = x;
	ps->top++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

4、出栈

出栈之前我们需要检查栈的容量是否为空。

//出栈
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}
1
2
3
4
5
6
7

5、获取栈顶元素

获取栈顶元素时我们也需要检查栈是否为空，避免造成对空指针的解引用。

//获取栈顶元素
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->data[ps->top - 1];  //数组下标从0开始
}
1
2
3
4
5
6
7

6、获取栈的长度

//获取栈的长度
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}
1
2
3
4
5
6

7、判断栈是否为空

//判断栈是否为空
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
1
2
3
4
5
6

8、销毁栈

//销毁栈
void StackDestory(ST* ps)
{
	assert(ps);
	free(ps->data);
	ps->data = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
1
2
3
4
5
6
7
8
9

需要注意的是，我们不需要定义栈的打印函数，因为栈不能遍历，如果我们想得到栈顶的前一个元素，我们就必须先把栈顶的元素给删除掉，让后面一个元素变成栈顶。

---

三、完整代码

1、Stack.h

#pragma once  //防止头文件重复包含

//头文件的声明
#include 
#include 
#include 
#include 

//结构和符号的定义
#define DEF_SIZE 5     //默认初始化大小
#define CRE_SIZE 2     //默认一次扩容的倍数
typedef int STDataType;//重命名数据类型

typedef struct Stack
{
	STDataType* data;  //指向动态开辟的数组
	int top;           //记录栈顶
	int capacity;      //记录容量，容量满时扩容
}ST;

//函数的声明
//初始化栈
void StackInit(ST* ps);
//销毁栈
void StackDestory(ST* ps);
//入栈
void StackPush(ST* ps, STDataType x);
//出栈
void StackPop(ST* ps);
//获取栈顶元素
STDataType StackTop(ST* ps);
//获取栈的长度
int StackSize(ST* ps);
//判断栈是否为空
bool StackEmpty(ST* ps);
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

2、Stack.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"

//初始化栈
void StackInit(ST* ps)
{
	assert(ps);
	ps->data = (STDataType*)malloc(sizeof(STDataType) * DEF_SIZE);
	if (ps->data == NULL)
	{
		perror("malloc fail");
		return;
	}
	ps->top = 0;
	ps->capacity = CRE_SIZE;
}

//销毁栈
void StackDestory(ST* ps)
{
	assert(ps);
	free(ps->data);
	ps->data = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

//入栈
void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	//检查是否需要扩容
	if (ps->top == ps->capacity)
	{
		STDataType* ptr = (STDataType*)realloc(ps->data, sizeof(STDataType) * ps->capacity * CRE_SIZE);
		if (ptr == NULL)
		{
			perror("realloc fail");
			return;
		}
		ps->data = ptr;
		ps->capacity *= DEF_SIZE;
	}

	//入栈
	ps->data[ps->top] = x;
	ps->top++;
}

//出栈
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	ps->top--;
}

//获取栈顶元素
STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->data[ps->top - 1];  //数组下标从0开始
}

//获取栈的长度
int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;
}

//判断栈是否为空
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
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

3、test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"

int main()
{
	ST st;
	//初始化栈
	StackInit(&st);

	//入栈
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);

	//栈不能遍历，只能取出；取出一个就pop一个
	while (!StackEmpty(&st))
	{
		printf("%d ", StackTop(&st));
		StackPop(&st);
	}

	//销毁栈
	StackDestory(&st);
	return 0;
}
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

大家也可以去我的 Gitee 仓库中获取完整代码：Stack/Stack · 野猪佩奇/日常学习 - 码云 - 开源中国 (gitee.com)

---

队列

一、队列的概念和结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表；队列中的数据元素遵守先进先出 FIFO（First In First Out）的原则；

入队列：进行插入操作的一端称为队尾；出队列：进行删除操作的一端称为队头。

队列概念相关选择题

以下( )不是队列的基本运算？

A 从队尾插入一个新元素

B 从队列中删除第i个元素

C 判断一个队列是否为空

D 读取队头元素的值

答案：B 队列只能删除队头的数据。

二、队列的实现

1、队列的结构

和栈一样，队列既可以使用顺序表实现，也可以使用链表实现，这里我们使用单链表实现，原因如下：

1、队列需要删除头部的元素，单链表头删的效率为O(1)；

2、使用链表可以按需申请空间，避免了空间的浪费；

但是我们发现使用单链表实现队列存在一个问题，那就是单链表尾插以及计算链表长度的效率都为O(N)，不符合我们的预期，那么我们需要把单链表改造为循环链表吗？可以是可以，但是这样又把队列的结构搞复杂了；所以综合考虑，这里我们增加三个变量，一个用于记录队尾，一个用于记录队头，还有一个用于记录队列的长度。

结构的定义

//符号和结构的定义
typedef int QEDataType;

typedef struct QueueNode  //队列的一个节点
{
	QEDataType data;
	struct QueueNode* next;
}QENode;

typedef struct Queue  //队列
{
	QENode* head;  //记录队列的头
	QENode* tail;  //记录队列的尾
	int size;      //记录队列的长度
}Queue;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2、初始化队列

//初始化队列
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 0;
}
1
2
3
4
5
6
7

3、从队尾入队列

由于我们使用了一个结构体来记录队列的头和尾，那么这里我们改变队列的头和尾时只需要改变结构体即可，所以只需要传递一级指针；

另外，队列也只能从队尾入数据，所以我们也没有必要单独封装一个 BuyNode 函数。

//队尾入队列
void QueuePush(Queue* pq, QEDataType x)
{
	assert(pq);
	//创建一个新节点
	QENode* newnode = (QENode*)malloc(sizeof(QENode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;

	//当入第一个元素时，需要改变队列的头
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = pq->tail->next;
	}
	pq->size++;
}
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

4、从队头出队列

这里我们除了正常的对队列进行判空之外，还有一个需要特别注意的地方：当队列只有一个元素时，我们再次头删虽然会让head指向NULL，但是tail仍然指向头删之前的那个节点，会形成野指针，所以我们这里需要单独判断。

//队头出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	//当队列只有一个元素时，我们再次头删虽然会让head指向NULL，但是tail仍然指向头删之前的那个节点，形成野指针，所以我们这里要单独判断
	if (pq->head == pq->tail)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QENode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	pq->size--;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

5、获取队头元素

//返回队头元素
QEDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}
1
2
3
4
5
6
7

6、获取队尾元素

//返回队尾元素
QEDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}
1
2
3
4
5
6
7

7、获取队列长度

//返回队列长度
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}
1
2
3
4
5
6

8、判断队列是否为空

//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}
1
2
3
4
5
6

9、销毁队列

//销毁队列
void QueueDestory(Queue* pq)
{
	assert(pq);
	QENode* cur = pq->head;
	while (cur)
	{
		QENode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

注意：和栈一样，队列也不需要定义 print 函数，因为队列也不能遍历，要想取出队头后面的元素，我们必须先 pop 掉之前的元素，让该元素成为队头。

---

三、完整代码

1、Queue.h

#pragma once    //防止头文件重复包含

//头文件的包含
#include 
#include 
#include 
#include 

//符号和结构的定义
typedef int QEDataType;

typedef struct QueueNode  //队列的一个节点
{
	QEDataType data;
	struct QueueNode* next;
}QENode;

typedef struct Queue  //队列
{
	QENode* head;  //记录队列的头
	QENode* tail;  //记录队列的尾
	int size;      //记录队列的长度
}Queue;

//函数的声明
//初始化队列
void QueueInit(Queue* pq);
//销毁队列
void QueueDestory(Queue* pq);
//队尾入队列
void QueuePush(Queue* pq, QEDataType x);
//队头出队列
void QueuePop(Queue* pq);
//返回队头元素
QEDataType QueueFront(Queue* pq);
//返回队尾元素
QEDataType QueueBack(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);
//返回队列长度
int QueueSize(Queue* pq);
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

2、Queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"

//初始化队列
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

//销毁队列
void QueueDestory(Queue* pq)
{
	assert(pq);
	QENode* cur = pq->head;
	while (cur)
	{
		QENode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

//队尾入队列
void QueuePush(Queue* pq, QEDataType x)
{
	assert(pq);
	//创建一个新节点
	QENode* newnode = (QENode*)malloc(sizeof(QENode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;

	//当入第一个元素时，需要改变队列的头
	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = pq->tail->next;
	}
	pq->size++;
}

//队头出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	//当队列只有一个元素时，我们再次头删虽然会让head指向NULL，但是tail仍然指向头删之前的那个节点，形成野指针，所以我们这里要单独判断
	if (pq->head == pq->tail)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QENode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	pq->size--;
}

//返回队头元素
QEDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->head->data;
}

//返回队尾元素
QEDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->tail->data;
}

//判断队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

//返回队列长度
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}
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

3、test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"

int main()
{
	Queue q;
	//初始化队列
	QueueInit(&q);

	//队尾入队列
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);

	//队列也不能遍历，取出一个元素即代表从队头出一个元素
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}

	//销毁队列
	QueueDestory(&q);
	return 0;
}
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

大家也可以去我的 Gitee 仓库中获取完整代码：Queue/Queue · 野猪佩奇/日常学习 - 码云 - 开源中国 (gitee.com)

---