【数据结构初阶】数组栈和链式队列的实现

//静态栈结构 - 很不实用
typedef int STDataType;
#define N 10
typedef struct Stack
{
	STDataType _a[N];
	int _top; // 栈顶
}Stack;

//动态栈结构
typedef int STDataType;
typedef struct Stack
{
	STDataType* array;
	int top;//这代表我们栈顶的位置，top会随着栈空间数据的扩大随之变换
	int capacity;
}ST;

void StackInit(ST* ps)
{
	assert(ps);
	ps->array = NULL;
	ps->top = 0;//ps->top = -1; 我们的top也是可以给-1的
	ps->capacity = 0;	

	//初始化时，top给的是0，意味着top指向栈顶数据的下一个
//我们的top指向的是最后栈顶数据的下一个，因为我们是先插入数据到下标为top的位置，然后top再++
	//初始化时，top给的是-1，意味着top指向栈顶数据
//我们的top指向的是栈顶数据，因为我们要先将top+1，然后再往此时的top位置放数据，下一次也是先将top位置+1再放数据

//这是一个什么问题呢？(就是)是先放数据再移动top呢？还是先移动top再放数据呢？
	
}

void StackDestroy(ST* ps)
{
	assert(ps);
	free(ps->array);
	ps->array = NULL;
	ps->capacity = ps->top = 0;
}

void StackPush(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->array, sizeof(STDataType) * newCapacity);
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->array = tmp;
		ps->capacity = newCapacity;
	}
	ps->array[ps->top] = x;	
	ps->top++;
}

void StackPop(ST* ps)//将元素进行出栈，删除数据
{
	assert(ps);
	assert(!StackEmpty(ps));//top为0的时候是不能进行删除的

	ps->top--;
}

bool StackEmpty(ST* ps)
{
	assert(ps);
	/*if (ps->top > 0)
	{
		return false;
	}
	else
	{
		return true;
	}*/

	return ps->top == 0;//这里的判断条件的正确与否，正好就对应上我们返回的是逻辑真还是逻辑假。true or false
}

STDataType StackTop(ST* ps)//取栈顶的数据
{
	assert(ps);
	assert(!StackEmpty(ps));//如果栈为空，就会报错

	//我们的栈必须得有数据你才能取数据啊，如果没有数据你还取数据的话，就是访问下标-1的数据了，造成越界访问
	return ps->array[ps->top - 1];
}

int StackSize(ST* ps)
{
	assert(ps);
	return ps->top;//top指向的是栈顶数据的下一个位置，又因为它从0开始增大，所以top的值正好就是栈数据的个数
}

#include "Stack.h"

void TestStack()
{
	ST st;
//1.用我们的结构体类型定义了一个结构体，结构体里面的array指针会指向我们动态开辟的数组栈，用于维护我们的数组栈
//2.我们其实实现的也是动态的数组栈，如果要实现静态的数组栈的话，我们还需在结构体里面定义定长数组，这非常的不方便
//跟个傻瓜一样，太低级了，所以我们选择柔性数组也就是用指针来维护我们的动态数组栈的方式实现，这还是比前者要高级的。
	
	StackInit(&st);
	//(&st)->array;值得注意的是，我们有时候也不必去创建一个结构体类型的指针来访问结构体成员，可以通过结构体变量本身的地址来
//访问其内部的成员，有意思哈。
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	printf("%d ", StackTop(&st));
	StackPop(&st);

	printf("%d ", StackTop(&st));
	StackPop(&st);

	StackPush(&st, 5);
	StackPush(&st, 6);
	StackPush(&st, 7); 
	while (!StackEmpty(&st))
	{
		printf("%d ", StackTop(&st));
		StackPop(&st);
	}
	//入栈1234出栈4321
	StackDestroy(&st);//如果我们不destroy的话，就会造成内存泄漏。
}
int main()
{
	TestStack();
	return 0;
}

typedef int QDataType;
typedef struct QueueNode//队列结构中的每一个结点
{
	struct QueueNode* next;
	QDataType data;
}QueueNode;
typedef struct Queue//我们的队列结构
{
	QueueNode* head;
	QueueNode* tail;
//这里我们其实也可以将这两个队列结点指针单独定义出来，但是这样不太符合代码的主流风格，所以我们将他们包到一个结构体里。
}Queue;
//单链表那里，我们是单独将单链表的头指针拎出来，独立于结点结构体定义的，这里我们是将两个指针合在一起定义到一个
//队列结构里面

//因为我们的队列不会在队尾进行删除，所以我们定义的尾指针的价值就得到了体现，而且用结构体封装这些指针还是有很多
//好处的，我们通过结构体指针就可以找到这些指针了，如果你不用结构体单独定义两个结点的指针，也不是不可以，但是
//你后面接口实现的时候，你就得传两个参数了，一个头指针一个尾指针，而且你要想修改他们的指向还得传二级指针
//就像下面这样来使用，那你调用接口的时候很有可能会被它烦死
void QueueInit(Queue** pphead, Queue** pptail);

void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

void QueueDestroy(Queue* pq)//销毁队列
{
	assert(pq);//head和tail可以为空，但我们的队列结构肯定不可以为空，如果队列结构都为空了，那肯定是我们传的参数出了问题
	QueueNode* cur = pq->head;
	//while (cur != pq->tail)
	//{
	//	//我们这里进行释放队列结点
	//	//但这种逻辑其实有问题，因为你最后一个队列结点的空间是没有进行删除的，会造成内存泄漏。
	//}
	while (cur != NULL)//当我们的cur走到NULL时，正好说明队列结点空间已经释放完毕了
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
}

void QueuePush(Queue* pq, QDataType x)
{
	//这里我们要分两种情况
	//1.我们的tail和head都是正常的，然后我们直接在tail后面插入队列结点，这就相当于我们的入队列，然后再更新一下tail的位置。
	//2.如果我们的tail和head都为空的话，我们直接将新的队列结点的地址赋值给我们的head和tail，此刻我们的尾和头所指位置是相同的
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	newnode->data = x;
	newnode->next = NULL;//将我们队列结点初始化

	if (pq->head == NULL) 
	{
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

void QueuePop(Queue* pq)
{
	assert(pq);//表达式计算结果为假(0)，assert就会报错
	assert(!QueueEmpty(pq));//我们的队列不可以为空
	QueueNode* next = pq->head->next;//如果我们这里的队列头指针为空，这里就造成内存读取权限访问冲突。
	free(pq->head);
//我们队列中的结点全被free掉了，可是tail的指向还是没人给他改一下，它还在指向一个已经被释放掉了的空间，
//tail就是一个典型的野指针
	pq->head = next;
	if (pq->head == NULL)
	{
		pq->tail = NULL;//我们的链表已经删除完之后，为了防止tail变为野指针，我们也让tail置为空
	}
}

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));//断言为假，程序就会崩
	return pq->head->data;
}

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));//粗暴判断队列结构和队列中的结点不为空

	return pq->tail->data;
}

int QueueSize(Queue* pq)//我们也可以在队列结构体定义那里加一个成员size_t _size，我们push它就++，pop它就--。
{
	assert(pq);
	QueueNode* cur = pq->head;
	int i = 0;
	while (cur)
	{
		i++;
		cur = cur->next;
	}
	return i;
}

void TestQueue1()
{
	Queue q;
	QueueInit(&q);//我们要改变队列结构，就传结构体指针过去，有了结构体指针，结构体中的东西就可以随便改了
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);//我们要想清楚我们改的是队列结构，而不是队列结点，所以我们应该传的是队列的地址，

	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);//想取到队列的下一个数据，必须得先出队列一个数据
	}
 	printf("\n");
	/*QueuePop(&q);
	QueuePop(&q);
	QueuePop(&q);
	QueuePop(&q);*/
	while (!QueueEmpty(&q))
	{
		printf("%d", QueueFront(&q));
		QueuePop(&q);
	}
//1.我们删除四次之后，通过调试窗口可以看出，我们的head已经变为空指针了，但此时tail所指的位置却不为空，所指结点
//的data却已经变为随机值了，此时tail其实是个野指针，因为删除的过程我们只注意移动head了，却没有管tail的死活
//2.printf("%d",QueueBack(&q));
//正好我们调用的QueueBack中的assert检查出来我们的队列结构此时为空了，但如果注释掉assert，其实是会打印出一个随机值

	QueueDestroy(&q);

}
//int main()
{

	TestQueue1();
	return 0;
}