【数据结构初阶】----栈和队列的基础功能的实现

栈

栈的概念及结构

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

栈的这个后进先出原则就好比羽毛球桶或者是弹匣
像下面这个羽毛球桶一样，我们将羽毛球一个一个放进去，那第一个放进去的羽毛球是不是我们最后一个取出来的，最后一个放进去的羽毛球则是我们开盖使用时取出的第一个羽毛球。
而栈也一样，如果我们想要取栈底的元素，我们只能从栈顶一个一个的把数据取走直到取到栈底的那个元素。

栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。因为在数组尾部插入数据只需长度size++即可，而使用链表的话我们则需要再申请一个节点，然后改变尾指针的位置。而进行删除操作的时候就更麻烦了，用数组实现的话我们只需要将size–，至于空间的释放我们只需要在最后销毁栈的时候一起释放就行，如果使用链表实现的话我们删除栈顶数据的时候我们不仅要找到前一个节点然后改变前一个节点的指向，还要释放删除的那个栈顶元素申请的空间。
实现栈功能的时候我们建立三个文件，一个头文件Stack.h用于定义栈的结构和实现功能时所需要的头文件以及后续函数的申请，两个源文件，一个Stack.c用于写功能实现的函数，一个test.c用于测试功能

栈的结构定义

栈的结构中包括一个指针a指向数据类型是STDataType的数组、一个记录数据个数的top，以及我们动态申请的空间大小capacity

typedef int STDataType;//元素类型

typedef struct Stack
{
	STDataType* a;
	int top;//栈顶的下一个元素
	int capacity;//空间大小
}ST;

栈的初始化

先判断传过来的指针的有效性，然后指针置空，数据个数和空间大小都先初始化为0，后续插入数据的时候我们在进行扩容操作

//初始化栈
void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->top = 0;//栈顶top指向有效元素的后一个
	pst->capacity = 0;
}

元素入栈

我们依旧先判断传过来的地址的有效性，然后我们判断空间是否够用，不够用的话我们需要malloc空间，这个操作我们称之为扩容，而扩容是扩多大呢？一般我们是将数组扩容为元素的两倍大。
在接下来我们看到这一段代码：
int newCapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
因为我们初始化的时候没有申请空间，所以如果是按两倍扩容的时候我们0*2还是等于0，所以我们使用一个三木操作符，如果初始空间是0我们就申请4个空间。
然后我们就直接在数组的栈顶插入数据即可，注意不要忘了让数据个数top++

//元素入栈
void STPush(ST* pst, STDataType x)
{
	assert(pst);
	//判断空间是否足够
	if (pst->top == pst->capacity)
	{
		int newCapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
		//主义realloc的其实地址是pst->a不是pst
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			perror("STPush():realloc");
			return;
		}
		pst->a = tmp;
		pst->capacity = newCapacity;
	}
	pst->a[pst->top++] = x;
}

元素出栈

这里除了判断地址有效性外还要注意的是栈里面的元素个数不能为0，栈里都没元素了我们还出什么？
出栈这个很简单，我们直接元素个数top–就好了，动态申请的空间我们等销毁栈的时候一起释放就好了。

//元素出栈
void STPop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	pst->top--;
}

获取栈顶元素

栈顶元素就是数组最后一个元素，因为数组是从0开始的，所以我们需要这样返回栈顶元素的时候记得返回的是下标是top-1的元素

//获取栈顶元素
STDataType STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	return pst->a[pst->top - 1];
}

获取栈中有效元素个数

我们直接返回我们记录的个数top就行了

//获取栈中有效元素个数
int STSize(ST* pst)
{
	return pst->top;
}

检测栈是否为空

栈里元素个数top为0就是空栈

bool STEmpty(ST* pst)
{
	assert(pst);
	return pst->top == 0;//空为真，返回1，不空为假，返回0
}

栈的销毁

释放申请的这块数组空间

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

队列

队列的概念及结构

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

队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低，因为删除队头元素后我们需要把后面的数据全部前移一位。
而对于链表实现的队列，在队头和队尾进行插入和删除操作的时间复杂度均为 O(1)。因为只需要修改指针的指向，不需要像数组那样移动大量元素。

队列的结构定义

QNode结构体是单链表的节点，Queue结构体中存放的是链表的头指针和尾指针以及链表的长度size

//队列：先进先出
typedef int QDataType;

//以链表为基础实现
typedef struct QueueNode
{
	QDataType val;
	struct QueueNode* next;
}QNode;

//因为后续函数要传的形参包括头指针和尾指针，二者要传的还是二级指针
//对于多个参数，我们直接定义一个结构体方便后续使用
typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

队列的初始化

初始化我们需要将链表的头指针和尾指针置空，长度也要初始化为0

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

从队尾入数据

入数据之前我们先为节点申请空间，从队尾入数据就是单链表的尾插操作，因为我们用的是不带头单向不循环链表，没有带“哨兵位”，所以我们插入数据的时候需要考虑链表是否为空两种情况，长度size别忘了++。

//队尾入队列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	//申请空间，因为只有入队需要申请空间，这里就不单独写一个函数
	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	if (newNode == NULL)
	{
		perror("QNodePush():malloc");
		return;
	}
	newNode->val = x;
	newNode->next = NULL;
	//空队列情况
	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newNode;
	}
	//非空队列情况
	else
	{
		pq->ptail->next = newNode;
		pq->ptail = newNode;
	}
	pq->size++;
}

从队头出数据

我们要对队列进行判空，没数据的话就出不了数据，从队头出数据就是删除单链表的头节点，删除之前别忘了保存头节点的下一个节点，当然如果链表中只有一个节点的话我们还需要改变尾节点的指向，因为只有一个节点的时候这个节点既是头节点也是尾节点，删除数据长度size别忘了–。

//队头出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->size);//有元素才能出
	//如果队列中只有一个元素
	if (pq->phead->next == NULL)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	//多元素
	else
	{
		QNode* next = pq->phead->next;
		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;
}

获取队列中有效元素的个数

这时候我们Queue结构体中定义的size就起作用了，我们返回size就可以了。

//获取队列中有效元素个数
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

检测队列是否为空

链表长度size==0队列则为空。

//检测队列是否为空，如果为空返回非0结果 如果非空返回0
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->size == 0;
}

队列的销毁

队列的销毁就是让我们把我们为链表节点动态申请的空间一个一个释放。

//销毁队列
void QueueDestory(Queue* pq)
{
	//空队列不影响
	assert(pq);
	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* nextNode = cur->next;
		free(cur);
		cur = nextNode;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}