栈和队列（数据结构、C语言）

前言：

• 本篇博客整理了数据结构初阶的，关于栈和队列的相关知识
• 代码实现：C语言

---

---

1. 栈

1.1 栈的概念和结构

• 栈：栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。
• 后进后出原则：栈中的数据元素遵循后进后出的原则
• 压栈：栈的插入操作叫做进栈、压栈、入栈，入数据在栈顶
• 出栈：栈的删除操作叫做出栈，出数据也在栈顶
  
  

---

1.2 栈的实现

• 栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
• 栈主要有以下几个函数接口

//静态的栈  定长，实际中一般不实用
//typedef int STDateType;
//typedef struct Stack
//{
//	STDateType a[N];//N的值要给定
//	int top;
//}ST;


//动态的栈 支持动态增长
typedef int STDateType;
typedef struct Stack
{
	STDateType* a;
	int top;//栈顶
	int capacity;//容量
}ST;


//初始化栈
void StackInit(ST* ps);

//销毁栈
void StackDestroy(ST* ps);

//入栈
void StackPush(ST* ps, STDateType x);

//出栈
void StackPop(ST* ps);

//获取栈顶元素
STDateType StackTop(ST* ps);

//检测栈是否为空
bool StackEmpty(ST* ps);

//获取栈的长度(栈中存放数据的个数)
int StackSize(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
36
37
38
39

---

1.2.1 初始化栈

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

1.2.2 销毁栈

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

1.2.3 入栈

void StackPush(ST* ps, STDateType x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDateType* tmp = (STDateType*)realloc(ps->a, sizeof(STDateType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}

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

1.2.4 出栈

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

1.2.5 获取栈顶元素

STDateType StackTop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	return ps->a[ps->top - 1];
}
1
2
3
4
5
6
7

1.2.6 检测栈是否为空

bool StackEmpty(ST* ps)
{
	assert(ps);

	return ps->top == 0;
}
1
2
3
4
5
6

1.2.7 获取栈的长度(栈中存放数据的个数)

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

---

2. 队列

2.1 队列的概念和结构

• 队列：只允许在一端进行插入数据，在另一端进行删除数据操作的特殊线性表
• 先进先出原则：队列具有先进先出的特性
• 队尾：进行插入操作的一端称为队尾
• 队头：进行删除操作的一端称为对头
  
• 队列的用途：

1. 先进先出的特性，排队，保持绝对公平性
2. 广度优先遍历 BFS

---

2.2 队列的实现

• 队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。
• 队列一般有以下接口函数：

//链式结构：表示队列
typedef int QDateType;
typedef struct QueueNode
{
	struct QueueNode* next;
	QDateType date;
}QNode;

//队列的结构
typedef struct Queue
{
	//int size;
	QNode* head;
	QNode* tail;
}Queue;

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

//销毁队列
void QueueDestroy(Queue* pq);

//队尾入队列
void QueuePush(Queue* pq, QDateType x);

//队头出队列
void QueuePop(Queue* pq);

//获取队列头部元素
QDateType QueueFront(Queue* pq);

//获取队列队尾元素
QDateType 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

2.2.1 初始化队列

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
}
1
2
3
4
5
6

2.2.2 销毁队列

void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}

	pq->head = pq->tail = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.2.3 队尾入队列

void QueuePush(Queue* pq, QDateType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		printf("malloc fail");
		exit(-1);
	}

	newnode->date = x;
	newnode->next = NULL;

	if (pq->tail == NULL)
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2.2.4 队头出队列

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	if (pq->head->next == NULL)//只剩下一个结点
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else//多个结点
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.2.5 获取队列头部元素

QDateType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->head->date;
}
1
2
3
4
5
6
7

2.2.6 获取队列队尾元素

QDateType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->tail->date;
}
1
2
3
4
5
6
7

2.2.7 检测队列是否为空

bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->head == NULL;
}
1
2
3
4
5
6

2.2.8 获取队列的长度(队列中存放数据的个数)

int QueueSize(Queue* pq)
{
	assert(pq);
	int size = 0;
	QNode* cur = pq->head;
	while (cur)
	{
		size++;
		cur = cur->next;
	}

	return size;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

---

学习记录：

• 本篇博客整理于2022.7.4
• 请多多指教🌹🌹🌹