数据结构 | 栈和队列

typedef int STDataType;	//栈的元素类型

typedef struct StackInfo
{
	STDataType* data;	//数据
	int top;	//栈顶
	int capacity;	//容量
}Stack;

void StackDestroy(Stack* ps)	//栈的销毁
{
	assert(ps);


	//只有为栈开辟空间了，才能正常销毁
	if (ps->data)
	{
		free(ps->data);
		ps->data = NULL;
		ps->top = ps->capacity = 0;
	}
}

void StackDestroy(Stack* ps)	//栈的销毁
{
	assert(ps);


	//只有为栈开辟空间了，才能正常销毁
	if (ps->data)
	{
		free(ps->data);
		ps->data = NULL;
		ps->top = ps->capacity = 0;
	}
}

void StackPush(Stack* ps, STDataType x)	//入栈
{
	assert(ps);

	//判断栈是否满
	if (ps->top == ps->capacity)
	{
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;	//二倍扩容
		STDataType* tmp = (STDataType*)realloc(ps->data, sizeof(STDataType) * newCapacity);
		//如果扩容失败，需要报错并结束程序
		if (tmp == NULL)
		{
			perror("realloc :: fail");
			exit(-1);
		}

		ps->data = tmp;
		ps->capacity = newCapacity;
	}

	//入栈，就是在栈顶处放入元素，然后栈顶+1
	ps->data[ps->top] = x;
	ps->top++;
}

void StackPop(Stack* ps)	//出栈
{
	assert(ps);
	assert(ps->top > 0);	//有元素才能出栈

	//出栈，直接栈顶-1
	ps->top--;
}

STDataType StackTop(Stack* ps)	//查看栈顶元素
{
	assert(ps);
	assert(ps->top > 0);	//有元素才能看

	//栈顶元素，在栈顶-1处，因为栈顶是从0开始的
	return ps->data[ps->top - 1];
}

int StackSize(Stack* ps)	//查看栈的有效元素个数
{
	assert(ps);

	//栈的大小就是当前栈的有效元素个数
	return ps->top;
}

bool StackEmpty(Stack* ps)	//判断栈是否为空
{
	assert(ps);

	//栈顶为0.说明栈空
	return ps->top == 0;
}

typedef int QListDataType;	//队列的数据类型

//这是队列中，单个节点的信息
typedef struct QListNode
{
	QListDataType data;
	struct QListNode* next;
}QNode;

//这是整个队列的信息，包含了队头和队尾两个指针
typedef struct QueueNode
{
	QNode* front;	//队头指针
	QNode* rear;	//队尾指针
	size_t size;	//队列长度
}Queue;

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

	//初始化状态：队头、队尾指针都指向空，队列大小为0
	pq->front = pq->rear = NULL;
	pq->size = 0;
}

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

	//销毁思路：利用临时指针进行销毁
	QNode* cur = pq->front;
	while (cur)
	{
		QNode* tmp = cur->next;
		free(cur);
		cur = tmp;
	}

	pq->front = pq->rear = NULL;
	pq->size = 0;
}

void QueuePush(Queue* pq, QListDataType x)	//入队
{
	assert(pq);

	//先买一个节点
	QNode* newnode = buyNode(x);

	//分情况：如果队头为空，说明队空，此时直接将新节点赋值给队头、队尾
	if (pq->front == NULL)
	{
		pq->front = pq->rear = newnode;
		pq->size++;
	}
	else
	{
		//否则就是将新节点，链接到队尾，然后更新队尾
		pq->rear->next = newnode;	//链接
		pq->rear = newnode;	//更新队尾
		pq->size++;
	}
}

void QueuePop(Queue* pq)	//出队
{
	assert(pq);
	assert(!QueueEmpty(pq));	//如果队空，是不能出队的

	//出队思想：有元素才能出队，更新队头，销毁原队头
	QNode* cur = pq->front;
	pq->front = pq->front->next;	//更新队头指针
	free(cur);
	cur = NULL;
	pq->size--;
}

QListDataType QueueFront(Queue* pq)	//查看队头元素
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->front->data;
}

QListDataType QueueRear(Queue* pq)	//查看队尾元素
{
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->rear->data;
}

int QueueSize(Queue* pq)	//当前队列的有效元素数
{
	assert(pq);

	return pq->size;	//直接返回就行了
}

bool QueueEmpty(Queue* pq)	//判断当前队空情况
{
	assert(pq);

	return pq->front == NULL;
}