栈

分析

栈的数据是栈顶进，栈顶出。
我们用数组和链表都可以，但是链表因为尾插和尾删没有数组方便，所以我们用数组。

例子：如果进去的顺序是1234，出来的顺序就是4321。
我们可以用一个数组来储存数据，然后再定义一个指针指向栈顶的数据，方便出栈和入栈。

typedef int SD;//随时更改数据类型
typedef struct stack
{
	SD* a;//数组
	int top;//栈顶的后一个位置
	int capacity;//容量
}ST;

这里用指针定义的数组，后面我们可以用扩容增加容量，这样就变成了一个数组。

初始化与销毁栈

一定要初始化空间，不然容易造成野指针的问题。
初始化

void StackInit(ST* ps)//初始化
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

初始化就不开辟空间了。
销毁栈
这里和链表不一样，比较方便，释放掉起始地址就好了。

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

出栈入栈与判断栈为空

入栈

void StackPush(ST* ps, SD x)//入栈
{
	assert(ps);
	//扩容
	if (ps->capacity == ps->top)//判断是否需要扩容
	{
		int count = (ps->capacity == 0 ? ps->capacity = 4 : ps->capacity * 2);//第一次扩容4个，之后的扩容的容量二倍增加
		SD* y = (SD*)realloc(ps->a, count * sizeof(SD));
		 if (y == NULL)
		 {
			 perror("realloc fail");
			 exit(-1);
		 }
		 ps->a = y;
		 ps->capacity = count;
	}
	ps->a[ps->top] = x;//赋值
	ps->top++;
}

例：

此时的top是4.
判断栈是否为空

bool StackEmpty(ST* ps)//判断
{
	assert(ps);
	return ps->top == 0;//如果为空就返回1，不为空返回0
}

出栈

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

出栈就很简单了，因为top是末尾的数据，如果想再入栈，入栈的地方是top指向的地方，会覆盖掉原来的数据。

获取栈顶元素

SD StackTop(ST* ps)//获取栈顶元素
{
	assert(ps);
	assert(!StackEmpty(ps));
	return ps->a[ps->top - 1];
}

获取栈中有效元素个数

top也就等于栈中数据的数量。

int StackSize(ST* ps)//获取栈中有效的元素
{
	assert(ps);
	return ps->top;
}

队列

分析

队列是从队头出，队尾入，数组就没有链表好用了，所以我们用单向链表。

结点

typedef int SD;
typedef struct QListNode
{
	struct QListNode* next;
	SD data;
}QL;

因为我们需要的是头删尾插，所以不仅仅需要头结点，还需要一个尾结点，这样更方便操作。

typedef struct Queue
{
	QL* head;//头结点，指向队列的队头
	QL* tail;//尾结点，指向队列的队尾
	int siz;//计算有多少个结点
}Qu;

初始化与销毁队列

初始化
头结点和尾结点的指向空即可，siz初始化为0用来记录结点数量。

void QueueInit(Qu* q)//初始化
{
	assert(q);
	q->head = q->tail = NULL;
	q->siz = 0;
}

销毁队列

void QueueDestroy(Qu* q)//销毁队列 
{
	assert(q);
	QL* cur = q->head;//这里要注意数据类型
	while (cur)
	{
		QL* del = cur -> next;
		free(cur);
		cur = del;
	}
	q->head = q->tail = NULL;
	q->siz = 0;
}

入列，出列与判断队列是否为空

入列
这里需要考虑队列是否为空的尾插。

void QueuePush(Qu* q, SD x)//入队
{
	assert(q);
	QL* w = (QL*)malloc(sizeof(QL));//新开辟结点
	if (w == NULL)
	{
		perror("malloc tail");
		exit(-1);
	}
	else
	{
		w->data = x;
		w->next = NULL;
	}
	if (q->head == NULL)//如果队列为空
	{
		q->head = q->tail = w;
	}
	else//如果队列不为空
	{
		q->tail->next = w;
		q->tail = w;
	}
	q->siz++;
}

判断
不为空返回0，为空返回非零。

bool QueueEmpty(Qu* q)//判断
{
	assert(q);
	return q->head == NULL;
}

出列
这里就是典型的头删了，只不过需要注意的是，tail是不会在这个函数中移动的，所以当释放掉tail指向的结点时，要把tail置为空，不然会成为野指针。

void QueuePop(Qu* q)//出队
{
	assert(q);
	assert(!QueueEmpty(q));
	if (q->head == NULL)//防止tail成为野指针
	{
		free(q->head);
		q->head = q->tail = NULL;
	}
	QL* cur = q->head;
	q->head = q->head->next;
	free(cur);
	cur = NULL;
	q->siz--;
}

获取队列头部，尾部元素

这里就体现了head和tail的好处。
头部

SD QueueFront(Qu* q)//获取队头元素
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->head->data;
}

尾部

SD QueueBack(Qu* q)//获取队尾元素
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->tail->data;
}

获取队列中有效元素个数

直接返回之前用于记录数量的siz就可以了。

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