1. 栈

1.1 栈的概念及结构

        栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一段称为栈顶，另一端称为栈底。

        栈中的数据元素遵守 后进先出 LIFO(Last In First Out)的原则，后进来的数据先出去

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

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

                        

1.2  栈的实现

        我们先分析一下，栈我们应该用顺序表还是链表实现？

        栈中的数据的插入和删除都是在栈顶实现的，不需要随机位置的插入删除，此时链表的优势就不大了。相比之下顺序表还有内存命中率高的优点，所以最后我们选择用顺序表实现栈

                                

        头文件，源文件，测试文件这里我就不展示了，直接写栈中功能的实现

1.2.1 栈的初始化和销毁

        这个没什么好说的，直接上代码

1.2.2 判断栈是否真是空

        

1.2.3 压栈

        压栈涉及到扩容，如果栈内空间不够就要扩容，栈满的判断标准就是 栈顶top 和 总空间大小capacity 数值相同，然后压完之后不要忘记top++

1.2.4 出栈

        这个很简单，让栈顶回退一个位置就行了

                ​​​​​​​        

1.2.5 取栈顶元素

        这里要注意我们在取栈顶的时候要取 top-1 因为我们在初始化的时候设定的top为0，实际上此时的栈顶指向了一个空的位置，之后我们每压一次栈top都会向后移动一下，指向下一个空的位置，所以我们实际取栈顶的时候要 top-1 或者说，top是指向了栈顶的下一个元素

        ​​​​​​​​​​​​​​        ​​​​​​​        

1.2.6 返回栈的大小(多少有效数据)

        这没啥好说的，上代码

        

1.3 栈的完整代码

        Stack.h

#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;	//栈顶
	int capacity;
}ST;


void STInit(ST* ps);
void STDestory(ST* ps);

//压栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);

//取栈顶元素
STDataType STTop(ST* ps);

int STSize(ST* ps);

bool STEmpty(ST* ps);

        Stack.c

#include"Stack.h"

//初始化
void STInit(ST* ps)
{
	assert(ps);

	ps->a = NULL;
	ps->top = 0;
	ps->capacity = 0;
}

//销毁
void STDestory(ST* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}




//压栈
void STPush(ST* ps, STDataType x)
{
	assert(ps);

	//满了，要扩容
	if (ps->top == ps->capacity)
	{
		//防止是第一次扩容，所以要判断一下
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;	
		STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}

		ps->a = tmp;
		ps->capacity = newcapacity;
	}

	ps->a[ps->top] = x;
	ps->top++;
}



//出栈
void STPop(ST* ps)
{
	assert(ps);
	//栈不为空才能删
	assert(!STEmpty(ps));

	ps->top--;
}


//取栈顶元素
STDataType STTop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));

	return ps->a[ps->top-1];
}


//返回栈的大小(多少有效数据)
int STSize(ST* ps)
{
	assert(ps);

	return ps->top;
}


//判断栈是否真是空
bool STEmpty(ST* ps)
{
	assert(ps);

	//如果真是空就返回真
	//如果不是空就返回假
	return ps->top == 0;
}

2. 队列

2.1 队列的概念及结构

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

        入队列：进行插入操作的一端为队尾

        出队列：进行删除操作的一端为队头

        ​​​​​​​        ​​​​​​​        

2.2 队列的实现

        首先我们分析一下应该怎么实现队列

        如果用顺序表的话，数据从前向后依次存放，此操作还比较方便，但是到删除时，从前向后删除，每删一个元素，就要将后面的元素向前挪一位，时间复杂度O(N)

        所以推荐使用链表解决问题，尾插数据，头删数据，就像上面画的那个类似管道的示意图一样，此时问题又来了，尾插数据需要遍历链表，这样时间复杂度的问题依旧没解决，怎么办？

        解决方案就是我们再引入一个新的结构体，专门用来维护这条链表，新的结构体中存放这个链表的头节点和尾节点的地址，还有这个链表的长度，这样只需将新节点尾插到ptail后面就好了，不用遍历链表了。

        创建链表节点：

        ​​​​​​​        ​​​​​​​        

        创建新结构体用于维护链表：

                        

        之后在主函数中用也这个新结构体来代替链表头节点进行传参，或者说这个新结构体代替的整条链表，而链表头节点只是一个节点，孰强孰弱，一目了然。

2.2.1 队列的初始化和销毁

        因为我们创建的链表是不带头的，所以初始化都是无脑置空就好

        

        

2.2.2 队列中剩余元素

        ​​​​​​​        ​​​​​​​ 

2.2.3 入队列

2.2.4 出队列

        出队列要注意链表的三种状态，分别是链表尾空、链表只有一个节点、链表有多个节点。为空的情况用断言处理，多个节点就正常删除头节点就行，但是要注意只有一个节点的时候要处理ptail 否则它将变成野指针

        ​​​​​​​        

2.2.5 取队头、取队尾

        ​​​​​​​        

        ​​​​​​​        

2.2.6 判断队列为空

                

2.3 队列的完整代码

        Queue.h

#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

typedef int QDataType;
typedef struct QueueNode
{
	QDataType val;
	struct QueueNode* next;
}QNode;


typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

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

//销毁
void QueueDestory(Queue* pq);

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

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

//取队头
QDataType QueueFront(Queue* pq);

//取队尾
QDataType QueueBack(Queue* pq);

//判断队列为空
bool QueueEmpty(Queue* pq);

//队列中剩余元素
int QueueSize(Queue* pq);

        Queue.c

#include"Queue.h"

//初始化
void QueueInit(Queue* pq)
{
	assert(pq);

	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

//销毁
void QueueDestory(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->phead;
	QNode* next = NULL;
	while (cur)
	{
		next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

//入队列
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->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}

	pq->size++;
}

//出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	//保正头部有的删
	assert(pq->phead);

	QNode* next = pq->phead->next;
	//当只有一个节点时，要处理ptail
	if (pq->phead == pq->ptail)
	{
		pq->ptail = NULL;
	}
	free(pq->phead);
	pq->phead = next;
	pq->size--;
}

//取队头
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	//取队头前提是有队头
	assert(pq->phead);

	return pq->phead->val;
}

//取队尾
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	//取队尾前提是有队尾
	assert(pq->ptail);

	return pq->ptail->val;
}

//判断队列为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->size == 0;
}

//队列中剩余元素
int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}