栈和队列详解

感谢各位大佬对我的支持,如果我的文章对你有用,欢迎点击以下链接
🐒🐒🐒 个人主页
🥸🥸🥸 C语言
🐿️🐿️🐿️ C语言例题
🐣🐣🐣 python
🐓🐓🐓 数据结构C语言

栈

栈的概念及结构

栈：一种特殊的线性表(数据是挨着储存,是连续的)，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。

栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

注意栈顶不能叫做头,栈底不能叫做尾

栈的实现

栈分为两种
数组栈:数组通常让首元素的空间为栈底,末尾为栈顶(因为栈的规则是后进先出,数组让末尾为栈顶的尾删效率更高)

链式栈:
双向链表实现的话栈顶可以是头节点或者尾借点,用头节点当栈顶就是头插或者头删,尾节点当栈顶就是尾插尾删
单链表实现的话通常用头节点当栈顶,尾节点当栈底(因为单链表头插头删的时间复杂度低,而尾插尾删需要遍历一遍链表,时间复杂度高)

数组栈和链式栈相比,数组栈相对来说更好一点,因为数组栈简单快捷,虽然数组栈有时需要扩容,但是这种情况相对来说比较少,因为一次扩容就是2倍左右(不是规定必须2倍,只是2倍相对来说更合理)
对于两个链式栈相比,单链表会更合适一点,因为双向链表实现起来更复杂一点

数组栈的实现

typedef struct stack
{
	int* a;
	int top;//栈顶
	int capacity;空间
}ST;
1
2
3
4
5
6

数组栈功能的实现

栈的初始化void STInit(ST* pst)

初始化的时对于指针a和capacity，我们很容易就会想到a=NULL，capacity=0

而对于top的初始化就需要注意

初始化情况一

如果top为数组的下标，当top初始化为0时就会出现歧义
当数组为空时，top=0
当数组中有一个元素时，top也为0
为了避免这种情况，我们将top初始化成-1

初始化情况二

我们也可以认为top代表数据个数，或者理解成指向栈顶元素的下一个位置
这样top就可以初始化成0

代码

void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->capacity = 0;
	pst->top = 0//或者pst->top = -1;
}
1
2
3
4
5
6
7

后面的代码我们讨论top初始化为0的情况

栈的插入void STPush(ST* pst, STDataType x)

栈的插入和之前我写的顺序表还有链表方式都差不多，有疑惑的可以去看看我之前写的文章

代码

void STPush(ST* pst, STDataType x)
{
	assert(pst);
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = realloc(pst->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
	pst->a[pst->top] = x;
	pst->top++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

栈的删除void STPop(ST* pst)

栈的删除要注意不能让top=0，因为top=0后就代表栈没有元素可以删除，所以要断言

代码

void STPop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	pst->top--;
}
1
2
3
4
5
6

栈获取数据STDataType STTop(ST* pst)

因为top初始化为0，所以top为栈顶元素的下一个的下标

代码

STDataType STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	return pst->a[pst->top - 1];
}
1
2
3
4
5
6

判断栈是否为空bool STEmpty(ST* pst)

bool STEmpty(ST* pst)
{
	assert(pst);
	return pst->top == 0;
}
1
2
3
4
5

求栈的元素个数int STSize(ST* pst)

int STSize(ST* pst)
{
	return pst->top;
}
1
2
3
4

栈的销毁void STDestory(ST* pst)

void STDestory(ST* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->top = pst->capacity = 0;
}
1
2
3
4
5
6
7

栈的打印方式

由于栈遵循后进先出,在访问栈的元素时,我们需要做到访问一个栈的元素就删除一个栈的元素,当栈访问完一遍后,栈的元素就全没了,也就是栈为空

int main()
{
	ST s;
	STInit(&s);
	STPush(&s, 1);
	STPush(&s, 2);
	STPush(&s, 3);
	STPush(&s, 4);
	STPush(&s, 5);
	while (!STEmpty(&s))

	{
		printf("%d ", STTop(&s));
		STPop(&s);
	}
	printf("\n");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

栈溢出问题

栈有两种
数据结构的栈:存储数据

操作系统的栈:内存区域的划分(malloc,realloc…)

栈溢出中的栈是指操作系统的栈,发生的情况一般为递归出现返回条件错误,导致一直调用函数建立函数栈帧

队列

队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) (一端入一端出)

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

队列的入队顺序和出队顺序是否和栈一样存在一对多的关系？
因为栈是后进先出,假设我们入栈一个数据A，在A入栈后不继续加入其他的数据B C D,那么如果我们进行出栈的话，数据A就会第一个出来



所以栈的入栈顺序和出栈顺序是一对多的情况，举个例子
栈的入栈顺序为A B C D E
则出栈顺序可能为 E D C B A，或者 A B C D E
对于E D C B A这种情况就是当数据全部入栈后，我们按照后进先出的规则，进行出栈，也就是E最后入栈，所以第一个出栈，D是倒数第二个入栈，所以出栈的时候就是第二个…

对于A B C D E这种情况就是当A刚入栈后，我们就让A直接出栈，因为其他的数据B C D E都还没有入栈，所以我们只能让A先出栈，之后再将B入栈，然后B再出栈…
出栈的顺序不止这两种，所以就不一一举例了，总之栈的出栈顺序和入栈顺序是一对多的关系

对于队列而言，因为是先进先出的顺序，所以入和出都只有一种情况，没有一对多的关系

队列的实现

队列也可以数组和链表的结构实现

如果用数组实现的就比较麻烦，因为队列是队尾入，对头出，那么如果用数组去实现队列，我们就要让数组头删，头删的复杂度为O（N）

如果用单链表的话，就很方便，因为是队尾入，队头出，删除数据不像栈一样要尾删，队列只需要让队头的数据删除就可以了，单链表的头删时间复杂度为O（1），并且实现起来要比双向链表要容易些，所以选择用单链表实现队列

单链表实现队列我们可以用带哨兵位的方式，也可以选择不用，带哨兵位需要malloc，最后还需要free掉哨兵位，并且哨兵位在这里的作用不是很大，所以队列的实现我们选择不带哨兵位的方式

实际中我们有时还会使用一种队列叫循环队列，环形队列可以使用数组实现，也可以使用循环链表实现

代码

typedef struct QueueNode
{
	QDataType val;
	struct QueueNode* next;
}QNode;
1
2
3
4
5

队列功能的实现

队列的尾插void QueuePush(Queue*pq, QDataType x);

队列尾插函数如果只传两个参数参数头节点的地址,还有需要插入的数据x,(void QueuePush(QNode* * phead, QDataType x)),那么尾插的时间复杂度就为O（N），这样好像单链表就没什么优势了
如果我们传入三个参数void QueuePush(QNode* * phead, QNode* * ptail, QDataType x)，其中ptail为指向尾节点的地址，虽然这样可以解决问题，但是我们要注意这里的指针全是二级指针，phead是plist指针传入的参数，因为plist是一个一级指针，要更改一级指针我们就需要将传参类型变成二级指针，ptail也是，非常麻烦

结构体封装指针typedef struct Queue

所以我们要创建一个结构体，将两个指针封装起来， 这样我们传入的参数就不用二级指针，只需要修改结构体成员就可以了

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size//size为队尾到队头总共有多少个节点
}Queue;
1
2
3
4
5
6

总结

如果遇到函数参数需要传入多个二级指针，那么我们可以用结构体将他们封装起来，结构体封装的成员就是二级指针的值，然后通过结构体访问成员将他们修改，并且在传参时我们只需要传入结构体的地址即可

代码

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode * )malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->val = x;
	newnode->next = NULL;
	if (pq->ptail == NULL)
	{
		pq->ptail = pq->phead = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

当ptail=NULL的时候就说明没有尾节点，只要队列有一个节点，那么尾节点都不可能为空，尾节点为空说明队列是空的，那么尾插就直接让尾节点=头节点=插入的newnode
如果尾节点不为空，那就直接让尾节点的next=newnode，然后插入newnode后newnode又是新的尾节点，所以让ptail=newnode
最后不要忘记size++

队列的头删void QueuePop(Queue* pq)

头删一般都得考虑两种情况，一种是只有一个节点，另一种就是没有节点

当没有节点时，我们assert断言就可以了

只有一个节点时，在头删后要小心ptail变成野指针，当phead走到下一个节点，发现是空后，如果直接把之前的头节点删除，我们会发现ptail还指向原来头节点的位置，free掉头节点后，ptail就成了野指针


所以需要判断如果phead走到下一个节点为空后，要让ptail赋值成NULL

代码

void QueuePop(Queue* pq)
{
	assert(pq);//结构体不能为空
	assert(pq->phead);//判断头节点为空的情况
	QNode* del = pq->phead;//del保存头节点方便后面释放空间
	pq->phead = pq->phead->next;
	free(del);
	if (pq->phead == NULL)
		pq->ptail == NULL;
		pq->size--
}
1
2
3
4
5
6
7
8
9
10
11

队列的初始化void QueueInit(Queue* pq)

代码

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}
1
2
3
4
5
6

队列的销毁void QueueDestroy(Queue* pq, QDataType x)

代码

void QueueDestroy(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = pq->ptail = NULL;
	size=0；
}
1
2
3
4
5
6
7
8
9
10
11
12
13

取队尾数据QDataType QueueBack(Queue* pq)

代码

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->ptail);
	return pq->ptail->val;
}
1
2
3
4
5
6

取队头数据QDataType QueueFront(Queue* pq)

代码

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead);
	return pq->phead->val;
}
1
2
3
4
5
6

判断队列是否为空bool QueueEmpty(Queue* pq)

代码

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == NULL;
}
1
2
3
4
5

获得队列的长度int QueueSize(Queue* pq)

代码

int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}
1
2
3
4
5